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 (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008).
| Property |
Value |
| dbo:abstract |
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 (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008). (en) |
| dbo:wikiPageExternalLink |
http://agtb.wordpress.com/2009/11/19/the-computational-complexity-of-pure-nash/ |
| dbo:wikiPageID |
26019038 (xsd:integer) |
| dbo:wikiPageLength |
31134 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1120934817 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Potential_game dbr:Facility_location_game dbr:Minimax_theorem dbr:Nash_equilibrium dbr:Strong_NP-completeness dbr:John_von_Neumann dbr:Symmetric_equilibrium dbr:Game_theory dbr:NP-complete dbr:NP-hard dbr:Congestion_game dbr:Correlated_equilibrium dbr:Epsilon-equilibrium dbr:Computational_problem dbr:Zero-sum_game dbr:PLS_(complexity) dbr:P_(complexity) dbr:Strategy_(game_theory) dbc:Game_theory_game_classes dbr:Time_complexity dbr:Treewidth dbr:Game_without_a_value dbr:EXPTIME dbr:Normal-form_game dbr:PSPACE dbr:Reduction_(complexity) dbr:AC0 dbr:Zero-sum dbr:Boolean_circuit dbr:Polynomial-time_approximation_scheme dbr:Polynomial_hierarchy dbr:Graphical_game_(game_theory) dbr:Turing_machine dbr:Indegree dbr:Symmetric_game dbr:PPAD_(complexity) dbr:Polymatrix_game dbr:Action-graph_game dbr:Anonymous_game dbr:Circuit_game dbr:Hypergraphical_game dbr:Local_effect_game dbr:Network_congestion_game dbr:Scheduling_game dbr:Sparse_game |
| dbp:wikiPageUsesTemplate |
dbt:Anchor dbt:Clear dbt:Fontcolor dbt:Reflist dbt:See_also dbt:Game_theory |
| dcterms:subject |
dbc:Game_theory_game_classes |
| rdf:type |
owl:Thing |
| rdfs:comment |
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 (a formal definition, describing succinct games as a computational problem, is given by Papadimitriou & Roughgarden 2008). (en) |
| rdfs:label |
Succinct game (en) |
| rdfs:seeAlso |
dbr:Game_theory |
| owl:sameAs |
freebase:Succinct game yago-res:Succinct game wikidata:Succinct game https://global.dbpedia.org/id/4vCJK |
| prov:wasDerivedFrom |
wikipedia-en:Succinct_game?oldid=1120934817&ns=0 |
| foaf:isPrimaryTopicOf |
wikipedia-en:Succinct_game |
| is dbo:wikiPageDisambiguates of |
dbr:Succinct_(disambiguation) |
| is dbo:wikiPageRedirects of |
dbr:Polymatrix_game dbr:Succinctly_representable_game |
| is dbo:wikiPageWikiLink of |
dbr:Concision dbr:Succinct_(disambiguation) dbr:Game_Description_Language dbr:Graphical_game_theory dbr:Polymatrix_game dbr:Succinctly_representable_game |
| is rdfs:seeAlso of |
dbr:Game_theory |
| is foaf:primaryTopic of |
wikipedia-en:Succinct_game |