Applying Linear Programming to Game Theory

Introduction

A central problem in algorithmic game theory involves finding the Nash equilibria of a game quickly. It turns out that this task is very hard in general – finding Nash equilibria is, in fact, PPAD-complete, even for two-player games. There are, however, classes of games for which finding Nash equilibria is computable in worst-case polynomial time, using linear programming. In this blog post, we’ll explore three of these examples: proving the minmax theorem, finding Nash equilibria given the supports of the equilibrium strategies, and finding correlated equilibria.

Simultaneous-Move Games

A simultaneous-move game (N,A,u) is defined as a set of agents, actions, and payoffs. More formally, we have

  • N = \{1,...n\} agents, indexed by i
  • A = A_1 \times ... \times A_n, where A_i is a set of actions available to agent i and where a = (a_1,...,a_n) \in A denotes an action profile
  • u = (u_1,...u_n), where u_i: A \rightarrow \mathbb{R} is the payoff function for agent i.

Nash Equilibrium

A Nash equilibrium is an action profile where nobody has an incentive to deviate from his prescribed action when fixing the others’ actions. A Nash equilibrium can be of pure-strategies or mixed strategies.

Pure-Strategy Nash Equilibrium

In a pure strategy Nash equilibrium, each player plays one action in equilibrium.

More formally, an action profile a^* = (a_1^*,...,a_n^*) is a pure-strategy Nash equilibrium of the simultaneous-move game (N,A,u) if for all i,

u_i(a_i^*,a_{-i}^*) \geq u_i(a_i,a_{-i}^*) \text{ for all strategies } a_i \in A_i.

Mixed-Strategy Nash Equilibrium

In a mixed-strategy Nash equilibrium, a player can play a subset of his available actions according to a certain probability distribution. We say that the strategies a_i \in A_i played with positive probability in a mixed-strategy is in the support of that strategy profile.

Formally, a strategy profile \sigma^* = (\sigma_1^*,...,\sigma_n^*) is a mixed-strategy Nash equilibrium in game (N,A,u) if for all i,
u_i(\sigma_i^*,\sigma_{-i}^*) \geq u_i(a_i,\sigma_{-i}^*) \text{ for all strategies } a_i \in A_i.

Chicken

One example of a two-player, simultaneous move game is the game of chicken. The story for the game is as follows:

             Two teenagers are driving towards each other at a high velocity. If one swerves before the other, the “chicken” loses prestige among his peers, while the other gains prestige. If both of them swerve together, they both retain their honor. If neither of them swerve, both suffer serious injuries, which is much worse than losing their prestige.

This game can be represented in normal form as follows:

game diagram

The rows represent the strategies available to player 1 while the columns represent the strategies available to player 2. The left number within a matrix entry represents the payoff to player 1 when the respective actions are played, while the right number represents the payoff to player 2. It is easy to see that there is no pure-strategy Nash equilibrium to this game. A mixed-strategy equilibrium does exist, however, where both players swerve with probability \frac{2}{3} and go straight with probability \frac{1}{3}. In fact, there is a theorem, which we will not prove, that every finite-strategy, finite-player game has a mixed-strategy Nash equilibrium.

Two-player, Zero-sum Games

A zero-sum game is a game in which the total payoffs to the players sum to 0 for every action profile in the game. (In fact, these games could also be called constant-sum games, since the payoffs need only sum to the same constant value).

Maximin Strategy

A maximin strategy for player 1 is a strategy which maximizes player 1’s payoff given that player 2 tries to minimize player 1’s payoff for any given strategy a_1 \in A_1. Namely,
\overline{s_1} \in arg max_{s_1} \left[min_{a_2\in A_2} u_1(s_1,a_2)\right]

Minimax Strategy

A minimax strategy for player 1 is a strategy which minimizes player 2’s expected utility, given that player 2 tries to maximize his own payoff given any strategy of player 1.
\underline{s_1} \in arg min_{s_1} \left[max_{a_2\in A_2} u_2(s_1,a_2)\right]

Minmax Theorem

The minmax theorem states that for any two-player, zero-sum game, the set of each player’s maximin strategies will be identical to the set of minimax strategies, that any combination of these minimax/maximin strategies will be a Nash equilibrium of the game, and that each player’s maximin value will equal its minimax value. We can prove this theorem using strong duality.

To solve the maximin value for Player 1, we can solve the LP

Maximize v
Subject to:

v - u_1(a_1,a_2)p_1(a_1) \leq 0
\sum_{a_1 \in A_1} p_1(a_1) = 1
p_1(a_1) \geq 0, \forall a_1 \in A_1
where p_1(a_1) is the probability with which player 1 plays the action a_1 \in A_1.

The dual to this problem is

Minimize u
Subject to:

u - u_2(a_1,a_2)p_2(a_2) \geq 0
\sum_{a_2 \in A_2} p_2(a_2) = 1
p_2(a_2) \geq 0, \forall a_2 \in A_1
where p_2(a_2) is the probability with which player 2 plays the action a_2 \in A_2.

This is exactly the same as the LP for Player 2’s optimal strategy, and thus strong duality gives us the minmax theorem. We can solve for the minimax/maximin strategies using an algorithm like the simplex algorithm.

Finding a Nash equilibrium when given the supports in a general two-player game

Although it is difficult to find mixed-strategy Nash equilibria for finite-games in general, it is simpler to find Nash equilibria given the strategies that are in the support of each player’s mixed-strategy in equilibrium. Indeed, given candidate supports (\sigma_1,\sigma_2), we may find Nash equilibria, if feasible, by solving the following LP for any objective function:

