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.
L R
T 9 8
B 3 4
l r
L 6 8
R 1 3
T B
l 4 4
r 5 7

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.
#TP=2
#BP=0
#TP=1
#BP=1
#TP=0
#BP=2
T 5 2 2
B 1 7 2

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.
#TP=2
#BP=0
#TP=1
#BP=1
#TP=0
#BP=2
T 8, 8, 2 2, 9, 5 4, 1, 4
B 6, 1, 3 2, 2, 1 7, 0, 6

In anonymous games, players have different utilities but do not distinguish between other players (for instance, having to choose between "go to cinema" and "go to bar" while caring only how crowded will each place be, not who'll they meet there). In such a game a player's utility again depends on how many of his peers choose which strategy, and his own, so utility values are required.

If the number of actions grows with the number of players, finding a pure Nash equilibrium in an anonymous game is NP-hard.[8] An optimal correlated equilibrium of an anonymous game may be found in polynomial time.[2] When the number of strategies is 2, there is a known PTAS for finding an ε-approximate Nash equilibrium.[10]

Polymatrix games

If the game in question was a polymatrix game, describing it would require 24 utility values. For simplicity, let us examine only the utilities of player I (we would need two more such tables for each of the other players).
L R
T 4, 6 8, 7
B 3, 7 9, 1
l r
T 7, 7 1, 6
B 8, 6 6, 4
l r
L 2, 9 3, 3
R 2, 4 1, 5

If strategy profile (B,R,l) was chosen, player I's utility would be 9+8=17, player II's utility would be 1+2=3, and player III's utility would be 6+4=10.

In a polymatrix game (also known as a multimatrix game), there is a utility matrix for every pair of players (i,j), denoting a component of player i's utility. Player i's final utility is the sum of all such components. The number of utilities values required to represent such a game is .

Polymatrix games always have at least one mixed Nash equilibrium.[11] The problem of finding a Nash equilibrium in a polymatrix game is PPAD-complete.[5] Moreover, the problem of finding a constant approximate Nash equilibrium in a polymatrix game is also PPAD-complete.[12] Finding a correlated equilibrium of a polymatrix game can be done in polynomial time.[2] Note that even if pairwise games played between players have pure Nash equilibria, the global interaction does not necessarily admit a pure Nash equilibrium (although a mixed Nash equilibrium must exist). Checking if a pure Nash equilibrium exists is a strongly NP-complete problem.[13]

Competitive polymatrix games with only zero-sum interactions between players are a generalization of two-player zero-sum games. The Minimax theorem originally formulated for two-player games by von Neumann generalizes to zero-sum polymatrix games.[14] Same as two-player zero-sum games, polymatrix zero-sum games have mixed Nash equilibria that can be computed in polynomial time and those equilibria coincide with correlated equilibria. But some other properties of two-player zero-sum games do not generalize. Notably, players need not have a unique value of the game and equilibrium strategies are not max-min strategies in a sense that worst-case payoffs of players are not maximized when using an equilibrium strategy. There exists an open source Python library[15] for simulating competitive polymatrix games.

Polymatrix games which have coordination games on their edges are potential games [16] and can be solved using a potential function method.

Circuit games

Let us now equate the players' various strategies with the Boolean values "0" and "1", and let X stand for player I's choice, Y for player II's choice and Z for player III's choice. Let us assign each player a circuit:

Player I: X ∧ (Y ∨ Z)
Player II: X ⊕ Y ⊕ Z
Player III: X ∨ Y

These describe the utility table below.

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

The most flexible of way of representing a succinct game is by representing each player by a polynomial-time bounded Turing machine, which takes as its input the actions of all players and outputs the player's utility. Such a Turing machine is equivalent to a Boolean circuit, and it is this representation, known as circuit games, that we will consider.

Computing the value of a 2-player zero-sum circuit game is an EXP-complete problem,[17] and approximating the value of such a game up to a multiplicative factor is known to be in PSPACE.[18] Determining whether a pure Nash equilibrium exists is a -complete problem (see Polynomial hierarchy).[19]

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 strongly NP-complete PPAD-complete (polynomial for zero-sum polymatrix) P NP-hard
Circuit game -complete
Congestion game PLS-complete P NP-hard


Notes

  1. ^ 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.
  2. ^ 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. S2CID 53224027.
  3. ^ 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.
  4. ^ 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.
  5. ^ 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. Vol. 4051. pp. 513–524. CiteSeerX 10.1.1.111.8075. doi:10.1007/11786986_45. ISBN 978-3-540-35904-3.
  6. ^ 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.
  7. ^ 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.
  8. ^ 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.
  9. ^ 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.
  10. ^ Daskalakis, Constantinos; Papadimitriou, Christos H. (2007). "Computing Equilibria in Anonymous Games". arXiv:0710.5582v1 [cs].
  11. ^ 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.
  12. ^ 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. S2CID 14633920.
  13. ^ Apt, Krzysztof; Simon, Sunil; Wojtczak, Dominik (4 October 2021). "Coordination Games on Weighted Directed Graphs". Mathematics of Operations Research. 47 (2): 995–1025. arXiv:1910.02693. doi:10.1287/moor.2021.1159. S2CID 203836087.
  14. ^ Cai, Y., Candogan, O., Daskalakis, C., & Papadimitriou, C. (2016). Zero-sum Polymatrix Games: A generalization of Minimax.https://people.csail.mit.edu/costis/zerosum_final3.pdf
  15. ^ O. Person https://pypi.org/project/polymatrix/
  16. ^ Rahn, Mona and Schafer, Guido (2015) Efficient Equilibria in Polymatrix Coordination Games https://arxiv.org/pdf/1504.07518.pdf
  17. ^ 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.
  18. ^ 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.
  19. ^ 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.

Read other articles:

Untuk operator PLTA Gezhouba, lihat China Yangtze Power. China Gezhouba Group Company LimitedNama asli中国葛洲坝集团股份有限公司Kode emitenSSE: 600068IndustriPLTA, konstruksi transmisi listrik, konstruksi transportasi, pengembangan lahan nyataDidirikan23 Januari 2006KantorpusatWuhan, Hubei, TiongkokWilayah operasiSeluruh duniaPendapatan CN¥ 71.605 miliar (2014)[1]Laba bersih CN¥ 2.287 miliar (2014)[1]Total aset CN¥ 104.900 miliar (2014)[1]...

 

 

See also: List of tallest buildings in Europe and List of tallest structures in Europe This list ranks the tallest buildings in the European Union that stand at least 150 metres (492 ft) tall, based on standard height measurement. This means that spires and other architectural details are included in the official height, but not antenna masts, as it is defined by the Council on Tall Buildings and Urban Habitat. Only habitable buildings are ranked, which excludes radio masts and towers, ...

 

 

For the rural locality, see Solonchak, Astrakhan Oblast. Solonchak ground Devil's Golf Course, Death Valley National Park, United States Solonchak (Russian and Ukrainian: Солончак) is a Reference Soil Group of the World Reference Base for Soil Resources (WRB). It is a pale or grey soil type found in arid to subhumid poorly-drained conditions. The word is Russian for salt marsh, which is in turn from the Russian sol (соль) salt. The Ukrainian folk word солончак, which in tu...

Region of the North Atlantic Ocean Not to be confused with Saragossa. For other uses, see Sargasso Sea (disambiguation). Map of the Sargasso Sea The Sargasso Sea in the North Atlantic is bounded by the Gulf Stream on the west, the North Atlantic Current on the north, the Canary Current on the east, and the North Equatorial Current on the south. The Sargasso Sea (/sɑːrˈɡæsoʊ/) is a region of the Atlantic Ocean bounded by four currents forming an ocean gyre.[1] Unlike all other re...

 

 

Маги́ческий, или волше́бный квадра́т — квадратная таблица n × n {\displaystyle n\times n} , заполненная n 2 {\displaystyle n^{2}} различными числами таким образом, что сумма чисел в каждой строке, каждом столбце и на обеих диагоналях одинакова. Если в квадрате равны суммы чисел только в ст�...

 

 

Part of a series onEthnicity in Philadelphia African Americans Cubans Hispanics and Latinos Irish Indians Italians Jews Native Americans Puerto Ricans vte Jews in Philadelphia can trace their history back to Colonial America. Jews have lived in Philadelphia since the arrival of William Penn in 1682. Colonial History Jewish traders have operated in southeastern Pennsylvania since at least the 1650s.[1] The first Jewish resident of the city on record was Jonas Aaron whose name appears ...

У этого термина существуют и другие значения, см. Воблер (значения). Воблеры Воблер (англ. wobbler) — твердотелая объёмная приманка для ловли рыбы троллингом, «дорожкой» или спиннингом. В переводе с английского wobbler — тот, кто шатается, вихляется. При использовании воб...

 

 

Railway station in Xiamen, China Xiamen厦门Southern entry of Xiamen railway stationGeneral informationLocationZhanqian Lu, Siming District, Xiamen, FujianChinaCoordinates24°28′14″N 118°06′41″E / 24.4705°N 118.1113°E / 24.4705; 118.1113Operated byNanchang Railway Bureau, China Railway CorporationLine(s)Yingxia RailwayPlatforms5Connections Bus terminal Other informationStation code TMIS code: 34583 Telegraph code: XMS Pinyin code: XME HistoryOpenedApril...

 

 

Questa voce o sezione sull'argomento fisica non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Un McDonnell Douglas F/A-18 Super Hornet della United States Navy in volo transonico. Un problema di fluidodinamica o aerodinamica viene detto in regime supersonico se le velocità caratteristiche del campo di moto...

Риччи Себастьяно. Картина «Тарквиний Древний вопрошает авгура Аттия Навия» (около 1690 года). Музей Гетти Ауспи́ции[1] (лат. auspicia, от avis — «птица» и speculare — «наблюдать»), Птицегада́ние — в узком смысле — гадание авгуров по поведению птиц, откуда и происходит...

 

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (May 2017) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by ...

 

 

艾德礼伯爵 阁下The Rt Hon. The Earl AttleeKG OM CH PC FRS联合王国首相任期1945年7月26日—1951年10月26日君主乔治六世副职赫伯特·莫里森前任温斯顿·丘吉尔继任温斯顿·丘吉尔联合王国副首相任期1942年2月19日—1945年5月23日(战时内阁)君主乔治六世首相温斯顿·丘吉尔前任职位创立继任赫伯特·莫里森反对党领袖任期1951年10月26日—1955年11月25日君主乔治六世伊丽莎白二�...

American economist (1847–1938) John Bates ClarkBorn(1847-01-26)January 26, 1847Providence, Rhode Island, USDiedMarch 21, 1938(1938-03-21) (aged 91)New York City, USAcademic careerInstitutionCarleton CollegeJohns Hopkins UniversityColumbia UniversitySchool ortraditionNeoclassical economicsAlma materAmherst CollegeDoctoraladvisorKarl KniesDoctoralstudentsHenry MooreAlvin Saunders JohnsonInfluencesKarl Knies Signature John Bates Clark (January 26, 1847 – March 21, 1938) was an...

 

 

Neighborhood of the Bronx in New York CityWestchester SquareNeighborhood of the BronxThe front door to the historic Huntington Free Library on Lane AvenueLocation in New York CityCoordinates: 40°50′35″N 73°50′35″W / 40.843°N 73.843°W / 40.843; -73.843Country United StatesState New YorkCity New York CityBorough The BronxCommunity DistrictBronx 10[1]EconomicsZIP Codes10461, 10462Area code718, 347, 929, and 917Websitewww.westchestersquare.nyc...

 

 

American poker player (born 1966) James Van AlstyneVan Alstyne in the 2007 World Series of PokerResidenceLas Vegas, Nevada, U.S.Born1966 (age 57–58)Columbus, Georgia, U.S.World Series of PokerBracelet(s)1Money finish(es)13Highest ITMMain Event finish16th, 1999World Poker TourTitle(s)NoneFinal table(s)2Money finish(es)10Information accurate as of February 23, 2010. James Gibson Van Alstyne (born 1966 in Columbus, Georgia) is an American professional poker player based in Las Vegas, ...

1871 Paris Commune elections ← 1870 March 26, 1871 (1871-03-26) 1871 → Registered484,569Turnout48% The Paris Commune of 1871 was established on March 26, 1871, following elections held by the Central Committee of the National Guard [fr]. This revolutionary government was inspired by the earlier Paris Commune of 1792 and realized the aspirations of the social movement. The Commune saw the formation of an assembly representing all republican fac...

 

 

Gandharan founder of Dzogchen tradition An illustration of Garab Dorje Garab Dorje (c. 665) (Tibetan: དགའ་རབ་རྡོ་རྗེ་, Wylie: dga’ rab rdo rje)[1] was the first human to receive the complete direct transmission teachings of Sutra, Tantra and Dzogchen. The circumstances of his birth are shrouded in different interpretations, with some accounts describing a miraculous birth by a virgin daughter of the king of Uddiyana. Garab Dorje became the first teacher...

 

 

В Википедии есть статьи о других людях с фамилией Кирай. Карч Кирайангл. Charles Frederick Karch Kiraly Общая информация Полное имя Чарльз Фредерик Кирай Родился 3 ноября 1960(1960-11-03) (63 года)Джэксон, штат Мичиган, США Гражданство  США Рост 190 Вес 86 Позиция доигровщик Информация о кома�...

Russian mathematician Not to be confused with Alexander Ostrovsky. Alexander OstrowskiBorn(1893-09-25)25 September 1893Kiev, Kiev Governorate, Russian EmpireDied20 November 1986(1986-11-20) (aged 93)Montagnola, Lugano, SwitzerlandScientific careerThesis Ueber Dirichletsche Reihen und algebraische Differentialgleichungen  (1920)Doctoral advisorEdmund LandauFelix KleinOther academic advisorsDmitry GraveKurt HenselDoctoral studentsTheodore MotzkinWalter GautschiStefan E. Warschaws...

 

 

الحديقة العامة {{{تعليق_بديل}}}المدخل الرئيسي للحديقة العامة تاريخ الافتتاح 1949 الموقع حي محطة بغداد، حلب،  سوريا البلد سوريا  الإحداثيات 36°12′35″N 37°08′50″E / 36.20972°N 37.14722°E / 36.20972; 37.14722 مساحة الأرض 17 هكتاراً المالك مجلس مدينة حلب تعديل مصدري - تعديل   تعدّ «ا�...