The Optimal Way to Play the Most Difficult
 Repeated Coordination Games

Pure win-lose coordination games ($\mathsf{WLC}$-games) are simple yet fundamental games where all players receive the same payoffs: 1 (win) or 0 (lose). This paper studies repeated $\mathsf{WLC}$-games, where the players make simultaneous choices in discrete rounds until (if ever) succeeding to coordinate on a winning profile. Choice matching games ($\mathsf{CM}$-games) are the simplest class of such games. The choice matching game $\mathsf{CM}_{\_}m^{n}$ has $n$ players with the goal to choose the same choice among $m$ different indistinguishable choices, with no communication during play. The players can use the history of the game (i.e., the players’ choices in previous rounds) for their benefit as the game proceeds. For simplicity, we denote the two-player game $\mathsf{CM}_{\_}m^{2}$  by  $\mathsf{CM}_{\_}m$.

A paradigmatic real-life scenario with a choice matching game relates to a phenomenon that has humorously been called “pavement tango” or “droitwich” in [2]. Here two people try to pass each other but may end up blocking each other by repeatedly moving sideways into the same direction. For another example of a choice matching game, consider $\mathsf{CM}_{\_}3$, the coordination-based variant of the rock-paper-scissors game, pictured on the right. {vwcol}[widths=0.85,0.15, sep=2mm, justify=flush, rule=0pt, lines=7] Here the two players (i.e., columns) coordinate if they succeed choosing an edge from one of the three rows. The players first choose randomly; suppose they select the nodes in dotted circles. Next the players have three options: (1) to repeat their first choice, (2) to try to coordinate with the first choice of the other player, or (3) to select the choice which has not been selected yet. Supposing that the players behave symmetrically, (3) is the only way to guarantee coordination in the second round.

A general $n$-player $\mathsf{WLC}$-game is a generalization of $\mathsf{CM}_{\_}m^{n}$ where the players do not necessarily have to choose from the same row to coordinate, and it may not even suffice to choose from the same row. In classical matrix form representation, two-player choice matching games have ones on the diagonal and zeroes elsewhere, while general two-player $\mathsf{WLC}$-games have general distributions of ones and zeroes; see Definition 2.1 for the full formal details.

In repeated $\mathsf{WLC}$-games, it is natural to try to coordinate as quickly as possible. There are two main scenarios to be investigated: guaranteeing coordination (with certainty) in as few rounds as possible and minimizing the expected number of rounds for coordination. The former concerns the number of rounds it takes to coordinate in the worst case and is measured in terms of guaranteed coordination times ($\mathsf{GCT}$s). The latter relates to the average case analysis measured in terms of expected coordination times ($\mathsf{ECT}$s).

Two protocols play a central role in our study. We introduce the so-called loop avoidance protocol $\mathsf{LA}$ (cf. Def. 4.1) that essentially instructs players to play so that the generated history of choices always reduces the symmetries (e.g., automorphisms) of the game structure. We also use the so-called wait-or-move protocol $\mathsf{WM}$ (cf. Def. 4.5), essentially telling players to randomly alternate between two choices that both coordinate with at least one of the opponent’s two choices. We show that $\mathsf{WM}$ leads to coordination in all two-player $\mathsf{WLC}$-games very fast, the $\mathsf{ECT}$ being at most $3-2p$, where $p$ is the probability of coordinating in the first round with random choices.

We then provide a complete analysis of the optimal $\mathsf{ECT}$s and $\mathsf{GCT}$s in all choice matching games $\mathsf{CM}_{\_}m$. We also identify the protocols giving the optimal $\mathsf{ECT}$s and $\mathsf{GCT}$s and show their uniqueness, where possible. The table in Figure 1 on the next page summarizes these results.

Our analysis is fully complete, as we prove that there exists a continuum of optimal protocols for $\mathsf{CM}_{\_}4$ and establish that for all even $m$, no protocol guarantees a win in $\mathsf{CM}_{\_}m$.

Concerning the more general class of all $\mathsf{WLC}$-games, we provide the following complete characterization of upper bounds for the optimal $\mathsf{ECT}$s in all two-player $\mathsf{WLC}$-games as a function of game size (a game in a classical matrix form is of size $m$ when the maximum of the number of rows and columns is $m$):