Maximize  Any objective function
Subject to:

\sum_{a_2\in A_2} u_1(a_1,a_2)p_2(a_2) = v_1, \forall a_1 \in \sigma_1
\sum_{a_2\in A_2} u_1(a_1,a_2)p_2(a_2) \leq v_1, \forall a_1 \notin \sigma_1
\sum_{a_1 \in A_1} p_1(a_1) = 1
p_1(a_1) \geq 0, \forall a_1 \in \sigma_1
p_1(a_1) = 0, \forall a_1 \notin \sigma_1
\sum_{a_1\in A_1} u_1(a_1,a_2)p_1(a_1) = v_1, \forall a_2 \in \sigma_1
\sum_{a_1\in A_1} u_1(a_1,a_2)p_1(a_1) \leq v_1, \forall a_2 \notin \sigma_1
\sum_{a_1 \in A_1} p_2(a_2) = 1
p_1(a_2) \geq 0, \forall a_2 \in \sigma_1
p_1(a_2) = 0, \forall a_2 \notin \sigma_1

We note that all strategies in a given support must be used in the mixed-strategy Nash equilibrium. The feasibility of this problem in comparison with the difficulty of finding Nash equilibria suggests that the main difficulty in finding Nash equilibria comes from the difficulty of searching through all possible combinations of supports for the action profiles in a game.

Correlated Equilibrium

A correlated equilibrium is another type of equilibrium which is a superset of Nash equilibria. In addition to the strategies available to players, there can be a signal which allows players to coordinate their actions. A natural example of a correlated equilibirum is at a traffic junction. When the traffic light is red, drivers stop at an intersection, whereas if the light is green, they go on – this insures that there are no (or relatively few) traffic accidents. If there aren’t traffic signals, drivers must play a mixed strategy of going on and stopping in equilibrium, which would guarantee a non-trivial amount of accidents, given that people do drive with some probability.

More generally, a correlated equilibrium can be defined as follows:

A joint probability distribution p^* on action profiles in A is a correlated equilibrium of a simultaneous-move game (N,A,u) if for all agents i, and for actions a_i \in A_i with p^*(a_i) >0

\sum_{a_{-i}\in A_{\-i}} p^*(a_{-i} | a_i)u_i(a_i,a_{-i}) \geq \sum_{a_{-i}\in A_{-i}} p^*(a_{-i} | a_i) u_i (a_i',a_{-i})

A Nash equilibrium is a special case of the correlated equilibrium, when (p^*a_{-i}|a_i) = p^*(a_{-i}). Interestingly, the generalization of Nash equilibrium to correlated equilibrium allows us to solve for equilibrium using an LP.

Maximize  Any objective function
Subject to:

\sum_{a_{-i}\in A_{\-i}} p^*(a_{-i} | a_i)u_i(a_i,a_{-i}) \geq \sum_{a_{-i}\in A_{-i}} p^*(a_{-i} | a_i) u_i (a_i',a_{-i})
\forall i \in N, \forall a_i \in A_i, \forall a_i' \in A_i
\sum_{a\in A} p(a) = 1
p(a) \geq 0, \forall a \in A.

It is interesting to note that the independence of each player’s action in a Nash equilibrium breaks the linearity of the first constraint in the LP above. Hence, it is the representation of all players’ strategies as a joint distribution which allows us to compute correlated equilibrium quickly.

Sources

This blog post draws heavily from the forthcoming book Economics and Computation by David C. Parkes and Sven Seuken.

Advertisements

2 thoughts on “Applying Linear Programming to Game Theory

  1. The webpage is the perfect put to showcase original crop, innovative ideas, cooperative military, et cetera. Today, present are probably billions of webpage on the Internet from about the world. The two the majority efficient conduct to get public to access and look on one’s webpage are through ads and investigate engines. Just like introduction ads on Television, newspapers, billboards, etc., populace can use up cash to place ads of their webpage on admired WebPages visited often by the others. The ads will exist in hyperlink which when it is clicked, will robotically straight the web browser to the ads’ website and display the webpage.
    Using the investigate engine to straight citizens to your webpage is free other than requires a modest endeavor lying on your part. There are three accepted look for engines (Bing, Google, and Yahoo) that the all-purpose communal uses to seem designed for information. Search engine employs vast CPU capital to explore billions of WebPages on the Internet to get the information that people query. Basically, the search is conducted in the next sequences:
    1) A easy software routine called spiderbot is sent absent to the Internet to crawl the webpage sites stored in the search engine’s Doman Name Database (DNdb). To accelerate the crawling, quite a lot of spiderbots may exist second-hand next to the equal time.
    2) The spiderbot afterward extracts the keywords in the webpage’s HTML source system. It updates the DNdb with the keywords connected with the webpage.
    3) The spiderbot next goes to the next webpage site in the DNdb. The process might obtain more than a few days to complete every the webpage sites in the DNdb.
    4) Steps 1) to 3) are recurring resting on a regular root to make certain that all the WebPages in the DNdb enclose their latest keywords.
    So, in organize to have your webpage to subsist searched, you need to register it with the investigate engine to live incorporated in its DNdb. Click on the hyperlink beneath to locate not in how.
    http://sprzatanie-bydgoszcz.com.pl
    As you type your query in the investigate engine’s webpage, it extracts the keywords in the query and starts a explore in its DMdb. If supplementary than one bout is create, every one connected webpage information will live displayed in the orders according to the webpage’s contented and relevance.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s