Nash equilibrium for a normal-form game given by a poset

58 Views Asked by At

Let $P$ be a poset partially ordered set. EDIT: $<$ is antisymmetric but not necessary associative. Hence, $(P,<)$ is not necessarily a poset, as reminded me by joriki.

Consider a simple $2$-player multi-round game, in each round of which Alice and Bob simultaneously choose an element of $P$ (say $a$ and $b$) and (1) if $a>b$ then Alice gets a point, (2) if $b>a$ then Bob gets a point, (3) if $a$ and $b$ are incomparable then neither gets any points. The game has many rounds.

Paper-rock-scissors is a simple example of this game.

For $p\in P$ let $n(p)=\#\{q\in P: q< p\}$ and let $N=\sum_{p\in P} n_p.$

I believe:

Theorem If $N>0$ then the game has a unique Nash equilibrium strategy consisting of choosing each $p\in P$ with probability $n(p)/N.$

Q: Is this statement known in game theory? What would be a reference for it?

Googling this topic I realized that my game is an example of a "normal form game". And even though it is based on a poset it is not a "poset game".

1

There are 1 best solutions below

0
On

In the following I'll assume that by “incomparable” you meant “incomparable or equal”. I'll also assume that you intended the poset to be finite (since otherwise you couldn't have summed over $n_p$).

Rock paper scissors is not an example of what you've defined. A poset is defined by a transitive relation, and the winning relation in rock paper scissors is not transitive. (In fact, that's sort of the point of the game.)

A game defined through a poset in this way is uninteresting, since every player will simply always pick a maximal element.

We can consider games defined by an asymmetric relation $\lt$ that need not be transitive, such as rock paper scissors. For such games, your theorem is false (although the resulting strategy happens to be in equilibrium in rock paper scissors due to the symmetry).

Consider the game on $P=(a,b,c,d)$ where $a\lt b\lt c\lt d\lt a$ and also $a\lt c$ and $b\lt d$. Your theorem would lead to $a$ and $b$ being chosen with probability $1/(1+1+2+2)=\frac16$ each and $c$ and $d$ being chosen with probability $2/(1+1+2+2)=\frac13$ each. This is not an equilibrium, since if you apply this strategy, then I can choose $d$ and expect $\frac13\cdot0+\frac13\cdot1+\frac16\cdot1+\frac16\cdot(-1)=\frac13$ points, whereas the equilibrium value of the game is $0$ by symmetry.

In equilibrium, all actions that are chosen with non-zero probability must yield the same expectation. If we assume that all probabilities are nonzero, this yields

$$ p_d-p_b-p_c=p_a-p_c-p_d=p_a+p_b-p_d=p_b+p_c-p_a\;, $$

which implies $p_b=-p_c$, so there is no equilibrium with all probabilities non-zero. Since $b$ looks like the least attractive action, let's try making only the other three probabilities non-zero. That leaves us with a game of rock paper scissors among $a$, $c$ and $d$, so by symmetry $p_a=p_c=p_d=\frac13$. This is indeed an equilibrium for the entire game, since the payoff for choosing $b$ is $\frac13-\frac13-\frac13=-\frac13$, so equilibrium is achieved by $p_b=0$.

You can't distinguish $a$ and $b$ by the number of relations they have (each wins against one other action and loses against two). The fact that they nevertheless have different equilibrium probablities shows that the equilibrium can't be found by a simple expression like the one in your theorem that only takes into account the “local” properties of each action.