Also, concerning two-player $\mathsf{CM}$-games, we establish that $\mathsf{CM}_{\_}m$ has the strictly greatest optimal $\mathsf{ECT}$ out of all two-player $\mathsf{WLC}$-games of size $m\not=3$, making $\mathsf{CM}$-games the most difficult $\mathsf{WLC}$-games to coordinating in. We give a separate full analysis of the case $m=3$.

Two comments are in order. Firstly, in real-life scenarios it can be very inefficient to determine the absolutely optimal protocols taking into account the full game structure. Indeed, this generally requires an analysis of the game structure and thus identifying, e.g., automorphic choices. Computing automorphisms of (even bipartite graphs) is well known to be hard. However, our analysis gives an instant way of finding a fast protocol for any two-player $\mathsf{WLC}$-game $G$. The $\mathsf{ECT}$ given by this protocol in $G$ is better or equal to the greatest optimal $\mathsf{ECT}$ of the games of the same size (cf. the theorem above). Secondly, our main analysis concerns only two-player games. However, the arguments for this case are already quite involved, so the $n$-player case is expected to be highly complex and is thus left for the future. Furthermore, the two-player case is an especially important special case covering, e.g., learning of communication protocols in distributed systems.

However, $\mathsf{WLC}$-games are a simple class of games that have not been extensively studied in the literature. In particular, choice matching games clearly constitute a highly fundamental class of games, and it is thus surprising that the analysis of the current paper has not been previously carried out. Thus the related analysis is well justified; it closes a gap in the literature. Indeed, while $\mathsf{CM}$-games are simple, they precisely capture the highly fundamental coordination problem of picking the same choice from a set of choices.

Our study differs from the classical game-theoretic work on repeated games where the focus is on accumulated payoffs instead of the discrete outcomes of $\mathsf{WLC}$-games. Indeed, repeated $\mathsf{WLC}$-games are based on reachability objectives. Especially our worst case (but also the average case) analysis has only superficial overlap with typical work on repeated games.

However, similar work exists, the most notable example being the seminal article [7] that studies a generalization of $\mathsf{WLC}$-games in a framework that has some similarities with our setting. Also the papers [9], [11], [8], [10] have a similar focus, as they also concentrate on coordination games with discrete win-lose outcomes. However, the papers [9], [11], [8], [10] do not investigate optimality of protocols in repeated games, unlike the current paper. The seminal work [7] introduces (what is equivalent to) the two-player $\mathsf{CM}$-games in their final section on general examples. They also essentially identify the optimal ways of playing $\mathsf{CM}_{\_}2$ and $\mathsf{CM}_{\_}3$ (discussed also in this article) although in a technically somewhat different setting with accumulated payoffs. Furthermore, they observe that a protocol essentially equivalent to $\mathsf{WM}$ is the best way to play $\mathsf{CM}_{\_}6$, an observation we also make in our setting. However, optimality of $\mathsf{WM}$ in $\mathsf{CM}_{\_}6$ is not proved in [7]. This would require an extensive analysis proving that the players cannot make beneficial use of asymmetric histories created by non-coordinating choices. Indeed, the main technical difficulty in our corresponding setting is to show uniqueness of the optimal protocol, which we do in each case where a unique protocol exist.

Nonetheless, despite the differences, the framework of [7] bears some conceptual similarities to ours, e.g., the authors also identify structural protocols (cf. Definition 3.4 below) as the natural notion of strategy for studying their framework. Furthermore, they make extensive use of focal points [18] in analysing how asymmetric histories can be used for coordination.

Relating to uniqueness of protocols, [12] argues that individual rationality considerations not are not sufficient for “learning how to coordinate” in the setting of [7]. We agree with [12] that some conventions are needed if many protocols lead to the optimal result. However—in our framework—as we can prove uniqueness of the optimal protocols for $\mathsf{CM}_{\_}m$ (for $m\neq 4$), then arguably rational players should adopt precisely these protocols in $\mathsf{CM}$-games.

The paper [14] is the preprint of the current submission with full proofs and further examples.

In principle one could of course reduce our arguments into the setting with games presented in matrix form. However, then it would become harder to apply natural graph-theoretic notions like degrees of nodes; special features such as cycles; general symmetries (automorphisms) et cetera. Such notions are key elements in our analysis.

We define (pure) win-lose coordination games as relational structures as follows.

