Editing Game theory (section)

==Representation of games==

The games studied in game theory are well-defined mathematical objects. To be fully defined, a game must specify the following elements: the ''players'' of the game, the ''information'' and ''actions'' available to each player at each decision point, and the [[Utility|''payoffs'']] for each outcome. (Eric Rasmusen refers to these four "essential elements" by the acronym "PAPI".)<ref name="r7a"/><ref name="r7b"/><ref name="r7c"/><ref name="r7d"/> A game theorist typically uses these elements, along with a [[solution concept]] of their choosing, to deduce a set of equilibrium [[Strategy (game theory)|strategies]] for each player such that, when these strategies are employed, no player can profit by unilaterally deviating from their strategy. These equilibrium strategies determine an [[Economic equilibrium|equilibrium]] to the game—a stable state in which either one outcome occurs or a set of outcomes occur with known probability.

Most cooperative games are presented in the characteristic function form, while the extensive and the normal forms are used to define noncooperative games.

===Extensive form===
{{main|Extensive form game}}
[[File:Ultimatum Game Extensive Form.svg|thumb|right|An extensive form game]]
The extensive form can be used to formalize games with a time sequencing of moves. Extensive form games can be visualized using game [[Tree (graph theory)|trees]] (as pictured here). Here each [[Graph (discrete mathematics)|vertex]] (or node) represents a point of choice for a player. The player is specified by a number listed by the vertex. The lines out of the vertex represent a possible action for that player. The payoffs are specified at the bottom of the tree. The extensive form can be viewed as a multi-player generalization of a [[decision tree]].<ref>{{cite book |last1=Fudenberg |first1=Drew |last2=Tirole |first2=Jean |title=Game Theory |date=1991 |publisher=MIT Press |isbn=978-0-262-06141-4 |page=67 }}</ref> To solve any extensive form game, [[backward induction]] must be used. It involves working backward up the game tree to determine what a rational player would do at the last vertex of the tree, what the player with the previous move would do given that the player with the last move is rational, and so on until the first vertex of the tree is reached.<ref>{{Cite book |title=Security Studies: an Introduction |last=Williams |first=Paul D. |publisher=Routledge |year=2013 |location=[[Abingdon-on-Thames|Abingdon]] |pages=55–56 |edition=second}}</ref>

