Infinite Subgame Perfect Equilibrium in the Hausdorff Difference Hierarchy

详细信息    查看全文

• 关键词：Infinite multi ; player games in extensive form ; Subgame perfection ; Borel hierarchy ; Preference characterization ; Pareto ; optimality
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9541
• 期：1
• 页码：147-163
• 全文大小：329 KB
• 参考文献：1.Abramsky, S., Winschel, V.: Coalgebraic analysis of subgame-perfect equilibria in infinite games without discounting (2012). arXiv preprint
  2.Brihaye, T., Bruyère, V., De Pril, J., Gimbert, H.: On subgame perfection in quantitative reachability games. Logical Methods in Computer Science, vol. 9 (2012)
  3.Brihaye, T., Bruyère, V., Meunier, N., Raskin, J.F.: Weak subgame perfect equilibria and their application to quantitative reachability (2015)
  4.Büchi, J.R., Landweber, L.H.: Solving sequential conditions by finite-state strategies. Trans. Am. Math. Soc. 138, 295–311 (1969)CrossRef MATH
  5.Escardó, M., Oliva, P.: Selection functions, bar recursion and backward induction. Math. Struct. Comput. Sci. 20(4), 127–168 (2010)CrossRef MATH
  6.Flesch, J., Kuipers, J., Mashiah-Yaakovi, A., Schoenmakers, G., Solan, E., Vrieze, K.: Perfect-information games with lower-semicontinuous payoffs. Math. Oper. Res. 35, 742–755 (2010)CrossRef MathSciNet MATH
  7.Flesch, J., Kuipers, J., Mashiah-Yaakovi, A., Schoenmakers, G., Shmaya, E., Solan, E., Vrieze, K.: Non-existence of subgame-perfect \(\varepsilon \) -equilibrium in perfect information games with infinite horizon. Int. J. Game Theor. 43(4), 945–951 (2014)CrossRef MathSciNet MATH
  8.Fudenberg, D., Levine, D.: Subgame-perfect equilibria of finite- and infinite-horizon games. J. Econ. Theor. 31(2), 251–268 (1983)CrossRef MathSciNet MATH
  9.Gale, D., Stewart, F.M.: Infinite games with perfect information. Ann. Math. Stud. 28, 245–266 (1953)MathSciNet
  10.Gimbert, H., Zielonka, W.: Games where you can play optimally without any memory. In: Abadi, M., de Alfaro, L. (eds.) CONCUR 2005. LNCS, vol. 3653, pp. 428–442. Springer, Heidelberg (2005)CrossRef
  11.Kechris, A.S.: Classical Descriptive Set Theory. Graduate Texts in Mathematics, vol. 156. Springer, New York (1995)MATH
  12.Kuhn, H.W.: Extensive games and the problem of information. In: Contributions to the Theory of Games II, pp. 193–216 (1953)
  13.Le Roux, S.: Acyclic preferences and existence of sequential nash equilibria: a formal and constructive equivalence. In: Berghofer, S., Nipkow, T., Urban, C., Wenzel, M. (eds.) TPHOLs 2009. LNCS, vol. 5674, pp. 293–309. Springer, Heidelberg (2009)CrossRef
  14.Le Roux, S.: Infinite sequential Nash equilibrium. Logical Methods in Computer Science, 9 (2013). Special Issue for the Conference Computability and Complexity in Analysis, (CCA 2011)
  15.Le Roux, S.: From winning strategy to Nash equilibrium. Math. Logic Q. 60, 354–371 (2014)CrossRef MATH
  16.Le Roux, S., Pauly, A.: Infinite sequential games with real-valued payoffs. In: Proceedings of LiCS (2014)
  17.Le Roux, S., Pauly, A.: Weihrauch degrees of finding equilibria in sequential games. In: Proceedings of CiE 2015 (2015) (to appear)
  18.Lescanne, P., Perrinel, M.: Backward coinduction, Nash equilibrium and the rationality of escalation. Acta Informatica 49(3), 117–137 (2012)CrossRef MathSciNet MATH
  19.Martin, D.A.: Borel determinacy. Ann. Math. 102, 363–371 (1975)CrossRef MATH
  20.Martin, D.A.: An extension of Borel determinacy. Ann. Pure Appl. Logic 49, 279–293 (1990)CrossRef MathSciNet MATH
  21.Mertens, J-F.: Repeated games. In: Proceedings of the International Congress of Mathematicians, pp. 1528–1577. American Mathematical Society (1987)
  22.Purves, R., Sudderth, W.: Perfect information games with upper-semicontinuous payoffs. Math. Oper. Res. 36, 468–473 (2011)CrossRef MathSciNet MATH
  23.Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit. Zeitschrift für die desamte Staatswissenschaft, vol. 121 (1965)
  24.Smith, M.J., Price, G.R.: The logic of animal conflicts. Nature 246, 15–18 (1973)CrossRef
  25.Solan, E., Vieille, N.: Deterministic multi-player dynkin games. J. Math. Econ. 39(8), 911–929 (2003)CrossRef MathSciNet MATH
  26.Ummels, M.: Rational behaviour and strategy construction in infinite multiplayer games. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 212–223. Springer, Heidelberg (2006)CrossRef
  27.Wolfe, P.: The strict determinateness of certain infinite games. Pac. J. Math. 5, 841–847 (1955)CrossRef MathSciNet MATH
  
• 作者单位：Stéphane Le Roux (15)
  
  15. Université Libre de Bruxelles, Brussels, Belgium
  
• 丛书名：Topics in Theoretical Computer Science
• ISBN：978-3-319-28678-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Subgame perfect equilibria are specific Nash equilibria in perfect information games in extensive form. They are important because they relate to the rationality of the players. They always exist in infinite games with continuous real-valued payoffs, but may fail to exist even in simple games with slightly discontinuous payoffs. This article considers only games whose outcome functions are measurable in the Hausdorff difference hierarchy of the open sets (i.e. \({ {\Delta }}^0_2\) when in the Baire space), and it characterizes the families of linear preferences such that every game using these preferences has a subgame perfect equilibrium: the preferences without infinite ascending chains (of course), and such that for all players a and b and outcomes x, y, z we have \(\lnot (z <_a y <_a x \,\wedge \, x <_b z <_b y)\). Moreover at each node of the game, the equilibrium constructed for the proof is Pareto-optimal among all the outcomes occurring in the subgame. Additional results for non-linear preferences are presented.