Computing equilibria for a service provider game with (Im)perfect information

ABSTRACT

We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a service to a set of potential customers. Each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider.Classical game theory assumes complete information: the provider has full knowledge of the behavior of all customers. We present a complete characterization of the complexity of computing optimal pricing strategies and of computing best/worst equilibria in this model. Basically, we show that most of these problems are inapproximable in the worst case but admit an FPAS in the average case. Our average case analysis covers large classes of distributions for customer utilities. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.A more realistic model considers providers with incomplete information. Following the game theoretic framework of Bayesian games introduced by Harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best/worst equilibria. Somewhat counterintuitively, 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 problems increases with the precision of the available knowledge.

REFERENCES

• 1: Bierman, H. S., and Fernandez, L. 1998. Game Theory with Economic Applications. Addison-Wesley, Reading, MA.
• 2: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 3: 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
• 4: Feldmann, R., Gairing, M., Lücking, T., Monien, B., and Rode, M. 2003. Nashification and the coordination ratio for a selfish routing game. Proceedings of the 30th Annual International Colloquium on Automata, Languages and Programming Springer-Verlag, Berlin, Germany, 514--526.
• 5: 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
• 6: Harris, M., and Raviv, A. 1981. A theory of monopoly pricing schemes with demand uncertainty. Amer. Econ. Rev. 71, 3, 347--365.
• 7: Harsanyi, J. C. 1967--1968. Games with incomplete information played by Bayesian players, I, II, III. Management Science 14, 159--182, 320--332.
• 8: Harsanyi, J. C. 1973. Games with randomly disturbed payoffs. Int. J. Game Theory 2, 1--23.
• 9: Holzman, R., and Law-Yone, N. 1997. Strong equilibrium in congestion games. Games Econ. Behav. 21, 85--101.
• 10: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 11: Kellerer, H., Pferschy, U., and Pisinger, D. 2004. Knapsack Problems. Springer-Verlag, Berlin, Germany.
• 12: Klemperer, P. 1999. Auction theory: A guide to the literature. J. Econ. Surv. 13, 3, 227--286.
• 13: Kyle, A. S. 1989. Informed speculation with imperfect competition. Rev. Econ. Stud. 56, 3, 317--355.
• 14: Leland, H. E., and Meyer, A. 1976. Monopoly pricing structures with imperfect discrimination. Bell J. Econ. 7, 2, 449--462.
• 15: Manlove, D. 1998. Minimaximal and maximinimal optimization problems: A partial order-based approach. Ph.D. dissertation. University of Glasgow, Department of Computing Science. http://www.dcs.gla.ac.uk/~davidm/publications.html.
• 16: Maskin, E., and Riley, J. 1984. Monopoly with incomplete information. RAND J. Econ. 15, 2, 171--196.
• 17: McDiarmid, C. 1998. Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms and Combinatorics, M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, Eds. Springer-Verlag, Berlin, Germany, pp. 195--247.
• 18: Milchtaich, I. 1996. Congestion games with player-specific payoff function. Games Econ. Behav. 13, 111--124.
• 19: 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]
• 20: Monderer, D., and Shapley, L. S. 1996. Potential games. Games Econ. Behav. 14, 124--143.
• 21: Myerson, R. 1981. Optimal auction design. Math. Oper. Research 6, 58--73.
• 22: Oi, W. Y. 1971. A Disneyland dilemma: Two part tariffs for a Mickey Mouse monopoly. Quart. J. Econ. 85, 1, 77--96.
• 23: Owen, G. 1995. Game Theory. Academic Press, New York.
• 24: 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]
• 25: 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
• 26: Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.
• 27: Schmalensee, R. 1981. Monopolistic two-part pricing arrangements. Bell J. Econ. 12, 2, 445--466.
• 28: Scotchmer, S. 1985. Two-tier pricing of shared facilities in a free-entry equilibrium. RAND J. Econ. 16, 456--472.
• 29: Staiger, R. W., and Wolak, F. A. 1992. Collusive pricing with capacity constraints in the presence of demand uncertainty. RAND J. Econ. 23, 2, 203--220.
• 30: Ui, T. 2000. A Shapley value representation of potential games. Games Econ. Behav. 31, 121--135.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.0 General
          Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
Market equilibria, imperfect information, service provider games