Computing equilibria for congestion games with (im)perfect information

ABSTRACT

We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a particular demand of service and the behavior of the customers is determined by utility functions that are non-increasing in the congestion. Customers decide whether to join or leave the service based on the experienced congestion and the offered prices. Following standard game theory, we assume each customer behaves in the most rational way. If the prices of service are fixed, then such a customer behavior leads to a pure, not necessarily unique Nash equilibrium among the customers. In order to evaluate marketing strategies, the service provider is interested in estimating its revenue under the best and worst customer equilibria. We study the complexity of this problem under different models of information available to the provider.•We first consider the classical model in which the provider has perfect knowledge of the behavior of all customers. We present a complete characterization of the complexity of computing optimal pricing strategies and of computing best and worst equilibria. Basically, we show that most of these problems are inapproximable in the worst case but admit an "average-case FPAS." Our average case analysis covers general distributions for customer demands and utility thresholds. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.•We extend our analysis to a more realistic model in which the provider has incomplete information. Following the game theoretic framework of Bayesian games introduced by Harsanyi, we assume that the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best and worst equilibria. Somewhat counterintuitive, we obtain an FPRAS for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst case measures. In particular, the worst case complexity of the considered stochastic equilibria problems increases with the precision of the available knowledge.

REFERENCES

• 1: Rene Beier , Berthold Vöcking, Random knapsack in expected polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780578]
• 2: Rene Beier , Berthold Vöcking, Probabilistic analysis of knapsack core algorithms, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 3: V. Conitzer and T. Sandholm. Complexity results about Nash equilibria. TR CMU-CS-02-135. Carnegie-Mellon U., 2002.
• 4: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 5: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 6: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 7: R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Nashification and the coordination ratio for a selfish routing game. 30th ICALP, 2003.
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Ashish Goel , Piotr Indyk, Stochastic Load Balancing and Related Problems, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.579, October 17-18, 1999
• 10: A. V. Goldberg , A. Marchetti-Spaccamela, On finding the exact solution of a zero-one knapsack problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.359-368, December 1984 [doi>10.1145/800057.808701]
• 11: M. Harris and A. Raviv. A theory of monopoly pricing schemes with demand uncertainty. The American Economic Review, 71(3): 347--365, 1981.
• 12: J. C. Harsanyi. Games with incomplete information played by Bayesian players, I, II, III. Management Science, 14: 159--182, 320--332, 468--502, 1968.
• 13: J. C. Harsanyi. Games with randomly disturbed payoffs. International Journal of Game Theory, 2: 1--23, 1973.
• 14: R. Holzman, N. Law-Yone. Strong equilibrium in congestion games. Games and Economic Behavior, 21: 85--101, 1997.
• 15: R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4): 199--216, 1996.
• 16: Jon Kleinberg , Yuval Rabani , Éva Tardos, Allocating bandwidth for bursty connections, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.664-673, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258661]
• 17: A. S. Kyle. Informed speculation with imperfect competition. The Review of Economic Studies, 56(3): 317--355, 1989.
• 18: H E. Leland and A. Meyer. Monopoly pricing structures with imperfect discrimination. The Bell J. Economics, 7(2): 449--462, 1976.
• 19: D. Manlove. Minimaximal and maximinimal optimization problems: a partial order-based approach. PhD thesis, University of Glasgow, Dept. of Computing Science, June 1998. http://www.dcs.gla.ac.uk/ davidm/publications.html.
• 20: E. Maskin and J. Riley. Monopoly with incomplete information. The RAND Journal of Economics, 15(2): 171--196, 1984.
• 21: I. Milchtaich. Congestion games with player-specific payoff function. Games and Economic Behavior, 13: 111--124, 1996.
• 22: Igal Milchtaich, Crowding games are sequentially solvable, International Journal of Game Theory, v.27 n.4, p.501-509, Jan. 1999 [doi>10.1007/s001820050086]
• 23: D. Monderer and L. S. Shapley. Potential games. Games and Economic Behavior, 14: 124--143, 1996.
• 24: W. Y. Oi. A Disneyland dilemma: Two part tariffs for a Mickey Mouse monopoly. The Quarterly Journal of Economics, 85(1): 77--96, 1971.
• 25: Amir Ronen, On approximating optimal auctions, Proceedings of the 3rd ACM conference on Electronic Commerce, p.11-17, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501160]
• 26: Amir Ronen , Amin Saberi, On the Hardness of Optimal Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.396-405, November 16-19, 2002
• 27: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. Int. Journal of Game Theory, 2: 65--67, 1973.
• 28: R. Schmalensee. Monopolistic two-part pricing arrangements. The Bell J. of Economics, 12(2): 445--466, 1981.
• 29: S. Scotchmer. Two-tier pricing of shared facilities in a free-entry equilibrium. The RAND J. Economics, 16: 456--472, 1985.
• 30: R. W. Staiger and F. A. Wolak. Collusive pricing with capacity constraints in the presence of demand uncertainty. The RAND Journal of Economics, 23(2): 203--220, 1992.
• 31: T. Ui. A Shapley value representation of potential games. Games and Economic Behavior, 31: 121--135, 2000.