×

Robust game theory. (English) Zbl 1134.91309

Summary: We present a distribution-free model of incomplete-information games, both with and without private information, in which the players use a robust optimization approach to contend with payoff uncertainty. Our “robust game” model relaxes the assumptions of Harsanyi’s Bayesian game model, and provides an alternative distribution-free equilibrium concept, which we call “robust-optimization equilibrium,” to that of the ex post equilibrium. We prove that the robust-optimization equilibria of an incomplete-information game subsume the ex post equilibria of the game and are, unlike the latter, guaranteed to exist when the game is finite and has bounded payoff uncertainty set. For arbitrary robust finite games with bounded polyhedral payoff uncertainty sets, we show that we can compute a robust-optimization equilibrium by methods analogous to those for identifying a Nash equilibrium of a finite game with complete information. In addition, we present computational results.

MSC:

91A06 \(n\)-person games, \(n>2\)
91A10 Noncooperative games
91A15 Stochastic games, stochastic differential games
90C05 Linear programming

Software:

PHCpack; Gambit
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23 (4), 769–805 (1998) · Zbl 0977.90052
[2] Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25 (1), 1–13 (1999) · Zbl 0941.90053
[3] Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Prog., Ser. A 88, 411–424 (2000) · Zbl 0964.90025
[4] Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont, MA, 1999 · Zbl 1015.90077
[5] Bertsimas, D., Pachamanova, D., Sim, M.: Robust linear optimization under general norms. Oper. Res. Lett. 32, 510–516 (2004) · Zbl 1054.90046
[6] Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Prog. 98, 49–71 (2003) · Zbl 1082.90067
[7] Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52 (1), 35–53 (2004) · Zbl 1165.90565
[8] Bohnenblust, H., Karlin, S.: On a theorem of Ville. In: H. Kuhn, A. Tucker (eds.), Contributions to the theory of games, vol. 1, Princeton UP, Princeton, 1950, pp. 155–160 · Zbl 0041.25701
[9] Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge UP, New York, 1998 · Zbl 0931.68015
[10] Brouwer, L.: Uber abbildung von mannigfaltikeiten. Mathematische Annalen 71, 97–115 (1912) · JFM 42.0417.01
[11] Courant, R.: Variational methods for the solution of problems of equilibrium and vibrations. Bull. Am. Math. Soc. 49, 1–23 (1943) · Zbl 0063.00985
[12] Crémer, J., McLean, R.: Optimal selling strategies under uncertainty for a discriminating monopolist when demands are interdependent. Econometrica 53 (2), 345–362 (1985) · Zbl 0567.90011
[13] Datta, R.: Using computer algebra to find Nash equilibria. In: J. Senda (ed.), Proc. 2003 Intl. Symp. on Symb. and Alg. Comp., ACM Press, New York, 2003, pp. 74–79 · Zbl 1072.68659
[14] Debreu, G.: A social equilibrium existence theorem. Proc. Nat. Acad. Sci., USA 38, 886–893 (1952) · Zbl 0047.38804
[15] Dow, J., Werlang, S.: Nash equilibrium under Knightian uncertainty: Breaking down backward induction. J. Econ. Theory 64, 305–324 (1994) · Zbl 0813.90132
[16] El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Analysis and Applications 18 (4), 1035–1064 (1997) · Zbl 0891.65039
[17] El Ghaoui, L., Oustry, F., Lebret, H.: Robust solutions to uncertain semidefinite programs. SIAM J. Optim. 9 (1), 33–52 (1999) · Zbl 0960.93007
[18] Fiacco, A., McCormick, G.: Nonlinear programming: Sequential unconstrained minimization techniques. John Wiley & Sons, New York, 1968 · Zbl 0193.18805
[19] Fudenberg, D., Levine, D.: The Theory of Learning in Games. Series on Economic Learning and Social Evolution. MIT Press, Cambridge, MA, 1998 · Zbl 0939.91004
[20] Fudenberg, D., Tirole, J.: Game Theory. MIT Press, Cambridge, MA, 1991 · Zbl 0596.90015
[21] Gilboa, I., Schmeidler, D.: Maxmin expected utility with a non-unique prior. J. Math. Econ. 18, 141–153 (1989) · Zbl 0675.90012
[22] Goldberg, A., Wright, A., Karlin, A., Hartline, J., Saks, M.: Competitive auctions, 2002. Submitted to Games and Economic Behavior · Zbl 1125.91041
[23] Govindan, S., Wilson, R.: A global Newton method to compute Nash equilibria. J. Econ. Theory 110, 65–86 (2003) · Zbl 1042.91001
[24] Harsanyi, J.: Games with incomplete information played by ‘Bayesian’ players, parts I–III. Mgmt. Sci. 14, 159–182,320–334,486–502 (1967, 1968) · Zbl 0207.51102
[25] Holmström, B., Myerson, R.: Efficient and durable decision rules with incomplete information. Econometrica 51, 1799–1820 (1983) · Zbl 0521.90008
[26] Holzman, R., Kfir-Dahav, N., Monderer, D., Tennenholtz, M.: Bundling equilibrium in combinatorial auctions. Games and Economic Behavior 47 (1), 104–123 (2004) · Zbl 1077.91023
[27] Hyafil, N., Boutilier, C.: Regret minimizing equilibria and mechanisms for games with strict type uncertainty. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence (AUAI ’04), AUAI Press, Arlington, VA, USA, 2004, pp. 268–277
[28] Kakutani, S.: A generalization of Brouwer’s fixed point theorem. Duke Math. J. 8, 457–459 (1941) · JFM 67.0742.03
[29] Klibanoff, P.: Uncertainty, decision, and normal form games, 1993. Manuscript, MIT
[30] Knight, F.: Risk, Uncertainty and Profit. Houghton Mifflin, Boston, 1921
[31] Lemke, C., Howson, J.: Equilibrium points of bimatrix games. SIAM J. Appl. Math. 12 (2), 413–423 (1964) · Zbl 0128.14804
[32] Lo, K.: Equilibrium in beliefs under uncertainty. J. Econ. Theory 71 (2), 443–484 (1996) · Zbl 0877.90092
[33] Ma, T.: Banach-Hilbert spaces, vector measures and group representations. World Scientific, New Jersey, 2002 · Zbl 1012.46001
[34] Marinacci, M.: Ambiguous games. Games and Economic Behavior 31 (2), 191–219 (2000) · Zbl 0966.91002
[35] McKelvey, R., McLennan, A.: Computation of equilibria in finite games. In: H. Amman, D. Kendrick, J. Rust (eds.), Handbook of computational economics, vol. I, Elsevier, 1996, pp. 87–142 · Zbl 1126.91304
[36] McKelvey, R., McLennan, A., Turocy, T.: Gambit: Software tools for game theory, version 0.97.0.6, 2004. http://econweb.tamu.edu/gambit/
[37] Mertens, J., Zamir, S.: Formulation of Bayesian analysis for games with incomplete information. Intl. J. Game Theory 14 (1), 1–29 (1985) · Zbl 0567.90103
[38] Morris, S.: The common prior assumption in economic theory. Econ. Philosophy 11, 227–253 (1995)
[39] Nash, J.: Equilibrium points in N-person games. Proc. Nat. Acad. Sci., USA 36, 48–49 (1950) · Zbl 0036.01104
[40] Nash, J.: Non-cooperative games. Ann. Math. 54 (2), 286–295 (1951) · Zbl 0045.08202
[41] Osborne, M., Rubenstein, A.: A Course in Game Theory. MIT Press, Cambridge, MA, 1994
[42] Papadimitriou, C.: Algorithms, games, and the internet. In: STOC ’01: Proc. 33rd Annual ACM Symposium on the Theory of Computing, ACM Press, New York, 2001, pp. 749–753 · Zbl 1323.68022
[43] Porter, R., Nudelman, E., Shoham, Y.: Simple search methods for finding a Nash equilibrium. In: Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-2004), 2004, pp. 664–669 · Zbl 1142.91313
[44] Scarf, H.: The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15 (5), 1328–1343 (1967) · Zbl 0153.49401
[45] Scarf, H.: The Computation of Economic Equilibria. Yale UP, New Haven, CT, 1973. In collaboration with T. Hansen · Zbl 0311.90009
[46] Smart, D.: Fixed Point Theorems. Cambridge UP, New York, 1974 · Zbl 0297.47042
[47] Soyster, A.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 21, 1154–1157 (1973) · Zbl 0266.90046
[48] Sturmfels, B.: Solving systems of polynomial equations. American Mathematical Society, Providence, RI, 2002 · Zbl 1101.13040
[49] van der Laan, G., Talman, A.: On the computation of fixed points in the product space of unit simplices and an application to noncooperative N person games. Math. Oper. Res. 7, 1–13 (1982) · Zbl 0497.90063
[50] van der Laan, G., Talman, A., van der Heyden, L.: Simplicial variable dimension algorithms for solving the nonlinear complementarity problem on a product of unit simplices using a general labeling. Math. Oper. Res. 12, 377–397 (1987) · Zbl 0638.90096
[51] Verschelde, J.: Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation. ACM Trans. Math. Softw. 25 (2), 251–276 (1999) · Zbl 0961.65047
[52] von Neumann, J., Morgenstern, O.: Theory of Games and Economic Behaviour. Princeton UP, 1944 · Zbl 0063.05930
[53] von Stengel, B.: Computing equilibria for two-person games. In: R. Aumann, S. Hart (eds.), Handbook of game theory with economic applications, vol. 3, chap. 45, Elsevier, 2002, pp. 1723–1759 · Zbl 1103.91319
[54] Wardrop, J.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, vol. 1, part II, 1952, pp. 325–78
[55] Wilson, R.: Game-theoretic approaches to trading processes. In: T. Bewley (ed.), Advances in Economic Theory: Fifth World Congress, chap. 2, Cambridge UP, New York, 1987, pp. 33–77
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.