We will use the visual representation of $\mathsf{WLC}$ games as hypergraphs; two-player games become just bipartite graphs under this scheme. The choices of each player are displayed as columns of nodes, starting from the choices of player 1 on the left and ending with the column of choices of player $n$. The winning relation consists of lines that represent the winning choice profiles. Thus winning choice profiles are also called edges. See Example A.1 in [14] for an illustration.

Consider a $\mathsf{WLC}$-game $G=(A,C_{\_}1,\dots,C_{\_}n,W_{\_}G)$ with $n$ players and $m$ winning choice profiles that do not intersect, i.e., none of the $m$ winning choice profiles share a choice $c\in A$. Such games form a simple yet fundamental class of games, where the goal of the players is simply to pick the same “choice”, i.e., to simultaneously pick one of the $m$ winning profiles. These games are called choice matching games. We let $\mathsf{CM}^{n}_{\_}m$ denote the choice matching game with $n$ players and $m$ choices for each player. In this article, we extensively make use of the two-player choice matching games, $\mathsf{CM}^{2}_{\_}m$. For these games, we will omit the superscript “$2$” and simply denote them by $\mathsf{CM}_{\_}m$. (Recall the example $\mathsf{CM}_{\_}3$ pictured in the introduction.)

Interestingly, out of all $n$-player $\mathsf{WLC}$-games where each of the $n$ players has $m$ choices, the game $\mathsf{CM}^{n}_{\_}m$ has the least probability of coordination when each player plays randomly. In this sense these games can be seen the most difficult for coordination. A fully compelling reason for the maximal difficulty of choice matching games is given later on by Theorem 7.3.

A repeated play of a $\mathsf{WLC}$-game $G$ consists of consecutive (one-step) plays of $G$. The repeated play is continued until the players successfully coordinate, i.e., select their choices from a winning choice profile. This may lead to infinite plays. We assume that each player can remember the full history of the repeated play and use this information when planning choices. The history of the play after $k$ rounds is encoded in a sequence $\mathcal{H}_{\_}k$ defined as follows.

A stage $k$ contains a history specifying precisely $k$ choice profiles chosen in a repeated play. A winning profile of $(G,\mathcal{H}_{\_}k)$ is called a touched edge if it contains some choice $c$ picked in some round $1,\dots,k$ leading to $(G,\mathcal{H}_{\_}k)$. As we assume that the players only need to coordinate once, we consider repeated plays only up to the first stage where some winning choice profile is selected. If coordination occurs in the $k$th round, the $k$th stage is called the final stage of the repeated play. (But a play can take infinitely long without coordination.)

[widths=0.85,0.15, sep=5mm, justify=flush, rule=0pt,lines=5] On the right is a drawing of the stage $2$ in a repeated play of $\mathsf{CM}_{\_}2$, the “coordination game variant” of the matching pennies game (or the “pavement tango” from the introduction). Here the players have failed to coordinate in round 1 (having picked the choices with dotted circles) and then failed again by both swapping their choices in round 2 (solid circles).

Since a protocol can depend on the full history of the current stage, it gives a mixed, memory-based strategy for any repeated $\mathsf{WLC}$-game. Thus protocols can informally be regarded as global “behaviour styles" of agents over the class of all repeated $\mathsf{WLC}$-games. It is important to note that all players can see (and remember) the previous choices selected by all the other players—and also the order in which the choices have been made.

In the scenario that we study, it is obvious to require that the protocols should act independently of the names of choices and the names (or ordering) of player roles $i$.¹¹1Note that if this assumption is not made, coordination can trivially be guaranteed in a single round in any $\mathsf{WLC}$-game by using a protocol which chooses some winning choice profile with probability $1$. In [7], this requirement follows from the “assumption of no common language” (for describing the game), and in [11], such protocols are called structural. We shall adopt the terminology of [11]. To extend this concept for repeated games, we first need to define the notion of a renaming. The intuitive idea of renamings is to extend isomorphisms between game graphs—including the history—to additionally enable permuting the players $1,\dots,n$ (see Example A.2 in [14] for an illustration of the definition).

Note that a structural protocol may depend on the full history which records even the order in which the choices have been played. Hereafter we assume all protocols to be structural.

