A community effort: equilibrium in quitting games [closed]

Question

This thread is in the spirit of the polymath project: a combined effort of the community to solve a difficult open problem. It is an activity of the European Network for Game Theory whose goal is to strengthen cooperation among the game theory community, and everyone, game theorist or not, is invited to join this effort.

The problem I will present is the determination whether every quitting game admits an $\epsilon$-equilibrium, for every $\epsilon > 0$. Some classes of quitting games are known to have $\epsilon$-equilibria, and I will mention them below. The reader of this thread should be aware that some scholars believe that the answer to this problem is positive, while others believe that the answer is negative.

I will first describe the problem in mathematical terms, then provide the game theoretic model from which it arises, and finally describe approaches already attempted in the literature in relation to this problem.

Quitting Games as Strategic-Form Games:

A strategic-form game is a triplet $(n,(S_i)_{i=1}^n,g)$, where

• $n > 0$ is the number of players. -For each player $i$, $S_i$ is a set of pure strategies. In our case, the sets $S_i$ will be the infinite set $\mathbf{N} \cup \{\infty\} = \{1,2,\cdots, \infty\}$. The Cartesian product of the set of pure strategies is $S := \times_{i=1}^n S_i$.
• $g : S \to \mathbf{R}^n$ is the payoff function.

A mixed strategy of player $i$ is a probability distribution $\sigma_i$ over $S_i$. A mixed-strategy profile is a vector $\sigma = (\sigma_i)_{i=1}^n$ of mixed strategies, one for each player. The expected payoff that corresponds to a mixed-strategy profile $\sigma = (\sigma_i)_{i=1}^n$ is \begin{equation} g(\sigma) := \sum_{s =(s_i)_{i=1}^n \in S} \left( g(s) \cdot \prod_{i=1}^n \sigma_i(s_i)\right). \end{equation}

Let $\epsilon \geq 0$. A mixed-strategy profile $\sigma^* = (\sigma^*_i)_{i=1}^n$ is an $\epsilon$-equilibrium if for every player $i\in \{1,2,\ldots,n\}$ and every mixed-strategy $\sigma_i$ of player $i$ we have \begin{equation} g_i(\sigma^*) \geq g_i(\sigma_i,\sigma^*_{-i}) - \epsilon, \end{equation} where $\sigma^*_{-i} = (\sigma^*_j)_{j \neq i}$.

When the sets $(S_i)_{i=1}^n$ are finite, a 0-equilibrium exists (Nash, 1950). When $n=2$ and $S_1=S_2 = \mathbf{N}$ are the set of natural numbers, an $\epsilon$-equilibrium may fail to exist for $\epsilon > 0$ sufficiently small. For example, the game ``choose the largest integer'', where the payoff function $g$ is defined by

