Succinct game
Consider a game of three players, I,II and III, facing, respectively, the strategies {T,B}, {L,R}, and {l,r}. Without further constraints, 3*23=24 utility values would be required to describe such a game. | ||||
L, l | L, r | R, l | R, r | |
---|---|---|---|---|
T | 4, 6, 2 | 5, 5, 5 | 8, 1, 7 | 1, 4, 9 |
B | 8, 6, 6 | 7, 4, 7 | 9, 6, 5 | 0, 3, 0 |
For each strategy profile, the utility of the first player is listed first (red), and is followed by the utilities of the second player (green) and the third player (blue). |
In algorithmic game theory, a succinct game or a succinctly representable game is a game which may be represented in a size much smaller than its normal form representation. Without placing constraints on player utilities, describing a game of players, each facing strategies, requires listing utility values. Even trivial algorithms are capable of finding a Nash equilibrium in a time polynomial in the length of such a large input. A succinct game is of polynomial type if in a game represented by a string of length n the number of players, as well as the number of strategies of each player, is bounded by a polynomial in n[1] (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008[2]).
Types of succinct games
Graphical games
Say that each player's utility depends only on his own action and the action of one other player - for instance, I depends on II, II on III and III on I. Representing such a game would require only three 2x2 utility tables, containing in all only 12 utility values.
|
Graphical games are games in which the utilities of each player depends on the actions of very few other players. If is the greatest number of players by whose actions any single player is affected (that is, it is the indegree of the game graph), the number of utility values needed to describe the game is , which, for a small is a considerable improvement.
It has been shown that any normal form game is reducible to a graphical game with all degrees bounded by three and with two strategies for each player.[3] Unlike normal form games, the problem of finding a pure Nash equilibrium in graphical games (if one exists) is NP-complete.[4] The problem of finding a (possibly mixed) Nash equilibrium in a graphical game is PPAD-complete.[5] Finding a correlated equilibrium of a graphical game can be done in polynomial time, and for a graph with a bounded treewidth, this is also true for finding an optimal correlated equilibrium.[2]
Sparse games
When most of the utilities are 0, as below, it is easy to come up with a succinct representation. | ||||
L, l | L, r | R, l | R, r | |
---|---|---|---|---|
T | 0, 0, 0 | 2, 0, 1 | 0, 0, 0 | 0, 7, 0 |
B | 0, 0, 0 | 0, 0, 0 | 2, 0, 3 | 0, 0, 0 |
Sparse games are those where most of the utilities are zero. Graphical games may be seen as a special case of sparse games.
For a two player game, a sparse game may be defined as a game in which each row and column of the two payoff (utility) matrices has at most a constant number of non-zero entries. It has been shown that finding a Nash equilibrium in such a sparse game is PPAD-hard, and that there does not exist a fully polynomial-time approximation scheme unless PPAD is in P.[6]
Symmetric games
Suppose all three players are identical (we'll color them all purple), and face the strategy set {T,B}. Let #TP and #BP be the number of a player's peers who've chosen T and B, respectively. Describing this game requires only 6 utility values.
|
In symmetric games all players are identical, so in evaluating the utility of a combination of strategies, all that matters is how many of the players play each of the strategies. Thus, describing such a game requires giving only utility values.
In a symmetric game with 2 strategies there always exists a pure Nash equilibrium – although a symmetric pure Nash equilibrium may not exist.[7] The problem of finding a pure Nash equilibrium in a symmetric game (with possibly more than two players) with a constant number of actions is in AC0; however, when the number of actions grows with the number of players (even linearly) the problem is NP-complete.[8] In any symmetric game there exists a symmetric equilibrium. Given a symmetric game of n players facing k strategies, a symmetric equilibrium may be found in polynomial time if k=.[9] Finding a correlated equilibrium in symmetric games may be done in polynomial time.[2]
Anonymous games
If players were different but did not distinguish between other players we would need to list 18 utility values to represent the game - one table such as that given for "symmetric games" above for each player.
|
익명 게임에서 플레이어는 유틸리티는 다르지만 다른 플레이어를 구분하지 않는다(예를 들어, 각 장소가 얼마나 붐빌지, 누가 거기서 만날지 아닌, 단지 얼마나 붐빌지 신경 쓰면서 "시네마 가기"와 "바 가기" 중 하나를 선택해야 한다). 이러한 게임에서 플레이어의 유틸리티는 또래 선수 중 몇 명이 어떤 전략을 선택하고 자신의 전략을 선택하느냐에 따라 달라지기 때문에 n( - s - 의 유틸리티 값이 필요하다.
선수 수에 따라 행동 횟수가 늘어나면 익명 게임에서 순수한 내시 평형을 찾는 것은 NP-하드다.[8] 익명 게임의 최적의 상관관계 평형은 다항식 시간에 찾을 수 있다.[2] 전략의 수가 2일 때, ε 근사치 나시 평형을 찾는 것으로 알려진 PTAS가 있다.[10]
폴리매트릭스 게임
문제가 된 게임이 폴리매트릭스 게임이라면 24개의 효용 값이 필요할 것이라고 기술했다. 단순성을 위해 플레이어 I의 유틸리티(다른 플레이어 각각에 대해 그러한 테이블이 두 개 더 필요함)만 검토해보자.
전략 프로파일(B,R,l)을 선택하면 플레이어 I의 효용성은 9+8=17, 플레이어 II의 효용성은 1+2=3, 플레이어 III의 효용성은 6+4=10이 된다. |
폴리매트릭스 게임(일명 멀티매트릭스 게임)에는 모든 플레이어(i,j)를 위한 유틸리티 매트릭스가 있어 플레이어 i의 유틸리티의 구성요소를 나타낸다. 플레이어 1의 최종 효용성은 그러한 모든 구성요소의 합이다. 이러한 게임을 나타내기 위해 필요한 유틸리티 값의 수는 2 입니다
폴리매트릭스 게임은 항상 적어도 하나의 혼합된 내쉬 평형을 가지고 있다.[11] 폴리매트릭스 게임에서 나시 평형을 찾는 문제는 PPAD 완성이다.[5] 게다가 폴리매트릭스 게임에서 일정한 근사치 나시 평형을 찾는 문제도 PPAD-완전하다.[12] 폴리매트릭스 게임의 상관관계를 찾는 것은 다항식 시간에 이루어질 수 있다.[2] 선수들 간에 행해지는 페어웨이즈 게임이 순수한 내시 평형을 가지고 있다고 해도, 글로벌 상호작용은 반드시 순수한 내시 평형을 인정하는 것은 아니라는 점에 유의한다(혼합된 내시 평형이 존재해야 함).
선수 간 제로섬 상호 작용만 하는 경쟁적인 폴리매트릭스 게임은 2인 제로섬 게임의 일반화다. 원래 폰 노이만이 2인용 게임을 위해 공식화한 미니맥스 정리는 제로섬 폴리매트릭스 게임에 일반화된다.[13] 2인용 제로섬 게임과 마찬가지로 폴리매트릭스 제로섬 게임도 다항식 시간에 계산할 수 있는 내시 평형(Nash 평형)이 혼합돼 있고 그 평형(평형)은 상관식 평형(Correlibria)과 일치한다. 그러나 2인용 제로섬 게임의 다른 특성들은 일반화되지 않는다. 특히 플레이어가 특유의 경기 가치를 가질 필요는 없고, 평형 전략을 구사할 때 플레이어의 최악의 보상이 극대화되지 않는다는 점에서 평형 전략이 최대민 전략이 아니다. 경쟁적인 폴리매트릭스 게임을 시뮬레이션할 수 있는 오픈 소스 파이썬 라이브러리가[14] 있다.
가장자리에 코디네이션 게임이 있는 폴리매트릭스 게임은 잠재적 게임이며 잠재적인 기능 방법을 사용하여 해결할 수 있다.
서킷 게임
이제 선수들의 다양한 전략을 부울 값 "0"과 "1"과 동일시하고, X는 I's choice, Y는 II's choice, Z는 III's choice를 나타내자. 각 플레이어에 회로를 할당합시다. 플레이어 I: X ∧ (Y ∨ Z) 아래 유틸리티 표에 대해 설명하십시오. | ||||
0, 0 | 0, 1 | 1, 0 | 1, 1 | |
---|---|---|---|---|
0 | 0, 0, 0 | 0, 1, 0 | 0, 1, 1 | 0, 0, 1 |
1 | 0, 1, 1 | 1, 0, 1 | 1, 0, 1 | 1, 1, 1 |
간결한 게임을 표현하는 가장 유연한 방법은 다항 시간 경계 튜링 기계로 각 플레이어를 표현하는 것인데, 이 기계는 모든 플레이어의 동작을 입력으로 받아들이고 플레이어의 효용을 출력한다. 그러한 튜링 기계는 부울 회로에 해당하며, 우리가 고려할 것은 회로 게임이라고 알려진 이 표현이다.
Computing the value of a 2-player zero-sum circuit game is an EXP-complete problem,[16] and approximating the value of such a game up to a multiplicative factor is known to be in PSPACE.[17] Determining whether a pure Nash equilibrium exists is a -complete problem (see Polynomial hierarchy).[18]
Other representations
Many other types of succinct game exist (many having to do with allocation of resources). Examples include congestion games, network congestion games, scheduling games, local effect games, facility location games, action-graph games, hypergraphical games and more.
Summary of complexities of finding equilibria
Below is a table of some known complexity results for finding certain classes of equilibria in several game representations. "NE" stands for "Nash equilibrium", and "CE" for "correlated equilibrium". n is the number of players and s is the number of strategies each player faces (we're assuming all players face the same number of strategies). In graphical games, d is the maximum indegree of the game graph. For references, see main article text.
Representation | Size (O(...)) | Pure NE | Mixed NE | CE | Optimal CE |
---|---|---|---|---|---|
Normal form game | NP-complete | PPAD-complete | P | P | |
Graphical game | NP-complete | PPAD-complete | P | NP-hard | |
Symmetric game | NP-complete | The computation of symmetric Nash equilibrium is PPAD-hard for two players. The computation of non-symmetric Nash equilibrium for two players is NP-complete. | P | P | |
Anonymous game | NP-hard | P | P | ||
Polymatrix game | PPAD-complete (polynomial for zero-sum polymatrix) | P | NP-hard | ||
Circuit game | -complete | ||||
혼잡 게임 | PLS 완료 | P | NP-하드 |
메모들
- ^ Papadimitriou, Christos H. (2007). "The Complexity of Finding Nash Equilibria". In Nisan, Noam; Roughgarden, Tim; Tardos, Éva; et al. (eds.). Algorithmic Game Theory. Cambridge University Press. pp. 29–52. ISBN 978-0-521-87282-9.
- ^ a b c d e Papadimitriou, Christos H.; Roughgarden, Tim (2008). "Computing Correlated Equilibria in Multi-Player Games". J. ACM. 55 (3): 1–29. CiteSeerX 10.1.1.335.2634. doi:10.1145/1379759.1379762.
- ^ Goldberg, Paul W.; Papadimitriou, Christos H. (2006). "Reducibility Among Equilibrium Problems". Proceedings of the thirty-eighth annual ACM symposium on Theory of computing. Seattle, WA, USA: ACM. pp. 61–70. doi:10.1145/1132516.1132526. ISBN 1-59593-134-1. Retrieved 2010-01-25.
- ^ Gottlob, G.; Greco, G.; Scarcello, F. (2005). "Pure Nash Equilibria: Hard and Easy Games". Journal of Artificial Intelligence Research. 24 (195–220): 26–37. arXiv:1109.2152. doi:10.1613/jair.1683.
- ^ a b Daskalakis, Constantinos; Fabrikant, Alex; Papadimitriou, Christos H. (2006). "The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games". Automata, Languages and Programming. Lecture Notes in Computer Science. 4051. pp. 513–524. CiteSeerX 10.1.1.111.8075. doi:10.1007/11786986_45. ISBN 978-3-540-35904-3.
- ^ Chen, Xi; Deng, Xiaotie; Teng, Shang-Hua (2006). "Sparse Games Are Hard". Internet and Network Economics. pp. 262–273. doi:10.1007/11944874_24. ISBN 978-3-540-68138-0.
- ^ Cheng, Shih-Fen; Reeves, Daniel M.; Vorobeychik, Yevgeniy; Wellman, Michael P. (2004). Notes on Equilibria in Symmetric Games. AAMAS-04 Workshop on Game Theory and Decision Theory.
- ^ a b Brandt, Felix; Fischer, Felix; Holzer, Markus (2009). "Symmetries and the Complexity of Pure Nash Equilibrium". J. Comput. Syst. Sci. 75 (3): 163–177. doi:10.1016/j.jcss.2008.09.001. Retrieved 2010-01-31.
- ^ Papadimitriou, Christos H.; Roughgarden, Tim (2005). "Computing equilibria in multi-player games". Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Vancouver, British Columbia: Society for Industrial and Applied Mathematics. pp. 82–91. ISBN 0-89871-585-7. Retrieved 2010-01-25.
- ^ Daskalakis, Constantinos; Papadimitriou, Christos H. (2007). "Computing Equilibria in Anonymous Games". arXiv:0710.5582v1 [cs].
- ^ Howson, Joseph T. (January 1972). "Equilibria of Polymatrix Games". Management Science. 18 (5): 312–318. doi:10.1287/mnsc.18.5.312. ISSN 0025-1909. JSTOR 2634798.
- ^ Rubinstein, Aviad (2015-01-01). Inapproximability of Nash Equilibrium. Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing. STOC '15. New York, NY, USA: ACM. pp. 409–418. arXiv:1405.3322. doi:10.1145/2746539.2746578. ISBN 9781450335362.
- ^ Cai, Y, Candogan, O, Daskalakis, C, & Papadimitriou, C. (2016) 제로섬 폴리매트릭스 게임: Minimax.https://people.csail.mit.edu/costis/zerosum_final3.pdf의 일반화
- ^ O. Person https://pypi.org/project/polymatrix/
- ^ Ran, Mona, Schafer, Guido(2015) Polymatrix Coordination Games의 Efficient Equilibria https://arxiv.org/pdf/1504.07518.pdf
- ^ Feigenbaum, Joan; Koller, Daphne; Shor, Peter (1995). A Game-Theoretic Classification of Interactive Complexity Classes. Certer for Discrete Mathematics \& Theoretical Computer Science. Retrieved 2010-01-25.
- ^ Fortnow, Lance; Impagliazzo, Russell; Kabanets, Valentine; Umans, Christopher (2005). "On the Complexity of Succinct Zero-Sum Games". Proceedings of the 20th Annual IEEE Conference on Computational Complexity. IEEE Computer Society. pp. 323–332. ISBN 0-7695-2364-1. Retrieved 2010-01-23.
- ^ Schoenebeck, Grant; Vadhan, Salil (2006). "The computational complexity of nash equilibria in concisely represented games". Proceedings of the 7th ACM conference on Electronic commerce. Ann Arbor, Michigan, USA: ACM. pp. 270–279. doi:10.1145/1134707.1134737. ISBN 1-59593-236-4. Retrieved 2010-01-25.