A choice $c$ in a stage $S$ is a focal point if it is not structurally equivalent to any other choice in that same stage $S$, with the possible exception of choices $c^{\prime}$ that all belong to some single edge with $c$. A focal point breaks symmetry and can be used for winning a repeated coordination game. This requires that the players have some (possibly prenegotiated) way to agree on which focal point to use. See the following example for an illustration.

In repeated coordination games, it is natural to try to coordinate as quickly as possible. There are two principal scenarios related to optimizing coordination times: the average case and the worst case. The former concerns the expected number rounds for coordination and the latter the maximum number in which coordination can be guaranteed with certainty.

It is possible that there are several different protocols giving the optimal $\mathsf{ECT}$ (or $\mathsf{GCT}$) for a given $\mathsf{WLC}$-game. If two protocols $\pi_{\_}1$ and $\pi_{\_}2$ are both optimal, it may be that the optimal value is nevertheless not obtained when some of the players follow $\pi_{\_}1$ and the others $\pi_{\_}2$. This leads to a meta-coordination problem about choosing the same optimal protocol to follow. However, such a problem will be avoided if there exists a unique optimal protocol.

The next lemma states that two structurally similar stages are essentially the same stage with respect to different $\mathsf{ECT}$s and $\mathsf{GCT}$s. The proof is straightforward.

In this section we introduce two special protocols, the loop avoidance protocol $\mathsf{LA}$ and the wait-or-move protocol $\mathsf{WM}$. Informally, $\mathsf{LA}$ asserts that in every round, every player $i$ should avoid—if possible—all choices $c$ that could possibly make the resulting stage automorphism-equivalent (cf. Def. 3.5) to the current stage, i.e., the stage just before selecting $c$.

It is easy to see that $\mathsf{LA}$ avoids, when possible, all such stages that are structurally similar to any earlier stage in the repeated play. As structurally similar stages are essentially identical (cf. Lemma 3.9), repetition of such stages can be seen as a “loop” in the repeated play. When trying to guarantee coordination as quickly as possible, such loops should be avoided. In addition to this heuristic justification, Theorems 5.1 and 5.2 give a fully compelling justification for $\mathsf{LA}$ when considering guaranteed coordination in two-player $\mathsf{CM}$-games. For now, we present the following results (for the proofs, see the correspondingly numbered Propositions 4.2 and 4.3 in [14]); see also Example 4.4 below for an illustration of the use of $\mathsf{LA}$.

We next present the wait-or-move protocol $\mathsf{WM}$, which naturally appears in numerous real-life two-player coordination scenarios. Informally, both players alternate (with equal probability) between two choices: the players own initial choice and another choice that coordinates with the initial choice of the other player.

Definition A.5 in [14] specifies $\mathsf{WM}$ in yet further detail. The following theorem shows that $\mathsf{WM}$ is very fast in relation to $\mathsf{ECT}$s. This holds for all two-player $\mathsf{WLC}$-games, not only choice matching games $\mathsf{CM}_{\_}m$. (The claim is validated by the proof of Proposition 4.5 in [14].)

It follows from the proof of Theorem 4.6 that the $\mathsf{ECT}$ with $\mathsf{WM}$ is exactly $3-\frac{2}{m}$ in all choice matching games $\mathsf{CM}_{\_}m$. Thus the last claim of the theorem cannot be improved, as the $\mathsf{ECT}$s of the games $\mathsf{CM}_{\_}m$ grow asymptotically closer to the strict upper bound $3$ when $m$ is increased. In the particular case of $\mathsf{CM}_{\_}2$, the $\mathsf{ECT}$ with $\mathsf{WM}$ is $3-\frac{2}{2}=2$. Thus the following clearly holds.

$\mathsf{WM}$ eventually leads to coordination with asymptotic probability $1$ in all two-player $\mathsf{WLC}$-games. But it does not guarantee (with certainty) coordination in any number of rounds in $\mathsf{WLC}$-games where the winning relation is not the total relation. In a typical real-life scenario, eternal non-coordination is of course impossible by $\mathsf{WM}$, but it is conceivable, e.g., that two computing units using the very same pseudorandom number generator will never coordinate due to being synchronized to swap their choices in precisely the same rounds.

It is easy to show that $\mathsf{WM}$ is the unique protocol which gives the optimal $\mathsf{ECT}$ (namely, 2 rounds) in the “droitwich-scenario” of the game $\mathsf{CM}_{\_}2$ (see the proof of Proposition 4.8 in [14]).

