A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract)
We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibr...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2016-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1609.04099v1 |
| _version_ | 1811303237902401536 |
|---|---|
| author | Stéphane Le Roux Arno Pauly |
| author_facet | Stéphane Le Roux Arno Pauly |
| author_sort | Stéphane Le Roux |
| collection | DOAJ |
| description | We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies.
For infinite sequential games we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are Delta^0_2 sets. |
| first_indexed | 2024-04-13T07:44:22Z |
| format | Article |
| id | doaj.art-13417d63bbe44c0f82501f8ac922a651 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-13T07:44:22Z |
| publishDate | 2016-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-13417d63bbe44c0f82501f8ac922a6512022-12-22T02:55:45ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802016-09-01226Proc. GandALF 201624225610.4204/EPTCS.226.17:15A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract)Stéphane Le Roux0Arno Pauly1 Universite libre de Bruxelles Universite libre de Bruxelles We consider a dynamical approach to sequential games. By restricting the convertibility relation over strategy profiles, we obtain a semi-potential (in the sense of Kukushkin), and we show that in finite games the corresponding restriction of better-response dynamics will converge to a Nash equilibrium in quadratic time. Convergence happens on a per-player basis, and even in the presence of players with cyclic preferences, the players with acyclic preferences will stabilize. Thus, we obtain a candidate notion for rationality in the presence of irrational agents. Moreover, the restriction of convertibility can be justified by a conservative updating of beliefs about the other players strategies. For infinite sequential games we can retain convergence to a Nash equilibrium (in some sense), if the preferences are given by continuous payoff functions; or obtain a transfinite convergence if the outcome sets of the game are Delta^0_2 sets.http://arxiv.org/pdf/1609.04099v1 |
| spellingShingle | Stéphane Le Roux Arno Pauly A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) Electronic Proceedings in Theoretical Computer Science |
| title | A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) |
| title_full | A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) |
| title_fullStr | A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) |
| title_full_unstemmed | A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) |
| title_short | A Semi-Potential for Finite and Infinite Sequential Games (Extended Abstract) |
| title_sort | semi potential for finite and infinite sequential games extended abstract |
| url | http://arxiv.org/pdf/1609.04099v1 |
| work_keys_str_mv | AT stephaneleroux asemipotentialforfiniteandinfinitesequentialgamesextendedabstract AT arnopauly asemipotentialforfiniteandinfinitesequentialgamesextendedabstract AT stephaneleroux semipotentialforfiniteandinfinitesequentialgamesextendedabstract AT arnopauly semipotentialforfiniteandinfinitesequentialgamesextendedabstract |