zbMATH — the first resource for mathematics

Inverse game theory: learning utilities in succinct games. (English) Zbl 1404.91059
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 413-427 (2015).
Summary: One of the central questions in game theory deals with predicting the behavior of an agent. Here, we study the inverse of this problem: given the agents’ equilibrium behavior, what are possible utilities that motivate this behavior? We consider this problem in arbitrary normal-form games in which the utilities can be represented by a small number of parameters, such as in graphical, congestion, and network design games. In all such settings, we show how to efficiently, i.e. in polynomial time, determine utilities consistent with a given correlated equilibrium. However, inferring both utilities and structural elements (e.g., the graph within a graphical game) is in general NP-hard. From a theoretical perspective our results show that rationalizing an equilibrium is computationally easier than computing it; from a practical perspective a practitioner can use our algorithms to validate behavioral models.
For the entire collection see [Zbl 1326.68026].

91A43 Games involving graphs
Full Text: DOI
[1] Kalyanaraman, S., Umans, C.: The complexity of rationalizing matchings. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol. 5369, pp. 171–182. Springer, Heidelberg (2008) · Zbl 1183.68311 · doi:10.1007/978-3-540-92182-0_18
[2] Kalyanaraman, S., Umans, C.: The complexity of rationalizing network formation. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, pp. 485–494, October 2009 · Zbl 1292.91151 · doi:10.1109/FOCS.2009.48
[3] Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 71–78. ACM, New York (2006) · Zbl 1301.68142 · doi:10.1145/1132516.1132527
[4] Chen, X., Deng, X., Teng, S.-H.: Settling the complexity of computing two-player Nash equilibria. J. ACM (JACM) 56(3), 14 (2009) · Zbl 1325.68095 · doi:10.1145/1516512.1516516
[5] Papadimitriou, C.H., Roughgarden, T.: Computing correlated equilibria in multi-player games. J. ACM 55(3), 14:1–14:29 (2008) · Zbl 1314.91012 · doi:10.1145/1379759.1379762
[6] Foster, D.P., Vohra, R.V.: Calibrated learning and correlated equilibrium. Games Econ. Behav. 21(12), 40–55 (1997) · Zbl 0894.90188 · doi:10.1006/game.1997.0595
[7] Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000) · Zbl 1020.91003 · doi:10.1111/1468-0262.00153
[8] Samuelson, P.A.: Consumption theory in terms of revealed preference. Economica 15(60), 243–253 (1948) · doi:10.2307/2549561
[9] Afriat, S.N.: The construction of utility functions from expenditure data. Int. Econ. Rev. 8(1), 67–77 (1967) · Zbl 0248.90001 · doi:10.2307/2525382
[10] Varian, H.R.: The nonparametric approach to demand analysis. Econometrica 50(4), 945–973 (1982) · Zbl 0483.90006 · doi:10.2307/1912771
[11] Varian, H.R.: Revealed preference. In: Samuelsonian Economics and the Twenty-First Century (2006) · doi:10.1093/acprof:oso/9780199298839.003.0007
[12] Nekipelov, D., Syrgkanis, V., Tardos, E.: Econometrics for learning agents. In: Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC 2015, pp. 1–18. ACM, New York (2015) · doi:10.1145/2764468.2764522
[13] Bresnahan, T.F., Reiss, P.C.: Empirical models of discrete games. J. Econometrics 48(1), 57–81 (1991) · Zbl 0745.90097 · doi:10.1016/0304-4076(91)90032-9
[14] Lise, W.: Estimating a game theoretic model. Comput. Econ. 18(2), 141–157 (2001) · Zbl 0996.91007 · doi:10.1023/A:1021086215235
[15] Bajari, P., Hong, H., Ryan, S.P.: Identification and estimation of a discrete game of complete information. Econometrica 78(5), 1529–1568 (2010) · Zbl 1202.91263 · doi:10.3982/ECTA5434
[16] Ng, A.Y., Russell, S.: Algorithms for inverse reinforcement learning. In: Proceedings of the 17th International Conference on Machine Learning, pp. 663–670. Morgan Kaufmann (2000)
[17] Abbeel, P., Ng, A.Y.: Apprenticeship learning via inverse reinforcement learning. In: Proceedings of the Twenty-first International Conference on Machine Learning, ICML 2004, pp. 1–8. ACM, New York (2004) · doi:10.1145/1015330.1015430
[18] Waugh, K., Ziebart, B.D., Andrew Bagnell, J.: Computational rationalization. The inverse equilibrium problem (2013)
[19] Ziebart, B.D., Maas, A., Andrew Bagnell, J., Dey, A.K.: Navigate like a cabbie: probabilistic reasoning from observed context-aware behavior. In: Proceedings of the Ubicomp, pp. 322–331 (2008) · doi:10.1145/1409635.1409678
[20] Ahuja, R.K., Orlin, J.B.: Inverse optimization. Oper. Res. 49(5), 771–783 (2001) · Zbl 1163.90764 · doi:10.1287/opre.49.5.771.10607
[21] Kearns, M., Littman, M.L., Singh, S.: Graphical models for game theory. In: Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI 2001, pp. 253–260. Morgan Kaufmann Publishers Inc, San Francisco (2001)
[22] Howson Jr., J.T.: Equilibria of polymatrix games. Manage. Sci. 18(5), 312–318 (1972) · Zbl 0228.90058 · doi:10.1287/mnsc.18.5.312
[23] Rosenthal, R.W.: A class of games possessing pure-strategy Nash equilibria. Int. J. Game Theory 2(1), 65–67 (1973) · Zbl 0259.90059 · doi:10.1007/BF01737559
[24] Chun, B.-G., Chaudhuri, K., Wee, H., Barreno, M., Papadimitriou, C.H., Kubiatowicz, J.: Selfish caching in distributed systems: a game-theoretic analysis. In: Proceedings of the 23rd Annual ACM Symposium on PODC, PODC 2004, pp. 21–30. ACM, New York (2004) · Zbl 1321.68068 · doi:10.1145/1011767.1011771
[25] Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4), 1602–1623 (2008) · Zbl 1173.91321 · doi:10.1137/070680096
[26] Fotakis, D.A., Kontogiannis, S.C., Koutsoupias, E., Mavronicolas, M., Spirakis, P.G.: The structure and complexity of nash equilibria for a selfish routing game. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 123–134. Springer, Heidelberg (2002) · Zbl 1056.68028 · doi:10.1007/3-540-45465-9_12
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.