\begin{equation} g_1(s_1,s_2) = -g_2(s_1,s_2) = \left\{ \begin{array}{lll} 1 & \ \ \ \ \ & s_1 \geq s_2,\\ -1 & & s_1 < s_2, \end{array} \right. \end{equation} is a game with no $\epsilon$-equilibrium for $\epsilon < 1$.

We are interested in a specific class of games, that we define now. In this definition we use the following notation: for every vector $s = (s_i)_{i=1}^n \in \{1,2,\ldots,\infty\}^n$, define \begin{equation} \min(s) := \bigl\{ i \in \{1,2,\ldots,n\} \colon s_i < \infty, s_i \leq s_j \ \ \ \forall j\in \{1,2,\ldots,n\}\bigr\}. \end{equation} This is the set of minimal coordinates of $s$ among the finite coordinates. The strategic-form game $(n,(S_i)_{i=1}^n,g)$ is a quitting game if

• $S_i = \{1,2,\cdots, \infty\}$ for each player $i \in \{1,2,\ldots,n\}$.
• The payoff function $g$ satisfies that $g(s)$ is a function of $\min(s)$, that is, $g(s) = g(s')$ whenever $\min(s) = \min(s')$.

The Problem: The question we are interested in is whether every quitting game admits an $\epsilon$-equilibrium, for every $\epsilon > 0$.

For $n=2$ a positive answer can be obtained by checking all configurations of the payoffs. For $n=3$ a positive result was given by Solan (1999).

Example of a Three-Player Game:

I will now provide the first example of a quitting game that was solved. Suppose that $n=3$ and $g$ is given by

\begin{array}{l|l} \min(s) & g(s)\\ \hline \emptyset & (0,0,0)\\ \{1\} & (1,3,0) \\ \{2\} & (0,1,3) \\ \{3\} & (3,0,1) \\ \{1,2\} & (1,0,1) \\ \{1,3\} & (0,1,1) \\ \{2,3\} & (1,1,0) \\ \{1,2,3\} & (0,0,0) \end{array}

This game was studied by Flesch, Thuijsman, and Vrieze (1997), who showed that the following mixed-strategy profile $\sigma^*$ is a 0-equilibrium:

• $\sigma^*_1(1+3k) = \tfrac{1}{2^k}$, $\sigma^*_1(2+3k) = 0$, and $\sigma^*_1(3+3k) =0$ for every $k \geq 0$. -$\sigma^*_2(1+3k) = 0$, $\sigma^*_2(2+3k) = \tfrac{1}{2^k}$, and $\sigma^*_2(2+3k) = 0$ for every $k \geq 0$.
• $\sigma^*_3(1+3k) = 0$, $\sigma^*_3(2+3k) = 0$, and $\sigma^*_3(3+3k) = \tfrac{1}{2^k}$ for every $k \geq 0$.

Under this mixed-strategy profile, Player~1 chooses a number in $1,4,7,\cdots$ according to a geometric distribution with parameter $\tfrac{1}{2}$, Player~2 chooses a number in $2,5,8,\cdots$ according to a geometric distribution with parameter $\tfrac{1}{2}$, and Player~3 chooses a number in $3,6,9,\cdots$ according to a geometric distribution with parameter $\tfrac{1}{2}$. In particular, the set $\min(s)$ contains a single player; with probability $\tfrac{4}{7}$ we have $\min(s) = \{1\}$, with probability $\tfrac{2}{7}$ we have $\min(s) = \{2\}$, and with probability $\tfrac{1}{7}$ we have $\min(s)=\{3\}$. It follows that the equilibrium payoff is $g(\sigma^*)=(1,2,1)$.

Example of a Four-Player Game:

I will now present an example of a 4-player quitting game, which was studied by Solan and Vieille (2002).

\begin{array}{l|l} \min(s) & g(s)\\ \hline \emptyset & (0,0,0,0)\\ \{1\} & (1,4,0,0) \\ \{2\} & (4,1,0,0) \\ \{3\} & (0,0,1,4) \\ \{4\} & (0,0,4,1) \\ \{1,2\} & (1,1,1,1) \\ \{1,3\} & (1,1,1,0) \\ \{1,4\} & (1,0,1,1) \\ \{2,3\} & (0,1,1,1) \\ \{2,4\} & (1,1,0,1) \\ \{3,4\} & (1,1,1,1) \\ \{1,2,3\} & (1,0,0,0) \\ \{1,2,4\} & (0,1,0,0) \\ \{1,3,4\} & (0,0,0,1) \\ \{2,3,4\} & (0,0,1,0) \\ \{1,2,3,4\} & (-1,-1,-1,-1) \end{array}

Solan and Vieille (2002) proved that the following mixed-strategy profile $x^*$ is a 0-equilibrium, where $a\approx 0.6999124$ and $b\approx 0.651355$:

• $\sigma^*_1(1+2k) = (1-a)a^k$ and $\sigma^*_1(2+2k)=0$ for every $k \geq 0$.
• $\sigma^*_3(1+2k) = (1-b)b^k$ and $\sigma^*_2(2+2k)=0$ for every $k \geq 0$.
• $\sigma^*_2(1+2k) = 0$ and $\sigma^*_2(2+2k) = (1-a)a^k$ for every $k \geq 0$.
• $\sigma^*_4(1+2k) = 0$ and $\sigma^*_4(2+2k) = (1-b)b^k$ for every $k \geq 0$.

Under this 0-equilibrium, Players 1 and 3 may select only odd numbers while Players 2 and 4 may select only even numbers.

Quitting Games as Dynamic Games:

Now that we presented the mathematical question and provided two examples, I will describe the game theoretic model that gives rise to it.

A quitting game (version 2) is a game that is played in stages $1,2,\cdots$ until it terminates. There are $n$ players. In every stage, each player decides whether to continue or to quit at that stage. If all players decide to continue, the game continues to the next stage. If at least one player decides to quit, then the game terminates, and each player $i$ receives the payoff $u^S_i$, where $S$ is the set of players who quit at the termination stage. If no player ever quits, the payoff of each player $i$ is $u^\infty_i$. The payoffs are undiscounted, and each player is interested in maximizing his or her expected terminal payoff.

The terminal payoff thus depends on the set of players who quit at the termination stage; if the game is terminated by the set of players $S$, then the payoff is $u^S = (u^S_i)_{i=1}^n \in \mathbf{R}^n$. We denote an $n$-player quitting game by the payoff function $(u^S)_{S \subseteq \{1,2,\ldots,n\}}$.

A pure strategy for a player is the stage in which he quits, that is, $S_i = \{1,2,\ldots,\infty\}$, where the pure strategy $\infty$ means that the players never quits. A quitting game (version 2) defines a strategic-form game with the $n$ players, where the set of pure strategies is $S_i$ and the payoff function is given by $g(s) = u^{\min(s)}$ for every $s \in S$. Since the payoff in a quitting game (version 2) depends on the set of players who are the first to quit, the two definitions of quitting games that we provided coincide.

As mentioned earlier, a mixed strategy of player $i$ is a probability distribution $\sigma_i$ over $S_i$. We can equivalently present a mixed strategy by the sequence of conditional probabilities that player $i$ quits in each stage, given that the game was not terminated before that stage. That is, the mixed strategy $\sigma_i$ can be represented by the vector $x_i = (x_i(t))_{t=1}^\infty$, where \begin{equation*} x_i(t) = \frac{\sigma_i(t)}{\sum_{k=t}^\infty \sigma_i(k) + \sigma_i(\infty)}. \end{equation*} Game theorists will note that the vector $x_i$ is the behavior strategy that corresponds to the mixed strategy $\sigma_i$. We will denote the payoff induced by the mixed-strategy profile $x$ by $u(x)$: [ u(x) := \sum_{s \in S} u(\min(s)) \cdot \prod_{i=1}^n x_i(s_i). ]

We can graphically present the three-player game studied by Flesch, Thuijsman, and Vrieze (1997) as follows.

One should view this figure as a three-dimensional matrix: Player~1 chooses a row, Player~2 chooses a column, and Player~3 chooses the left-hand side or the right-hand side matrix. An asterisked entry in the matrix corresponds to a choice that lead the game to terminate.

In the equivalent representation of mixed strategies as sequences, the following mixed-strategy profile is a 0-equilibrium:

• $x^*_1(1 + 3k) = \tfrac{1}{2}, x^*_1(2+3k) = 0, x^*_1(3+3k) = 0$, for every $k \geq 0$.
• $x^*_2(1 + 3k) = 0, x^*_2(2+3k) = \tfrac{1}{2}, x^*_2(3+3k) = 0$, for every $k \geq 0$.
• $x^*_3(1 + 3k) = 0, x^*_3(2+3k) = 0, x^*_3(3+3k) = \tfrac{1}{2}$, for every $k \geq 0$.

This mixed-strategy profile is cyclic: in the first stage, Player~1 quits with probability $\tfrac{1}{2}$ while the other two players continue, in the second stage Player~2 quits with probability $\tfrac{1}{2}$ while the other two players continue, in the third stage Player~3 quits with probability $\tfrac{1}{2}$ while the other two players continue, and the players repeat this behavior cyclically. As mentioned before, under this mixed strategy profile, the payoff is \begin{equation*} u(x^*) = (1,2,1). \end{equation*} By the cyclic nature of the game, the payoff from the second stage on is $(1,1,2)$, and the payoff from the third stage on is $(2,1,1)$. That is, if $y^*$ is the mixed-strategy profile that is defined by $y^*(t) = x^*({t+1})$ for every $t \geq 1$, then \begin{equation*} u(y^*) = (1,1,2), \end{equation*} and if $z^*$ is the mixed-strategy profile that is defined by $z^*(t) = x^*({t+2})$ for every $t \geq 1$, then \begin{equation*} u(z^*) = (2,1,1). \end{equation*}

Quitting Games and Dynamical Systems:

This solution leads one to a new approach that involves dynamical systems. To describe this approach I will describe binary games in strategic form. A binary game is a strategic-f0rm game where $S_i = \{C,Q\}$ for every player $i\in \{1,2,\ldots,n\}$. A mixed strategy of a player in a binary game is equivalent to a number in $[0,1]$, the probability that the player chooses the pure strategy $Q$. A mixed-strategy profile is denoted by $\xi = (\xi_i)_{i =1}^n \in [0,1]^n$.

When $\xi \in \mathbf{R}^n$ is a vector, we denote by $(1_i,\xi_{-i})$ the vector $\xi$ after replacing the $i$'th coordinate with 1. The definition of $(0_i,\xi_{-i})$ is analogous. A vector $\xi$ is a perfect $\epsilon$-equilibrium in a binary game if the following conditions hold for every $i \in \{1,2,\ldots,n\}$:

• If $\xi_i > 0$ then $g_i(1_i,\xi_{-i}) \geq g_i(\xi)-\epsilon$.
• If $\xi_i < 1$ then $g_i(0_i,\xi_{-i}) \geq g_i(\xi)-\epsilon$.

This definition is a refinement of the concept of $\epsilon$-equilibrium, the two coincide for $\epsilon = 0$, and in the literature of computer sciences it is known as well-supported equilibrium. Under an $\epsilon$-equilibrium, a player may play with positive probability an action that yields to him a low payoff, as long as this probability is sufficiently small; under a perfect $\epsilon$-equilibrium this does not happen, and all actions that are played with positive probability give roughly the same payoff.

Given a quitting game (version 2) $u = (u^S)_{S \subseteq \{1,2,\ldots,n\}}$ and a vector $c \in \mathbf{R}^n$, we define a binary game $G_B(c) = (n,(\widehat u^S)_{S \subseteq \{1,2,\ldots,n\}})$ by

\begin{equation} \widehat u^S := \left\{ \begin{array}{lll} c & \ \ \ \ \ & S = \emptyset,\\ u^S & & S \neq \emptyset. \end{array} \right. \end{equation} That is, we replace the payoff $u^\emptyset$ by $c$.

Going back to the three-player example of Flesch, Thuijsman, and Vrieze (1997), one can verify that $\xi = (\tfrac{1}{2},0,0)$ is a 0-equilibrium in the binary game $G_B(1,2,1)$. Similarly, $\xi=(0,\tfrac{1}{2},0)$ is a 0-equilibrium in the binary game $G_B(1,1,2)$, and $\xi=(0,0,\tfrac{1}{2})$ is a 0-equilibrium in the binary game $G_B(2,1,1)$. In other words, if we consider the 0-equilibrium $x^*$ of the three-player quitting game that was identified by Flesch, Thuijsman, and Vrieze (1997), then the mixed-action profile $x^*(t)$ is a 0-equilibrium in the binary game that is derived from $u$ when plugging the payoff under $x^*$ from stage $t+1$ and on as $\widehat u^\emptyset$. In other words, $x^*(t)$ is a 0-equilibrium in the binary game $G_B(u(x^*({t+1}),x^*({t+2}),\cdots))$.

This observation is general: if we are given a quitting game $u$, and if $x$ is a mixed-strategy profile in the quitting game that satisfies the following two properties:

• The vector $x(t)$ is a 0-equilibrium in the binary game $G_B(u(x^*({t+1}),x^*({t+2}),\cdots))$, for every $t \geq 1$.
• Under the mixed-strategy profile $x$ the game is bound to terminate: $\prod_{t =1}^\infty \prod_{i=1}^n (1-x_i(t)) = 0$.

Then $x$ is a 0-equilibrium in the quitting game $u$. This result follows from the definitions and the monotone convergence theorem (or the martingale convergence theorem).

In fact, a more general result (that will be described now) was proven by Solan and Vieille (2001).

Let now $u$ be a quitting game, and $x$ a mixed-strategy profile in this game. Solan and Vieille (2001) proved that if the following two conditions hold:

• For every $t \geq 1$ the vector $x(t)$ is a perfect $\epsilon$-equilibrium in the binary game $G_B(u(x({t+1}),x({t+2}),\cdots))$.
• For every $t$, $\sum_{i=1}^n x_i(t) \geq \epsilon$.

then $x$ is an $\epsilon^{1/6}$-equilibrium of the quitting game $u$.

Fix a quitting game $u$ and $\epsilon > 0$. Let $F_\epsilon$ be the set-valued function that assigns to every vector $c \in \mathbf{R}^n$ the set of perfect $\epsilon$-equilibria of the binary game $G_B(c)$. An orbit of $F_\epsilon$ is a sequence $(c^t)_{t \geq 1}$ that satisfies $c^t \in F_\epsilon(c^{t+1})$ for every $t \geq 1$. By Solan and Vieille (2001), if the set-valued function $F_\epsilon$ has an orbit that satisfies that for every $t \geq 1$, there exists a vector $x^t \in [0,1]^n$ such that $x^t$ is a perfect $\epsilon$-equilibrium in the binary game $G_B(c^{t+1})$ and the payoff under $x^t$ in this game is $c^t$, that is, \begin{equation*} c^t = \widehat u(x^t) = c^{t+1} \prod_{i=1}^n (1-x^t_i) + \sum_{\emptyset \neq S \subseteq \{1,2,\ldots,n\}} \left( u^S \prod_{i \in S} x^t_i \prod_{i \not\in S} (1-x^t_i)\right), \end{equation*} and if $\sum_{i=1}^n x^t_i \geq \epsilon$ for every $t \geq 1$, then $x = (x^t)_{t \geq 1}$ is an $\epsilon^{1/6}$-equilibrium in the quitting game.

Solan and Vieille (2001) showed that if for every $i \in \{1,2,\ldots,n\}$ and every $S \subseteq \{1,2,\ldots,n\}$ we have $u^{\{i\}}_i \geq u^{S\cup \{i\}}_i$ (that is, each player prefers to quit alone rather than to quit with other players), then $F_\epsilon$ has an orbit that satisfies the above desired properties. Simon (2012) used tools from algebraic topology to extend the family of quitting games that have such an orbit. To date it is not known whether such an orbit exists for every quitting game.

Quitting Games and Linear Complementarity Problems:

I will now describe another technique to study quitting games that was used in Solan and Solan (2017) and involves linear complementarity problems. Let $R$ be an $n \times n$ matrix whose columns are denoted by $r^1,r^2,\cdots,r^n$, and let $q \in \mathbf{R}^n$. Denote by $\Delta(\{0,1,\cdots,n\})$ the set of probability distributions over the set $\{0,1,\cdots,n\}$. The linear complementarity problem $lcp(R,q)$ is the following problem that consists of linear equalities and inequalities: \begin{eqnarray} \hbox{Find}&&w \in \mathbf{R}^n \hbox{ and } z = (z_0,z_1,\cdots,z_n) \in \Delta(\{0,1,\cdots,n\}),\label{lpc}\\ \hbox{such that} && w_i \geq r^i_i, \ \ \ \forall i \in \{1,2,\ldots,n\},\\ && w = z_0q + \sum_{i =1}^n z_i r^i,\\ &&z_i = 0 \hbox{ or } w_i = r^i_i, \ \ \ \forall i \in \{1,2,\ldots,n\}. \end{eqnarray} The last condition in this problem is the complementarity condition. This definition resembles the usual definition of linear complementarity problems, but does not coincide with it.

We note that if $q$ satisfies $q_i \geq r^i_i$ for every $i \in \{1,2,\ldots,n\}$, then there is at least one solution to the linear complementarity problem, namely, $z = (1,0,\cdots,0)$ and $w = q$. An $n\times n$ matrix $R$ is called a $Q$-matrix if for every $q \in \mathbf{R}^n$ the linear complementarity problem $lcp(R,q)$ has at least one solution.

Let now $u=(u^S)_{S \subseteq \{1,2,\ldots,n\}}$ be a quitting game. Let $R$ be the $n \times n$ matrix whose $i$'th column is $u^{\{i\}}$, that is $r^i = u^{\{i\}}$. Solan and Solan (2017) proved that if the matrix $R$ is not a $Q$-matrix, then the quitting game $u$ has a 0-equilibrium. Moreover, the 0-equilibrium $x$ is \emph{stationary}: we have $x^t = x^{t+1}$ for every $t \geq 0$.

Conclusion:

As I mentioned earlier, it is not clear whether every quitting game has an $\epsilon$-equilibrium for every $\epsilon > 0$. To prove that the answer is negative, it is sufficient to find one quitting game that has no $\epsilon$-equilibrium for $\epsilon > 0$ sufficiently small. One way to do that seems to involve the identification of a quitting game for which the set-valued function $F_\epsilon$ does not have an orbit that satisfies the properties mentioned in the section on dynamical systems. To do that, one may wish to characterize the set-valued functions $F_\epsilon$ that arise from quitting games, and show that this class is sufficiently rich.

What are the tools that we need to use if the answer to our main problem is positive? I hope that this thread will clarify this question. Though our goal is to find a definite answer to an open problem, the community will benefit from partial results: the identification of classes of quitting games that admit $\epsilon$-equilibrium for every $\epsilon > 0$, the identification of new tools that are relevant to the problem, or the linkage of this problem with other mathematical problems and mathematical areas.

I thank Janos Flesch, Abraham Neyman, and Ron Peretz for commenting on the presentation of the problem.