The game pictured consists of two players.  The way this particular game is structured (i.e., with sequential decision making and perfect information), ''Player 1'' "moves" first by choosing either {{var|F}} or {{var|U}} (fair or unfair). Next in the sequence, ''Player 2'', who has now observed ''Player 1''{{'}}s move, can choose to play either {{var|A}} or {{var|R}}  (accept or reject). Once ''Player 2'' has made their choice, the game is considered finished and each player gets their respective payoff, represented in the image as two numbers, where the first number represents Player 1's payoff, and the second number represents Player 2's payoff.  Suppose that ''Player 1'' chooses {{var|U}} and then ''Player 2'' chooses {{var|A}}: ''Player 1'' then gets a payoff of "eight" (which in real-world terms can be interpreted in many ways, the simplest of which is in terms of money but could mean things such as eight days of vacation or eight countries conquered or even eight more opportunities to play the same game against other players) and ''Player 2'' gets a payoff of "two".

The extensive form can also capture simultaneous-move games and games with imperfect information. To represent it, either a dotted line connects different vertices to represent them as being part of the same information set (i.e. the players do not know at which point they are), or a closed line is drawn around them. (See example in the [[#Perfect information and imperfect information|imperfect information section]].)

===Normal form===
<!----- {| align=right border="1" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 1em; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align=bottom |''A normal form game''
|-
|
! scope="col" style="color: #900;width: 90px;" | ''Player 2 chooses left''
! scope="col" style="color: #900;width: 90px;" | ''Player 2 chooses right''
|-
! scope="col" style="color: #009;width: 90px;" | ''Player 1 chooses top''
| align=center | <span style="color: #009">4</span>, <span style="color: #900">3</span>
| align=center | <span style="color: #009">-1</span>, <span style="color: #900">-1</span>
|-
! scope="col" style="color: #009;width: 100px;" | ''Player 1 chooses bottom''
| align=center | <span style="color: #009">0</span>, <span style="color: #900">0</span>
| align=center | <span style="color: #009">3</span>, <span style="color: #900">4</span>
|} ----->
{{Payoff matrix |Float=right |Width=330
| Name = Normal form or payoff matrix of a 2-player, 2-strategy game
| 2L = {{color|#900|Player 2<br />chooses ''Left''}}
| 2R = {{color|#900|Player 2<br />chooses ''Right''}}
| 1U = {{color|#009|Player 1<br />chooses ''Up''}}
| 1D = {{color|#009|Player 1<br />chooses&nbsp;''Down''}}
| UL = {{color|#009|'''4'''}}, {{color|#900|'''3'''}}
| UR = {{color|#009|'''–1'''}}, {{color|#900|'''–1'''}}
| DL = {{color|#009|'''0'''}}, {{color|#900|'''0'''}}
| DR = {{color|#009|'''3'''}}, {{color|#900|'''4'''}}
}}
{{main|Normal-form game}}
The normal (or strategic form) game is usually represented by a [[Matrix (mathematics)|matrix]] which shows the players, strategies, and payoffs (see the example to the right). More generally it can be represented by any function that associates a payoff for each player with every possible combination of actions. In the accompanying example there are two players; one chooses the row and the other chooses the column. Each player has two strategies, which are specified by the number of rows and the number of columns. The payoffs are provided in the interior. The first number is the payoff received by the row player (Player 1 in our example); the second is the payoff for the column player (Player 2 in our example). Suppose that Player 1 plays ''Up'' and that Player 2 plays ''Left''. Then Player 1 gets a payoff of 4, and Player 2 gets 3.

When a game is presented in normal form, it is presumed that each player acts simultaneously or, at least, without knowing the actions of the other. If players have some information about the choices of other players, the game is usually presented in extensive form.

Every extensive-form game has an equivalent normal-form game, however, the transformation to normal form may result in an exponential blowup in the size of the representation, making it computationally impractical.{{sfnp|Shoham|Leyton-Brown|2008|p=35}}

===Characteristic function form===
{{main|Cooperative game theory}}
In cooperative game theory the characteristic function lists the payoff of each coalition. The origin of this formulation is in John von Neumann and Oskar Morgenstern's book.<ref>{{Cite web |date=2025-02-12 |title=Game theory - Von Neumann, Morgenstern, Theory {{!}} Britannica |url=https://www.britannica.com/science/game-theory/The-von-Neumann-Morgenstern-theory |access-date=2025-03-19 |website=Britannica |language=en}}</ref>

Formally, a characteristic function is a function <math> v : 2^N \to \mathbb{R} </math><ref><math>2^N</math> denotes the [[power set]] of <math>N</math>.</ref> from the set of all possible coalitions of players to a set of payments, and also satisfies <math> v( \emptyset ) = 0 </math>. The function describes how much collective payoff a set of players can gain by forming a coalition.

===Alternative game representations===
{{see also|Succinct game}}

Alternative game representation forms are used for some subclasses of games or adjusted to the needs of interdisciplinary research.<ref>{{cite arXiv |last1=Tagiew |first1=Rustam |title=If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction |date=3 May 2011 |eprint=1105.0558 |class=cs.GT }}</ref> In addition to classical game representations, some of the alternative representations also encode time related aspects.
{| class="wikitable sortable"
|-
!Name
!Year
!Means
![[#Game_types|Type of games]]
!Time
|-
|[[Congestion game]]<ref>{{cite journal |last1=Rosenthal |first1=Robert W. | author-link1=Robert W. Rosenthal |title=A class of games possessing pure-strategy Nash equilibria |journal=International Journal of Game Theory |date=December 1973 |volume=2 |issue=1 |pages=65–67 |doi=10.1007/BF01737559|s2cid=121904640 }}</ref>
|1973
|functions
|subset of n-person games, simultaneous moves
|No
|-
|Sequential form<ref>{{cite book |last1=Koller |first1=Daphne | author-link1=Daphne Koller |last2=Megiddo |first2=Nimrod | author-link2=Nimrod Megiddo |last3=von Stengel |first3=Bernhard |title=Proceedings of the twenty-sixth annual ACM symposium on Theory of computing – STOC '94 |chapter=Fast algorithms for finding randomized strategies in game trees |pages=750–759 |date=1994 |doi=10.1145/195058.195451 |isbn=0-89791-663-8 |s2cid=1893272 }}</ref>
|1994
|matrices
|2-person games of imperfect information
|No
|-
|Timed games<ref>{{cite journal |last1=Alur |first1=Rajeev |last2=Dill |first2=David L. |title=A theory of timed automata |journal=Theoretical Computer Science |date=April 1994 |volume=126 |issue=2 |pages=183–235 |doi=10.1016/0304-3975(94)90010-8|doi-access=free }}</ref><ref>{{cite journal |last1=Tomlin |first1=C.J. |last2=Lygeros |first2=J. |last3=Shankar Sastry |first3=S. |title=A game theoretic approach to controller design for hybrid systems |journal=Proceedings of the IEEE |date=July 2000 |volume=88 |issue=7 |pages=949–970 |doi=10.1109/5.871303|s2cid=1844682 }}</ref>
|1994
|functions
|2-person games
|Yes
|-
|Gala<ref>{{cite journal |last1=Koller |first1=Daphne |last2=Pfeffer |first2=Avi |title=Representations and solutions for game-theoretic problems |journal=Artificial Intelligence |date=July 1997 |volume=94 |issue=1–2 |pages=167–215 |doi=10.1016/S0004-3702(97)00023-4 }}</ref>
|1997
|[[First-order logic|logic]]
|n-person games of imperfect information
|No
|-
|[[Graphical game theory|Graphical games]]<ref>{{cite journal |last1=Michael |first1=Michael Kearns |last2=Littman |first2=Michael L. |title=Graphical Models for Game Theory |journal=In UAI |date=2001 |pages=253–260 |citeseerx=10.1.1.22.5705 }}</ref><ref>{{cite arXiv |last1=Kearns |first1=Michael |last2=Littman |first2=Michael L. |last3=Singh |first3=Satinder |title=Graphical Models for Game Theory |date=7 March 2011 |eprint=1301.2281 |class=cs.GT}}</ref>
|2001
|graphs, functions
|n-person games, simultaneous moves
|No
|-
|Local effect games<ref>{{cite conference|last1=Leyton-Brown |first1=Kevin |last2=Tennenholtz |first2=Moshe |title=Local-Effect Games |publisher=Schloss Dagstuhl-Leibniz-Zentrum für Informatik |conference=Dagstuhl Seminar Proceedings |date=2005 |url=https://drops.dagstuhl.de/volltexte/2005/219/pdf/05011.LeytonBrownKevin.Paper.219.pdf|access-date=February 3, 2023}}</ref>
|2003
|functions
|subset of n-person games, simultaneous moves
|No
|-
|[[Game description language|GDL]]<ref>{{cite journal |last1=Genesereth |first1=Michael |last2=Love |first2=Nathaniel |last3=Pell |first3=Barney |title=General Game Playing: Overview of the AAAI Competition |journal=AI Magazine |date=15 June 2005 |volume=26 |issue=2 |pages=62 |doi=10.1609/aimag.v26i2.1813 }}</ref>
|2005
|[[First-order logic|logic]]
|deterministic n-person games, simultaneous moves
|No
|-
|Game Petri-nets<ref>{{cite journal |last1=Clempner |first1=Julio |title=Modeling shortest path games with Petri nets: a Lyapunov based theory |journal=International Journal of Applied Mathematics and Computer Science |date=2006 |volume=16 |issue=3 |pages=387–397 |url=https://eudml.org/doc/207801 }}</ref>
|2006
|[[Petri net]]
|deterministic n-person games, simultaneous moves
|No
|-
|Continuous games<ref>{{cite journal |last1=Sannikov |first1=Yuliy |title=Games with Imperfectly Observable Actions in Continuous Time |journal=Econometrica |date=September 2007 |volume=75 |issue=5 |pages=1285–1329 |doi=10.1111/j.1468-0262.2007.00795.x |url=http://www.dklevine.com/archive/sannikov_games.pdf }}</ref>
|2007
|functions
|subset of 2-person games of imperfect information
|Yes
|-
|PNSI<ref>{{cite book |last1=Tagiew |first1=Rustam |title=2008 International Conference on Computational Intelligence for Modelling Control & Automation |chapter=Multi-Agent Petri-Games |date=December 2008 |pages=130–135 |doi=10.1109/CIMCA.2008.15 |isbn=978-0-7695-3514-2 |s2cid=16679934 }}</ref><ref>{{cite book |last1=Tagiew |first1=Rustam |title=New Challenges in Computational Collective Intelligence |chapter=On Multi-agent Petri Net Models for Computing Extensive Finite Games |volume=244 |date=2009 |pages=243–254 |doi=10.1007/978-3-642-03958-4_21 |publisher=Springer |series=Studies in Computational Intelligence |isbn=978-3-642-03957-7 }}</ref>
|2008
|[[Petri net]]
|n-person games of imperfect information
|Yes
|-
|Action graph games<ref>{{cite arXiv |last1=Bhat |first1=Navin |last2=Leyton-Brown |first2=Kevin |title=Computing Nash Equilibria of Action-Graph Games |date=11 July 2012 |eprint=1207.4128 |class=cs.GT}}</ref>
|2012
|graphs, functions
|n-person games, simultaneous moves
|No
|}