Next we compare the pros and cons of $\mathsf{LA}$ and $\mathsf{WM}$ in two-player $\mathsf{CM}$-games. Recall that $\mathsf{WM}$ does not guarantee coordination in $\mathsf{CM}_{\_}m$ (when $m\not=1$), while $\mathsf{LA}$ does guarantee coordination in $\mathsf{CM}_{\_}m$ if and only if $m$ is odd. Concerning expected coordination times, it is easy to prove that $\mathsf{WM}$ gives a smaller $\mathsf{ECT}$ than $\mathsf{LA}$ in $\mathsf{CM}_{\_}m$ for all even $m$ (except for the case $m=2$, where $\mathsf{WM}$ and $\mathsf{LA}$ behave identically). Thus we now restrict attention to the games $\mathsf{CM}_{\_}m$ with odd $m$. Then, the probability of coordinating in the $\ell$-th round of $\mathsf{CM}_{\_}m$ using $\mathsf{LA}$, with $\ell\leq\lceil m/2\rceil$, can relatively easily be seen to be calculable by the formula $P_{\_}{\ell,m}$ defined below (where the product is $1$ when $\ell=1$). And using the formula for $P_{\_}{\ell,m}$, we also get a formula for the expected coordination time $E_{\_}m$ in $\mathsf{CM}_{\_}m$ with $\mathsf{LA}$:

Using this and Theorem 4.6, we can compare the $\mathsf{ECT}$s in $\mathsf{CM}_{\_}m$ with $\mathsf{LA}$ and $\mathsf{WM}$ for odd $m$ (see the following table).

Especially the case $m=7$ is interesting, as the $\mathsf{ECT}$ with $\mathsf{LA}$ is exactly 3 which is precisely the strict upper bound for the $\mathsf{ECT}$s with $\mathsf{WM}$ for the class of all two-player choice matching games $\mathsf{CM}_{\_}m$. Furthermore, $m=7$ is the case where $\mathsf{WM}$ becomes faster than $\mathsf{LA}$ in relation to $\mathsf{ECT}$s. Thus $\mathsf{WM}$ clearly stays faster than $\mathsf{LA}$ for all $m\geq 7$, including even values of $m$.

In this section we investigate when coordination can be guaranteed in two-player $\mathsf{CM}$-games and which protocols give the optimal $\mathsf{GCT}$ for them. The following result is a direct consequence of the symmetries of $\mathsf{CM}_{\_}m$ for even $m$ (see the proof of Proposition 5.1 in [14]):

We then consider choice matching games $\mathsf{CM}_{\_}m$ with an odd $m$. Proposition 4.3 showed that the $\mathsf{GCT}$ with $\mathsf{LA}$ in these games is $\lceil m/2\rceil$. The next theorem shows that this is the optimal $\mathsf{GCT}$ for $\mathsf{CM}_{\_}m$, and moreover, $\mathsf{LA}$ is the unique protocol giving this $\mathsf{GCT}$. The proof of Theorem 5.2 is an interesting exercise in the optimally fast elimination of automorphisms.

In this section we investigate which protocols give the best $\mathsf{ECT}$s for two-player choice matching games. We also investigate when the best $\mathsf{ECT}$ is obtained by a unique protocol. We already know by Propositions 4.8 and 4.2 that the optimal $\mathsf{ECT}$s for $\mathsf{CM}_{\_}2$ and $\mathsf{CM}_{\_}3$ are uniquely given by $\mathsf{WM}$ and $\mathsf{LA}$, respectively. Thus it remains to consider the games $\mathsf{CM}_{\_}m$ with $m\geq 4$. We first cover the case $m\geq 6$ and show that then $\mathsf{WM}$ is the unique protocol giving the best $\mathsf{ECT}$. The remaining special cases $m=4$ and $m=5$ will then be examined. The following auxiliary lemma (proven in [14]) will be used in the proofs.

We are now ready to cover the case for choice matching games $\mathsf{CM}_{\_}m$ with $m\geq 6$.

We then cover the case for $\mathsf{CM}_{\_}5$. The argument is similar to the case for $\mathsf{CM}_{\_}m$ with $m\geq 6$, but this time leads to the use of $\mathsf{LA}$ instead of $\mathsf{WM}$.