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.
- Bierman, H. S., and Fernandez, L. 1998. Game Theory with Economic Applications. Addison-Wesley, Reading, MA.Google Scholar
- Fabrikant, A., Papadimitriou, C. H., and Talwar, K. 2004. The complexity of pure Nash equilibria. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing. ACM, New York, 604--612. Google ScholarDigital Library
- Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., and Spirakis, P. 2002. The structure and complexity of Nash equilibria for a selfish routing game. In In Proceedings of the 29th Annual International Colloquium on Automata, Languages and Programming. Springer-Verlag, Berlin, Germany, 123--134. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Garey, M. R., and Johnson, M. R. 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, CA. Google ScholarDigital Library
- Harris, M., and Raviv, A. 1981. A theory of monopoly pricing schemes with demand uncertainty. Amer. Econ. Rev. 71, 3, 347--365.Google Scholar
- Harsanyi, J. C. 1967--1968. Games with incomplete information played by Bayesian players, I, II, III. Management Science 14, 159--182, 320--332.Google ScholarDigital Library
- Harsanyi, J. C. 1973. Games with randomly disturbed payoffs. Int. J. Game Theory 2, 1--23.Google ScholarCross Ref
- Holzman, R., and Law-Yone, N. 1997. Strong equilibrium in congestion games. Games Econ. Behav. 21, 85--101.Google ScholarCross Ref
- Ibarra O. H., and Kim, C. E. 1975. Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM 22, 463--468. Google ScholarDigital Library
- Kellerer, H., Pferschy, U., and Pisinger, D. 2004. Knapsack Problems. Springer-Verlag, Berlin, Germany.Google Scholar
- Klemperer, P. 1999. Auction theory: A guide to the literature. J. Econ. Surv. 13, 3, 227--286.Google ScholarCross Ref
- Kyle, A. S. 1989. Informed speculation with imperfect competition. Rev. Econ. Stud. 56, 3, 317--355.Google ScholarCross Ref
- Leland, H. E., and Meyer, A. 1976. Monopoly pricing structures with imperfect discrimination. Bell J. Econ. 7, 2, 449--462.Google ScholarCross Ref
- 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.Google Scholar
- Maskin, E., and Riley, J. 1984. Monopoly with incomplete information. RAND J. Econ. 15, 2, 171--196.Google ScholarCross Ref
- 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.Google Scholar
- Milchtaich, I. 1996. Congestion games with player-specific payoff function. Games Econ. Behav. 13, 111--124.Google ScholarCross Ref
- Milchtaich, I. 1998. Crowding games are sequentially solvable. Int. J. Game Theory 27, 501--509. Google ScholarDigital Library
- Monderer, D., and Shapley, L. S. 1996. Potential games. Games Econ. Behav. 14, 124--143.Google ScholarCross Ref
- Myerson, R. 1981. Optimal auction design. Math. Oper. Research 6, 58--73.Google ScholarDigital Library
- Oi, W. Y. 1971. A Disneyland dilemma: Two part tariffs for a Mickey Mouse monopoly. Quart. J. Econ. 85, 1, 77--96.Google ScholarCross Ref
- Owen, G. 1995. Game Theory. Academic Press, New York.Google Scholar
- Ronen, A. 2001. On approximating optimal auctions. In Proceedings of the 3rd ACM Conference on Electronic Commerce. ACM, New York, 11--17. Google ScholarDigital Library
- Ronen, A., and Saberi, A. 2002. On the hardness of optimal auctions. In Proceedings of the 43st IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 396--405. Google ScholarDigital Library
- Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2, 65--67.Google ScholarDigital Library
- Schmalensee, R. 1981. Monopolistic two-part pricing arrangements. Bell J. Econ. 12, 2, 445--466.Google ScholarCross Ref
- Scotchmer, S. 1985. Two-tier pricing of shared facilities in a free-entry equilibrium. RAND J. Econ. 16, 456--472.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- Ui, T. 2000. A Shapley value representation of potential games. Games Econ. Behav. 31, 121--135.Google ScholarCross Ref
Index Terms
- Computing equilibria for a service provider game with (Im)perfect information
Recommendations
Settling the complexity of Leontief and PLC exchange markets under exact and approximate equilibria
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingOur first result shows membership in PPAD for the problem of computing approximate equilibria for an Arrow-Debreu exchange market for piecewise-linear concave (PLC) utility functions. As a corollary we also obtain membership in PPAD for Leontief ...
Perfect bayesian equilibria in repeated sales
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithmsA special case of Myerson's classic result describes the revenue-optimal equilibrium when a seller offers a single item to a buyer. We study a natural repeated sales extension of this model: a seller offers to sell a single fresh copy of an item to the ...
On the Complexity of Nash Equilibria and Other Fixed Points
We reexamine what it means to compute Nash equilibria and, more generally, what it means to compute a fixed point of a given Brouwer function, and we investigate the complexity of the associated problems. Specifically, we study the complexity of the ...
Comments