On the structure of weakly acyclic games (Q372989): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||||||||||||||
(7 intermediate revisions by 5 users not shown) | |||||||||||||||
aliases / en / 0 | aliases / en / 0 | ||||||||||||||
On the Structure of Weakly Acyclic Games | |||||||||||||||
description / en | description / en | ||||||||||||||
scientific article | scientific article; zbMATH DE number 5802673 | ||||||||||||||
Property / title | |||||||||||||||
On the Structure of Weakly Acyclic Games (English) | |||||||||||||||
Property / title: On the Structure of Weakly Acyclic Games (English) / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Open document ID | |||||||||||||||
Property / zbMATH Open document ID: 1310.91039 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / DOI | |||||||||||||||
Property / DOI: 10.1007/978-3-642-16170-4_12 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / published in | |||||||||||||||
Property / published in: Algorithmic Game Theory / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / publication date | |||||||||||||||
19 October 2010
| |||||||||||||||
Property / publication date: 19 October 2010 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / review text | |||||||||||||||
The paper under review is to link the class of weakly acyclic games with the existence of pure Nash equilibria in its subgames. The authors prove that the uniqueness of a pure Nash equilibrium in every subgame leads to weak acyclicity of a game, and the existence of multiple pure Nash equilibria in every subgame does not imply weak acyclicity in general. In a better-response dynamics, players take turns in an arbitrary order, with each player making a better-response to the strategies of the other players, given the current strategies of the other players. Repeat this process until no player wants to switch to a different strategy, at which point we reach a pure Nash equilibrium. Weakly acyclic games are those games in which from any starting state there exists a better-response improvement path leading from the strategies profile to a pure Nash equilibrium. In the introductory section, the authors present a motivating example on a four-nodes network, which serves as a good example for the main results of the paper. The most important result states that if every subgame of a game has a unique pure Nash equilibrium then the game is weakly acyclic. Some related works are provided. Section 2 starts with precise definitions of better-response strategies (improved path), best-response strategies (improved path), pure Nash equilibrium and weakly acyclic games among others. Theorem 1 in Section 3 gives a sufficient condition for weak acyclicity with \(n\) players, that every game that has a unique pure Nash equilibrium in every subgame is weakly acyclic under best-response. \textit{T. Yamamori} and \textit{S. Takahashi} [``The pure Nash equilibrium property and the quasi-acyclic condition'', Econ. Bull. 3, No. 22, 1--6 (2002), \url{http://www.economicsbulletin.com/2002/volume3/EB-02C70011A.pdf}] showed that subgame stability in 2-player games implies weak acyclicity even under best-response, which is not true in \(3 \times 3 \times 3\) games. Theorem 2 of the paper shows that subgame stability is not sufficient for weak acyclicity even in non-strict \(2\times 2\times 2\) games. On the other hand, Theorem 3 proves that subgame stability is sufficient for weak acyclicity in any strict \(2\times 2\times M\) or \(2\times 3\times M\) game. The proof of Theorem 3 follows, with a series of lemmas and case studies. Theorem 3 is maximal, any sizes of 3-player games admit subgame-stable examples that are not weakly acyclic in Theorem 4. Theorem 5 provides insufficiency for more players to have weakly acyclic games and completes the classification of weak acyclicity under three subgame-based properties. The authors leave an important open question on finding efficient algorithms for checking unique subgame stability. It will be also interesting to know whether such an algorithm, if it exists, is in P or NP. | |||||||||||||||
Property / review text: The paper under review is to link the class of weakly acyclic games with the existence of pure Nash equilibria in its subgames. The authors prove that the uniqueness of a pure Nash equilibrium in every subgame leads to weak acyclicity of a game, and the existence of multiple pure Nash equilibria in every subgame does not imply weak acyclicity in general. In a better-response dynamics, players take turns in an arbitrary order, with each player making a better-response to the strategies of the other players, given the current strategies of the other players. Repeat this process until no player wants to switch to a different strategy, at which point we reach a pure Nash equilibrium. Weakly acyclic games are those games in which from any starting state there exists a better-response improvement path leading from the strategies profile to a pure Nash equilibrium. In the introductory section, the authors present a motivating example on a four-nodes network, which serves as a good example for the main results of the paper. The most important result states that if every subgame of a game has a unique pure Nash equilibrium then the game is weakly acyclic. Some related works are provided. Section 2 starts with precise definitions of better-response strategies (improved path), best-response strategies (improved path), pure Nash equilibrium and weakly acyclic games among others. Theorem 1 in Section 3 gives a sufficient condition for weak acyclicity with \(n\) players, that every game that has a unique pure Nash equilibrium in every subgame is weakly acyclic under best-response. \textit{T. Yamamori} and \textit{S. Takahashi} [``The pure Nash equilibrium property and the quasi-acyclic condition'', Econ. Bull. 3, No. 22, 1--6 (2002), \url{http://www.economicsbulletin.com/2002/volume3/EB-02C70011A.pdf}] showed that subgame stability in 2-player games implies weak acyclicity even under best-response, which is not true in \(3 \times 3 \times 3\) games. Theorem 2 of the paper shows that subgame stability is not sufficient for weak acyclicity even in non-strict \(2\times 2\times 2\) games. On the other hand, Theorem 3 proves that subgame stability is sufficient for weak acyclicity in any strict \(2\times 2\times M\) or \(2\times 3\times M\) game. The proof of Theorem 3 follows, with a series of lemmas and case studies. Theorem 3 is maximal, any sizes of 3-player games admit subgame-stable examples that are not weakly acyclic in Theorem 4. Theorem 5 provides insufficiency for more players to have weakly acyclic games and completes the classification of weak acyclicity under three subgame-based properties. The authors leave an important open question on finding efficient algorithms for checking unique subgame stability. It will be also interesting to know whether such an algorithm, if it exists, is in P or NP. / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 91A10 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 91A43 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / Mathematics Subject Classification ID | |||||||||||||||
Property / Mathematics Subject Classification ID: 91A22 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 6217446 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH DE Number | |||||||||||||||
Property / zbMATH DE Number: 5802673 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
weak acyclicity | |||||||||||||||
Property / zbMATH Keywords: weak acyclicity / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / zbMATH Keywords | |||||||||||||||
subgame stability | |||||||||||||||
Property / zbMATH Keywords: subgame stability / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / MaRDI profile type | |||||||||||||||
Property / MaRDI profile type: MaRDI publication profile / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W2568233966 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / OpenAlex ID | |||||||||||||||
Property / OpenAlex ID: W4210491882 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / arXiv ID | |||||||||||||||
Property / arXiv ID: 1108.2092 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Weakly-Acyclic (Internet) Routing Games / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3579412 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Learning in games by random sampling / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Improvement dynamics in games with strategic complementarities / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Q3549685 / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Payoff-Based Dynamics for Multiplayer Weakly Acyclic Games / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Congestion games with player-specific payoff functions / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Potential games / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: Dominance Solvable Voting Schemes / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: A class of games possessing pure-strategy Nash equilibria / rank | |||||||||||||||
Normal rank | |||||||||||||||
Property / cites work | |||||||||||||||
Property / cites work: The Evolution of Conventions / rank | |||||||||||||||
Normal rank | |||||||||||||||
links / mardi / name | links / mardi / name | ||||||||||||||
Latest revision as of 09:15, 3 July 2024
scientific article; zbMATH DE number 5802673
- On the Structure of Weakly Acyclic Games
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of weakly acyclic games |
scientific article; zbMATH DE number 5802673 |
|
Statements
On the structure of weakly acyclic games (English)
0 references
On the Structure of Weakly Acyclic Games (English)
0 references
21 October 2013
0 references
19 October 2010
0 references
The paper under review is to link the class of weakly acyclic games with the existence of pure Nash equilibria in its subgames. The authors prove that the uniqueness of a pure Nash equilibrium in every subgame leads to weak acyclicity of a game, and the existence of multiple pure Nash equilibria in every subgame does not imply weak acyclicity in general. In a better-response dynamics, players take turns in an arbitrary order, with each player making a better-response to the strategies of the other players, given the current strategies of the other players. Repeat this process until no player wants to switch to a different strategy, at which point we reach a pure Nash equilibrium. Weakly acyclic games are those games in which from any starting state there exists a better-response improvement path leading from the strategies profile to a pure Nash equilibrium. In the introductory section, the authors present a motivating example on a four-nodes network, which serves as a good example for the main results of the paper. The most important result states that if every subgame of a game has a unique pure Nash equilibrium then the game is weakly acyclic. Some related works are provided. Section 2 starts with precise definitions of better-response strategies (improved path), best-response strategies (improved path), pure Nash equilibrium and weakly acyclic games among others. Theorem 1 in Section 3 gives a sufficient condition for weak acyclicity with \(n\) players, that every game that has a unique pure Nash equilibrium in every subgame is weakly acyclic under best-response. \textit{T. Yamamori} and \textit{S. Takahashi} [``The pure Nash equilibrium property and the quasi-acyclic condition'', Econ. Bull. 3, No. 22, 1--6 (2002), \url{http://www.economicsbulletin.com/2002/volume3/EB-02C70011A.pdf}] showed that subgame stability in 2-player games implies weak acyclicity even under best-response, which is not true in \(3 \times 3 \times 3\) games. Theorem 2 of the paper shows that subgame stability is not sufficient for weak acyclicity even in non-strict \(2\times 2\times 2\) games. On the other hand, Theorem 3 proves that subgame stability is sufficient for weak acyclicity in any strict \(2\times 2\times M\) or \(2\times 3\times M\) game. The proof of Theorem 3 follows, with a series of lemmas and case studies. Theorem 3 is maximal, any sizes of 3-player games admit subgame-stable examples that are not weakly acyclic in Theorem 4. Theorem 5 provides insufficiency for more players to have weakly acyclic games and completes the classification of weak acyclicity under three subgame-based properties. The authors leave an important open question on finding efficient algorithms for checking unique subgame stability. It will be also interesting to know whether such an algorithm, if it exists, is in P or NP.
0 references
weak acyclicity
0 references
subgame stability
0 references