Dynamics and Coalitions in Sequential Games
We consider N-player non-zero sum games played on finite trees (i.e., sequential games), in which the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome wrt to the current strategy profile). This generates a dynamics in the game which may ev...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2017-09-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1709.02100v1 |
| _version_ | 1818130588407693312 |
|---|---|
| author | Thomas Brihaye Gilles Geeraerts Marion Hallet Stéphane Le Roux |
| author_facet | Thomas Brihaye Gilles Geeraerts Marion Hallet Stéphane Le Roux |
| author_sort | Thomas Brihaye |
| collection | DOAJ |
| description | We consider N-player non-zero sum games played on finite trees (i.e., sequential games), in which the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome wrt to the current strategy profile). This generates a dynamics in the game which may eventually stabilise to a Nash Equilibrium (as with Kukushkin's lazy improvement), and we argue that it is interesting to study the conditions that guarantee such a dynamics to terminate.
We build on the works of Le Roux and Pauly who have studied extensively one such dynamics, namely the Lazy Improvement Dynamics. We extend these works by first defining a turn-based dynamics, proving that it terminates on subgame perfect equilibria, and showing that several variants do not terminate. Second, we define a variant of Kukushkin's lazy improvement where the players may now form coalitions to change strategies. We show how properties of the players' preferences on the outcomes affect the termination of this dynamics, and we thereby characterise classes of games where it always terminates (in particular two-player games). |
| first_indexed | 2024-12-11T08:07:26Z |
| format | Article |
| id | doaj.art-eea095413de2401f8b26c7c06a2d14f0 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-12-11T08:07:26Z |
| publishDate | 2017-09-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-eea095413de2401f8b26c7c06a2d14f02022-12-22T01:14:57ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802017-09-01256Proc. GandALF 201713615010.4204/EPTCS.256.10:8Dynamics and Coalitions in Sequential GamesThomas Brihaye0Gilles Geeraerts1Marion Hallet2Stéphane Le Roux3 UMONS Université libre de Bruxelles UMONS Université libre de Bruxelles We consider N-player non-zero sum games played on finite trees (i.e., sequential games), in which the players have the right to repeatedly update their respective strategies (for instance, to improve the outcome wrt to the current strategy profile). This generates a dynamics in the game which may eventually stabilise to a Nash Equilibrium (as with Kukushkin's lazy improvement), and we argue that it is interesting to study the conditions that guarantee such a dynamics to terminate. We build on the works of Le Roux and Pauly who have studied extensively one such dynamics, namely the Lazy Improvement Dynamics. We extend these works by first defining a turn-based dynamics, proving that it terminates on subgame perfect equilibria, and showing that several variants do not terminate. Second, we define a variant of Kukushkin's lazy improvement where the players may now form coalitions to change strategies. We show how properties of the players' preferences on the outcomes affect the termination of this dynamics, and we thereby characterise classes of games where it always terminates (in particular two-player games).http://arxiv.org/pdf/1709.02100v1 |
| spellingShingle | Thomas Brihaye Gilles Geeraerts Marion Hallet Stéphane Le Roux Dynamics and Coalitions in Sequential Games Electronic Proceedings in Theoretical Computer Science |
| title | Dynamics and Coalitions in Sequential Games |
| title_full | Dynamics and Coalitions in Sequential Games |
| title_fullStr | Dynamics and Coalitions in Sequential Games |
| title_full_unstemmed | Dynamics and Coalitions in Sequential Games |
| title_short | Dynamics and Coalitions in Sequential Games |
| title_sort | dynamics and coalitions in sequential games |
| url | http://arxiv.org/pdf/1709.02100v1 |
| work_keys_str_mv | AT thomasbrihaye dynamicsandcoalitionsinsequentialgames AT gillesgeeraerts dynamicsandcoalitionsinsequentialgames AT marionhallet dynamicsandcoalitionsinsequentialgames AT stephaneleroux dynamicsandcoalitionsinsequentialgames |