Paper deep dive
Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games
Ian Gemp, Crystal Qian, Marc Lanctot, Kate Larson
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 7/8/2026, 11:55:45 AM
Summary
This paper introduces a generalized framework for Nash equilibrium called the Context-Ordinal Nash Equilibrium (CO-NE), which operates without numerical utility functions by relying solely on ordinal player preferences. By leveraging social choice theory and doubly probabilistic voting rules to define best responses, the authors establish the existence of CO-NE under mild conditions using Kakutani's fixed-point theorem. They further introduce regularization techniques to ensure continuity and develop learning algorithms like Follow The Regularized Leader (FTRL) to compute these equilibria, demonstrating their applicability to human preference data in experimental settings.
Entities (12)
Relation Signals (10)
Google DeepMind → affiliationof → Ian Gemp
confidence 99% · Ian Gemp Google DeepMind New York, NY USA
Ian Gemp → authorof → Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games
confidence 99% · Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games Ian Gemp Google DeepMind
Context-Ordinal Game → generalizes → Nash Equilibrium
confidence 97% · In this work, we forgo precise utilities and generalize the Nash equilibrium to a setting where we only assume a player is capable of providing an ordinal ranking of their actions
Context-Ordinal Nash Equilibrium → definedusing → Social Choice Theory
confidence 96% · we naturally look towards social choice theory for how to aggregate preferences to identify the most preferred actions. We define this generalized notion of a context-ordinal Nash equilibrium
Kakutani's Fixed-Point Theorem → provesexistenceof → Context-Ordinal Nash Equilibrium
confidence 95% · Theorem 1 (Kakutani 1941). If each BRi is u.h.c., then an NE exists in mixed strategies.
Doubly Probabilistic Social Choice Function → defines → Best Response
confidence 94% · Player ii’s best response, BRi(x−i), is the result of the dpSCF voting rule νi on this population of votes.
Regularization → appliedto → Best Response
confidence 93% · We set μi=1/|𝒜i|𝟏 always. A regularized best-response in COGs should satisfy the following desiderata for every x−i
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Nash equilibrium serves as a fundamental mathematical tool in economics and game theory. However, it classically assumes knowledge of player utilities, whereas economics generally regards preferences as more fundamental. To leverage equilibrium analysis in strategic scenarios, one must first elicit numerical utilities consistent with player preferences, a delicate and time-consuming process. In this work, we forgo precise utilities and generalize the Nash equilibrium to a setting where we only assume a player is capable of providing an ordinal ranking of their actions within the context of other players' joint actions. The key technical challenge is to rethink the definition of a best-response. While the classical definition identifies actions maximizing expected payoff, we naturally look towards social choice theory for how to aggregate preferences to identify the most preferred actions. We define this generalized notion of a context-ordinal Nash equilibrium, establish its existence under mild conditions on aggregation methods, introduce notions of regularization, approximation, and regret, explore complexity for simple settings, and develop learning rules for computing such equilibria. In doing so, we provide a generalization of Nash equilibrium and demonstrate its direct applicability to elicited preferences in human experiments.
Tags
Links
- Source: https://arxiv.org/abs/2605.07996v1
- Canonical: https://arxiv.org/abs/2605.07996v1
Trouble viewing inline? Open PDF directly →
Full Text
104,520 characters extracted from source content.
Expand or collapse full text
Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games Ian Gemp Google DeepMind New York, NY, USA imgemp@google.com &Crystal Qian Google DeepMind New York, NY USA cjqian@google.com Marc Lanctot Google DeepMind Montreal, CA lanctot@google.com &Kate Larson Google DeepMind & University of Waterloo Waterloo, CAN katelarson@google.com Abstract Nash equilibrium serves as a fundamental mathematical tool in economics and game theory. However, it classically assumes knowledge of player utilities, whereas economics generally regards preferences as more fundamental. To leverage equilibrium analysis in strategic scenarios, one must first elicit numerical utilities consistent with player preferences, a delicate and time-consuming process. In this work, we forgo precise utilities and generalize the Nash equilibrium to a setting where we only assume a player is capable of providing an ordinal ranking of their actions within the context of other players’ joint actions. The key technical challenge is to rethink the definition of a best-response. While the classical definition identifies actions maximizing expected payoff, we naturally look towards social choice theory for how to aggregate preferences to identify the most preferred actions. We define this generalized notion of a context-ordinal Nash equilibrium, establish its existence under mild conditions on aggregation methods, introduce notions of regularization, approximation, and regret, explore complexity for simple settings, and develop learning rules for computing such equilibria. In doing so, we provide a generalization of Nash equilibrium and demonstrate its direct applicability to elicited preferences in human experiments. 1 Introduction Game theory seeks to define rational (utility-maximizing) behavior in the presence of rational co-players. However, not all strategic scenarios admit precise numerical utilities. In elections, for instance, voters may strategically cast ballots in order to achieve desired election results. One can imagine pursuing tactical voting without ever ascribing any precise numerical value to each electoral outcome. We later study human data from such settings in experiments. The dominant solution concept in game theory is the notion of a Nash equilibrium (NE), a strategy profile from which no single player has any incentive to deviate [50]. Traditionally, an incentive to deviate would mean that a player has an opportunity to take an action that achieves higher expected utility. However, how can one compute an expected utility in a setting where numerical utilities are not available? 25% 30% 45% \ ≻ ≻ \\ ≻ ≻ \\ ≻ ≻ \Opp. Strategy Our vote when opp. plays Figure 1: An NE is a strategy profile where each player best responds to its co-players. In a game without payoffs, but where players can rank their actions, we use social choice (voting) theory to define a best response. Consider playing an opponent in rock-paper-scissors ( , , ); their mixed strategy is [25%,30%,45%][25\%,30\%,45\%]. When the opponent plays, e.g., , our rank vote over our own actions is \ ≻ ≻ \. Imagine a population of votes with representation proportional to the opponent’s mixed strategy—25%25\% of the votes are \ ≻ ≻ \, 30%30\% are \ ≻ ≻ \, etc. We define a best response as the outcome of a voting rule on this population. For example, Borda elects as our best response. Instead of assuming access to numerical utilities, one can more generally assume each player is capable of ranking the possible outcomes [24]. Given the other players play a deterministic strategy, a rational player would simply deviate to the action that results in the outcome they most prefer. Any utility function one might elicit through careful measurement would also achieve its maximum for that action, and so we can still consider the player to be utility-maximizing despite the lack of utilities. Unfortunately, it is unclear how to translate this notion in the case where co-players’ strategies are mixed (i.e., randomized). Previous work has either switched from using probability theory to possibility theory [6] or introduced an additional, disinterested player to recover a mediated equilibrium [23]. Neither is able to recover a Nash equilibrium under a traditional probabilistic framework. A critical obstacle towards defining a Nash equilibrium in this setting is how to aggregate ordinal outcomes under mixed (probabilistic) strategies. In this work, we look towards a field that has spent centuries studying the problem of preference aggregation, a veritable “mathematics without numbers” [40], namely social choice theory. With this viewpoint, we successfully construct a notion of a mixed Nash equilibrium called a context-ordinal Nash equilibrium that generalizes the classical definition. An example of a context-ordinal equilibrium is depicted and explained in Figure 1. Given this new definition, many questions emerge. We establish its existence under mild conditions on aggregation (voting) rules, introduce notions of regularization, approximation, and regret, study complexity for simple settings, and develop learning rules for computing such equilibria. In doing so, we provide a generalization of Nash equilibrium that can be directly applied to elicited preferences, the fundamental data of human interactions, which we demonstrate in two experiments: (i) general agent evaluation in Arcade, and (i) empirical analysis of ranked-choice human leader selection (Lost at Sea, [15, 54]). 2 Background & Related Work First, we review background on classical non-cooperative game theory, social choice, and prior models of equilibria assuming access to only player preferences. 2.1 Non-Cooperative Game Theory A classical normal-form game (NFG) is a tuple ⟨,=(×i=1ni),u=(u1,…,un)⟩ ,A=( * _i=1^nA_i),u=(u_1,…,u_n) where =1,…,nN=\1,…,n\ is the set of players, iA_i is player i’s finite set of actions, and ui:→ℝu_i:A is player i’s utility function. Players may randomize over their action sets, that is, play mixed strategies: i=ΔiX_i= ^A_i. Their utility functions naturally extend to this domain using expected value: ui:=(×j=1nj)→ℝ=∼[ui()]u_i:X=( * _j=1^nX_j) =E_ a x[u_i( a)] where ∈ x and ∈ a . Let x−ix_-i denote the mixed strategy profile for players not i. A Nash equilibrium (NE) is a profile x from which no player has any incentive to deviate: ui()≥ui(z,x−i)∀i,z∈iu_i( x)≥ u_i(z,x_-i)\,\,∀\,\,i,z _i. Equivalently, each player’s strategy is a best response: xi∈BRi(x−i)=argmaxz∈iui(z,x−i)∀i. x_i∈ BR_i(x_-i)= *arg\,max_z _iu_i(z,x_-i)\,\,∀\,\,i. (1) 2.2 Social Choice (Voting) Theory Much of social choice theory studies procedures for aggregating voter preferences over alternatives such that desirable axioms are satisfied [18]. The syntax a≻a′a a indicates a voter strictly prefers a to a′a ; a⪰a′a a , weakly prefers. A voter is indifferent between the two if a′⪰a a and a⪰a′a a , abbreviated a∼a′a a . Each voter specifies all their preferences with a preference relation ρ. The set of all possible preference relations over a set of alternatives A is ()P(A). A voting rule that determines the “winner(s)” (a non-empty subset, possibly with ties), is a social choice function (SCF). One that returns a ranking over the alternatives is a social welfare function (SWF). An SWF can be converted to an SCF by selecting the subset that achieves the top-rank. A probabilistic SCF (pSCF) returns a distribution (lottery) over alternatives. An SCF can be converted to a pSCF by converting its output to a lottery with probability mass only on the winners. In addition, we assume a voting rule can take as input a lottery over possible votes, rather than the actual set of voters’ votes. For example, if the set of votes is (a≻a′,a≻a′,a≺a′)(\a a \,\a a \,\a a \) for three voters and two alternatives a and a′a , then a voting rule can also accept the lottery [2/3:a≻a′,1/3:a′≻a][2/3:\a a \,1/3:\a a\]. We call these doubly probabilistic SCFs (Def. 2). For intuition, we sometimes explain this concept using an infinite population of votes, each distinct vote (ballot) occurring with a given frequency. For example, Fig. 1 shows ballot \ ≻ ≻ \ occurring in 30%30\% of votes. 2.3 Ordinal Games and Equilibria Ordinal games [24] forgo numerical payoffs and instead assume each player can rank all joint outcomes, e.g., player 11 of 22 would rank (R,S)∼(S,P)∼(P,R)≻(R,R)∼(P,P)∼…(R,S) (S,P) (P,R) (R,R) (P,P) ... in rock-paper-scissors. Cruz and Simaan [24] proposed a notion of approximate equilibrium for 22-player ordinal games parameterized by order m,n\m,n\, indicating that player 11 (22) seeks their mmth (nnth) ranked action when deviating. A traditional pure strategy NE in an ordinal game is equivalent to a 1,1\1,1\-NE; such an NE is not guaranteed to exist though. Conitzer [23] raises the issue of defining mixed NE in ordinal games and conjectures that it “cannot be done without access to cardinal utilities”. Instead, Conitzer [23] leverages the folk theorems in infinitely repeated games to construct an equilibrium that is consistent with both repeated games and mediated games. This mediated equilibrium is specified with a joint distribution x and correlated co-player distribution x−ix_-i for every player i. These equilibria are proven to be robust in the sense that for any utility function that satisfies the ordinal constraints of the game, the pair x and (x−i)i(x_-i)_i remains a mediated equilibrium. Other work defines mixed strategies in terms of possibility distributions rather than probability distributions [6]. A possibilistic mixed strategy maps each action to an ordinal scale that can be interpreted as a preference or likelihood toward playing that action. A corresponding mixed NE can then be defined in terms of mixed possibilistic strategies. In contrast to the mediated equilibrium, we aim to define a single factorized equilibrium profile =(x1,…,xn) x=(x_1,…,x_n). And in contrast to the possibilistic framework, we will define mixed strategies traditionally as probability distributions. In addition, it is unclear how any of the frameworks above might handle noisy ordinal preferences, a practically important scenario we explore later in a stochastic Condorcet election domain. Lastly, both frameworks assume the ordinal game (OG) setting [24], which we argue 1) is over-specified for the purposes of defining a suitable NE concept and 2) is unnatural when a player’s actions are incomparable under different co-player action profiles (see Sec 5.1). 3 Context-Ordinal Games & Equilibria To ascertain if a player would want to alter their strategy from a purported equilibrium, we only need to look at their possible choices, assuming their co-players’ strategies remain fixed. In particular, it is not essential, as in an OG, to know how a player i might want their co-players to change their strategies to benefit them (i). This leads us to the idea of a context-ordinal game (COG), where each player ranks possible outcomes given actions chosen by everyone else. We encourage the reader to consult Fig. 1 before continuing. Definition 1 (Context-Ordinal Game). A context-ordinal game (COG) is a tuple ⟨,=(×i=1ni),ρ⟩ ,A=( * _i=1^nA_i),ρ where =1,…,nN=\1,…,n\ is the set of players, iA_i is player i’s finite set of actions, and ρ=ρ1,…,ρnρ=\ _1,…, _n\ contains each player’s conditional preference relation. Each ρi:×j≠inj→(i) _i: * _j≠ i^nA_j (A_i) maps the co-players’ joint action to player i’s preferences over iA_i. For a strategy profile to be a Nash equilibrium, each player’s strategy must be a best response to the remaining players. We generalize the argmax *arg\,max in (1) to mean any distribution over the player’s actions that “tie” for top-ranked according to a social choice rule (a doubly pSCF). Definition 2 (Doubly Probabilistic SCF). A doubly pSCF (dpSCF) is a correspondence ν:Δ(i)→2Δiν: ^P(A_i)→ 2 ^A_i from a lottery over votes to a convex set of distributions over actions. The next definition is the key to defining our mixed Nash equilibrium concept. Definition 3 (Best Response with Social Choice). Player i’s co-players play a−ia_-i with probability x−i(a−i)x_-i(a_-i). For each a−ia_-i played, player i conditionally specifies preferences ρi(a−i) _i(a_-i) over their actions iA_i, referred to as a “vote”111If preferences are stochastic, the vote itself may be represented as a lottery over votes.. Let vi(x−i)v_i(x_-i) be the resulting population of votes where each vote ρi(a−i) _i(a_-i), occurs with probability x−i(a−i)x_-i(a_-i). Player i’s best response, BRi(x−i) BR_i(x_-i), is the result of the dpSCF voting rule νi _i on this population of votes. The following NE definition is standard. Our primary innovation is Def. 3 of a best response. Definition 4 (Context-Ordinal Nash Equilibrium). A strategy profile x is a context-ordinal Nash equilibrium (CO-NE) iff xi∈BRi(x−i)x_i∈ BR_i(x_-i) for all i. In words, x is an NE if every player’s mixed strategy only places mass on winning candidate actions. See Appx. A.3 for a definition of a correlated equilibrium. Our definition is naturally robust to mis-specification of utilities (assuming they exist), a key focus of [23]. The underlying utilities are allowed to change as long as the partial ranking of actions does not. Because our definition only observes the partial ranking, the NE is invariant to these changes in utility. 3.1 Existence of Mixed Context-Ordinal NE The social choice best response operator BRi BR_i for each player i maps from a partial profile x−ix_-i to a non-empty, convex subset of the simplex. Denote upper hemicontinuous by u.h.c. Theorem 1 (Kakutani 1941). If each BRi BR_i is u.h.c., then an NE exists in mixed strategies. A set-valued mapping BRi BR_i is u.h.c. if for every convergent sequence of co-player strategies x−itt\ [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i^t\_t, e.g., the distribution over votes illustrated in Fig. 1, and for any convergent sequence of player i’s best responses xitt\ [rgb]0.2578125,0.5234375,0.95703125 [named]pgfstrokecolorrgb0.2578125,0.5234375,0.95703125x_i^t\_t with xit∈BRi(x−it) [rgb]0.2578125,0.5234375,0.95703125 [named]pgfstrokecolorrgb0.2578125,0.5234375,0.95703125x_i^t∈ BR_i( [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i^t), the limt→∞xit _t→∞ [rgb]0.2578125,0.5234375,0.95703125 [named]pgfstrokecolorrgb0.2578125,0.5234375,0.95703125x_i^t lies in BRi(limt→∞x−it) BR_i( _t→∞ [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i^t). Traditional SCFs may exhibit discontinuities in their elected candidates as the population of votes slightly changes. By considering the distributions returned by dpSCFs, we can more naturally study their u.h.c. properties. The u.h.c. definition handles subtleties that arise, for example, when the distribution of votes changes from one that prefers candidate A to one in which candidate A and B are tied. In the latter case, any distribution over A and B is valid and samples a suitable winning candidate: BRi(limt→∞x−it)=[z,1−z],z∈[0,1] BR_i( _t→∞ [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i^t)=[z,1-z],z∈[0,1]. And if the limit of the winning candidate distribution specifically selected A (limt→∞xit=[1,0] _t→∞ [rgb]0.2578125,0.5234375,0.95703125 [named]pgfstrokecolorrgb0.2578125,0.5234375,0.95703125x_i^t=[1,0]), that would still satisfy the u.h.c. condition because A is in the set of valid candidate distributions. We identify several u.h.c. families of voting rules: a) score voting where each vote assigns candidates numerical scores and the candidate with highest (x−ix_-i-weighted) score wins, b) positional voting [56], e.g., Borda counts, c) probabilistic voting [17], e.g., maximal lotteries [30, p. 30], d) and social grading functions [10]. Scoring and positional voting rules induce normal-form games. Classical NE implicitly uses score voting (see Appx. A.2) where voters score candidate actions with their precise payoffs. Later we introduce regularized best responses, rendering any dpSCF voting rule u.h.c. and ensuring existence of their NE. Complexity of CO-NE In Appx. D, we study complexity of CO-NE and show that there exist intuitively adversarial 22-player games that when studied under simple voting rules (e.g., Borda counts) map to normal-form games that are not zero-sum. The implication is that CO-NE are not polynomial-time computable. Whereas prior work sought to define equilibria of ordinal games that lie in P at the expense of a departure from traditional representation, our aim is to define an equilibrium notion that generalizes Nash: probabilistic, factorizes, and gracefully reduces to classical NE under assumptions, e.g., score voting where score==utility. 4 Learning and Approximation Gradient descent serves as the workhorse of learning in games. Its interpretation as a proximal operator is important here because it allows us to view (projected) gradient descent as the solution to a regularized optimization problem. This view appears in related algorithms like follow the regularized leader [48, 59] and mirror descent as well [11]: xi′=Πi[xi+η∇xiui(xi,x−i)] x_i = _X_i[x_i+η _x_iu_i(x_i,x_-i)] =argmaxz∈iui(z,x−i)−12η‖z−xi‖2 = *arg\,max_z _iu_i(z,x_-i)- 12η||z-x_i||^2 (2) where xi′x_i denotes the next iterate, Πi _X_i denotes the Euclidean projection onto the set iX_i, and η is a step size parameter (equiv., inverse regularization coefficient). Convergence of gradient descent is typically analyzed in terms of the successive distance between iterates, ‖xi′−xi‖||x_i -x_i||. Notice that in unconstrained settings when the projection operator acts as an identity, this simplifies to ‖η∇xiui(xi,x−i)‖||η _x_iu_i(x_i,x_-i)|| and is hence proportional to the norm of the gradient. Gradient norms are used as both performance metrics and constructing loss functions to develop other algorithms [33]. It should not come as a surprise then that our first task is to replicate a technique to regularize our best response definition. Doing so will provide us with methods for learning as well as metrics to measure performance of those learning algorithms. 4.1 Regularization of Best Responses 1. x^−i∼Dir(+1qx−i) [rgb]1,0.6484375,0 [named]pgfstrokecolorrgb1,0.6484375,0 x_-i \! (1+ 1q [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i ) 2. ∼Cat(μi)\; ( _i) 3. H∼Bern(p)\; (p) 22% 31% 47% \ ≻ ≻ \\ ≻ ≻ \vu=v_u=\ ≻ ∼ \\ ≻ ≻ \THT Figure 2: Algorithm 1 applied to the example from Fig. 1. Step 1: Original co-player strategy x−i=[25%,30%,45%]x_-i=[25\%,30\%,45\%] is perturbed via x^−i x_-i ∼Dir(+1q (1+ 1q x−ix_-i)), yielding [22%,31%,47%][22\%,31\%,47\%]; as q→0q→ 0, x^−i→x−i [rgb]1,0.6484375,0 [named]pgfstrokecolorrgb1,0.6484375,0 x_-i→ [rgb]0.91796875,0.26171875,0.20703125 [named]pgfstrokecolorrgb0.91796875,0.26171875,0.20703125x_-i. Step 2: A usurper action u=u= is sampled from Cat(μi)Cat( _i), giving vu=v_u=\ ≻ ∼ \ with top-ranked and all others tied. Step 3: Each vote is independently replaced by vuv_u with probability p (coin flip). When p=0p=0 the population is unchanged; when p=1p=1 all votes become vuv_u. A voting rule νi _i determines a best response from this perturbed population. Results are averaged over trials to obtain the final regularized best response. Regularization is a useful tool in game theory for selecting equilibria [47, 36], aiding convergence [52], imitating target play [34, 8], and online learning (FTRL) [57]. An exemplar is KL-divergence: KL(μ∥x)=∑μ(a)log(μ(a)/x(a)) KL(μ x)= _Aμ(a) (μ(a)/x(a)), which measures how much an approximate distribution x differs from a true distribution μ. The reverse KL, KL(x∥μ) KL(x μ) was used in [7] to regularize learned strategies in Diplomacy towards recorded human play. Given that COGs lack utilities, making how to achieve direct regularization unclear, we take the approach of regularizing via random perturbation. Let BRi(p,q,μi)BR_i^(p,q, _i) denote the regularized best response operator parameterized by target distribution μi∈Δi _i∈ ^A_i, perturbation hyperparameter q≪1q 1, and regularization strength p∈[0,1]p∈[0,1]. We set μi=1/|i| _i= 1|A_i|1 always. A regularized best-response in COGs should satisfy the following desiderata for every x−ix_-i: (C1) Maximum regularization (p=1p=1) results in μi _i for any target distribution μi _i; (C2) Zero regularization (p=0p=0) returns an element of BRi BR_i from Def. 3; (C3) Any regularization results in a single-valued best response; (C4) The regularized best response is a continuous function of x−ix_-i. For clarity, we use a concrete example in Fig. 2 to describe our approach which satisfies the above conditions and defer Algorithm 1 and a more rigorous discussion to Appx. B. Next, we will leverage regularization to construct notions of approximation and regret in COGs. Later in Section 5, we also use it to construct algorithms, e.g., FTRL, to approximate context-ordinal Nash equilibria in experiments. Appx. F reviews learning algorithms. 4.2 Performance Metrics Approximate Nash equilibria are most often judged on how much any player can gain by deviating, referred to as exploitability, ϵ=maxiϵiε= _i _i, where: ϵi() _i( x) =maxz∈Δiui(z,x−i)−ui(), = _z∈ ^A_iu_i(z,x_-i)-u_i( x), (3) and ϵi _i is sometimes referred to as immediate regret. That is because of the tight connection between game theory and online learning [35]. (External) regret for a sequence of strategies [xi,t]t∈[1,T][x_i,t]_t∈[1,T] measures exploitability over T rounds of play: maxz∈Δi∑t=1Tui(z,x−i,t)−ui(t) _z∈ ^A_i _t=1^Tu_i(z,x_-i,t)-u_i( x_t). COGs do not provide utilities so we explore alternative notions of approximation and regret. 4.2.1 Strategy Space We can measure a distance to NE in strategy space as ϵ=maxiϵiε= _i _i, ϵi(x) _i(x) =minz∈BRi(x−i)D(z,xi) = _z∈ BR_i(x_-i)D(z,x_i) (4) and D is continuous and non-negative. For example, D could be earth mover’s distance which results in ϵi _i summing the amount of probability mass that player i has placed on strictly losing candidates. As defined, this function may be discontinuous because of jumps in the u.h.c. best response set BRi BR_i. We can replace the feasible set by the regularized best response BRi(p,q,μi) BR_i^(p,q, _i) which is continuous. By Berge’s maximum theorem [5, Theorem 17.31], ϵi(p,q,μi)() _i^(p,q, _i)( x) =minzi∈BRi(p,q,μi)(x−i)D(zi,xi) = _z_i∈ BR_i^(p,q, _i)(x_-i)D(z_i,x_i) (5) is continuous in x. Figure 5 in Appx. E illustrates this measure for the classic Chicken game. While this measure is suitable for immediate regret, it is unclear how to extend it to regret which evaluates a sequence of strategies. (a) Exploitability (b) Hindsight Winrate Figure 3: We evaluate our (SGF-based) FTRL approach (psp_s indicates the solver’s BRi(ps,q,μi) BR_i^(p_s,q, _i) parameter) on the Atari evaluation game according to the metrics in Section 4.2. (3(a)) EMD as defined in Section 4.2.1 with p=0p=0, eqn. (5); (3(b)) Hindsight winrate from Section 4.2.2. Panel (3(b)) sets ps=1/t+1p_s= 1t+1. FTRL can also be considered a smoothed-FP approach [29]. 4.2.2 Meta-Game Analysis Another choice directly asks “would you prefer to have played a fixed zi∗z_i^* in hindsight?” To define the best fixed zi∗z_i^* in hindsight, simply collect all the “votes” generated at each round t by the co-players in proportion to their strategies x−i,tx_-i,t. Use the (dpSCF) voting rule to aggregate the votes across all rounds and return the best probabilistic strategy zi∗z_i^*. To measure the regret, consider the same sequence of co-player strategies as before, but apply the voting rule, only considering the hindsight and online actions in proportion to their appearance in their mixed strategies. For example, if at t=t′t=t , zi∗=[1,0]z_i^*=[1,0] and xi,t′=[0.5,0.5]x_i,t =[0.5,0.5], in proportion to each a−i∼x−ia_-i x_-i played at time t′t , generate two votes with equal representation: the first action compared against itself and the first action against the second. As before, collect all of the generated votes and apply the voting rule (equiv. best response operator BRi BR_i) to determine the winner. We present the probability of hindsight being selected by BRi(p,q=0.1,μi=[1/2,1/2]) BR_i^(p,q=0.1, _i=[ 12, 12]) in Figure 3(b) over iterations. In Appx. E.2, we explore one more additional metric derived from the social choice perspective, namely margin of victory, which measures the proportion of votes (x−ix_-i) that must be altered for a given strategy xix_i to become a best response xi∈BRi(x−i)x_i∈ BR_i(x_-i). 4.3 Approximating Classical Nash Equilibria The focus of this work is on games with only revealed ordinal preferences. Nevertheless, one might still hope to approximate a classical NE of the game that is defined by hidden cardinal utilities. We obtain non-trivial approximation bounds for that setting by appealing to results from the study of distortion within social choice. Let ui⊳ρiu_i _i mean any utility uiu_i consistent with preferences ρi _i. Then the (additive ++) distortion of a voting rule νi _i, d+(νi) d^+( _i) =maxρi,maxui⊳ρi[ui()−ui(BRi,x−i)], = _ _i, x _u_i _i[u_i( x)-u_i( BR_i,x_-i)], (6) captures the cost of electing candidates using ordinal information instead of voters’ more nuanced cardinal utilities (ordinal information is assumed consistent with utilities). It is typically assumed that each voter attributes cardinal utilities to candidates such that they are non-negative and sum-to-11, “one person, one vote” [53]. This property does not generally hold in games—a player’s payoffs do not sum-to-11 under each possible co-player action a−ia_-i. Nevertheless, equilibria are invariant to affine transformations of payoffs, so we can shift and scale each player’s payoffs such that they are all non-negative with positive sum. This still leaves varying payoff-sums ( s), but we can recover a bound on the suboptimality of the best responses computed using voting rules versus expected payoff maximization. Theorem 2. Let νi _i be a dpSCF voting rule and BRi BR_i its induced best response (Def. 3). Let d+(νi,ui,x−i)=maxzui(z,x−i)−ui(BRi,x−i)≥0d^+( _i,u_i,x_-i)= _zu_i(z,x_-i)-u_i( BR_i,x_-i)≥ 0 denote the suboptimality of the best response to x−ix_-i computed using νi _i. Finally, let (ui)=∑ai∈iui(ai,a−i)a−i∈−i s(u_i)=\ _a_i _iu_i(a_i,a_-i)\_a_-i _-i denote the set of player i’s payoff sums under each co-player action profile. Then d+(νi,ui,x−i) d^+( _i,u_i,x_-i) ≤d¯+(νi,(ui))=κ++(minksk)d+(νi) ≤ d^+( _i, s(u_i))=κ^++( _ks_k)d^+( _i) (7) where κ+=(maxksk−minksk)κ^+=( _ks_k- _ks_k) and d+(νi)d^+( _i) is the additive distortion νi _i from (6). Theorem 3 shows our regularized best response BRi(p,q,μi) BR_i^(p,q, _i) only introduces an additional distortion to d+(νi)d^+( _i) that is at most linear in p for small p. We similarly derive a multiplicative bound d(νi,ui,x−i)=maxzui(z,x−i)ui(BRi,x−i)≤κd(νi)d( _i,u_i,x_-i)= _z u_i(z,x_-i)u_i( BR_i,x_-i)≤κ d( _i) where κ=maxkskminkskκ= _ks_k _ks_k. There exist voting rules νi _i that guarantee additive distortion of 1/4≤d+(νi)≤1/2(1−1/|i|2) 14≤ d^+( _i)≤ 12(1- 1|A_i|^2) and achieve ~(|i|) O( |A_i|) for multiplicative distortion d(νi)d( _i) [21]. One of the earliest decentralized learning algorithms, (weakened) fictitious-play (WFP), iterates by approximately best responding to the co-player’s historical play. The upper bound on the approximation error just derived in Theorem 2 can be used to directly derive bounds on the approximation error of an equilibrium computed using WFP. Corollary 1 (Theorem 1 [22]). The WFP profile T=[xT(1),xT(2)] x_T=[x^(1)_T,x^(2)_T] after T rounds is an ϵT _T-NE where ϵT≤T+12T+T−12Tmaxid¯+(ν,(ui)) _T≤ T+12T+ T-12T _i d^+(ν, s(u_i)). Shift and scale the payoffs w.l.o.g. so that maxksk=1 _ks_k=1. Theorem 2 combined with Corollary 1 and the known distortion bounds listed above imply there exists a voting rule ν such that FP converges to, at worst, a (1−1/4minksk)(1- 14 _ks_k)-NE in 22-player general-sum. Note that 1/2 12 is the known lower bound for approximating NE with constant size support [26]. With only access to ordinal feedback, FP achieves 3/4 34 for minksk=1 _ks_k=1, a loss of 1/4 14 in expected payoff. Recent work provides algorithms for approximating coarse correlated equilibria assuming player’s rankings over actions are drawn according to a Placket-Luce model consistent with true underlying utilities [43]. This allows them to estimate the utilities by observing sampled rankings, i.e., invert the model. In contrast, we do not assume it is possible to discover the underlying utilities. For example, if a user deterministically reveals their preferences to be a single ranking, we can never learn the gaps in utility between actions. Our aim in this work is to develop a theory that natively handles ordinal information without (implicitly) working with any presumed underlying cardinal information. (a) Agent Marginals (b) Game Marginals (c) Agent Marginals Diffs Figure 4: Atari: We present two different CO-NEs computed using the FTRL-inspired approach: (SGF-NE) both agents use social grading functions and (SGF/Borda-NE) where the task agent instead uses Borda. We compare them to the NE of an agent vs task performance matrix with scores normalized to [0,1][0,1] as in [9]. Figure 4(c) supports convergence of our FTRL-inspired solver. Figure 3 displays additional performance information for the SGF-NE approach. 5 Applications We demonstrate our theory in two different domains: a) game-theoretic evaluation of AI agents and b) a tactical voting setting with stochastic election outcomes and preferences. 5.1 General Agent Evaluation in the Arcade Learning Environment We consider a game-theoretic [9, 44, 45] evaluation experiment with Atari agent vs task performance data [37, Table 5] (c.f. Figure 7). In this setting, the performance matrix A plays the role of the payoff matrix in a zero-sum bi-matrix game: minxmaxyx⊤Ay _x _yx Ay where x (y) is the distribution over agents (tasks). The solution surfaces a distribution over agents that is robust against an adversarially chosen task distribution (NE-Norm in Figure 4). We instead run a version of FTRL (FTPL) [48, 59] using our proposed regularized best response. We use social grading functions (SGF-NE) as the voting rule and assign each agent one of four grades on a task based on quartiles. Figure 4 also considers a heterogeneous setting where the agent player uses SGF and task player uses Borda (SGF/Borda-NE). Figure 3 presents performance of our FTRL-style solver according to the metrics discussed in Sections 4.2: exploitability (4) and hindsight winrate. All indicate our algorithm is effectively learning. Figure 4 displays the learned equilibrium for the agent and task player along with a plot supporting convergence of the iterates. Prior work espousing voting-as-evaluation found the rainbow agent top-ranked according to 99 different popular voting rules [41, Table 2]. Their result can be interpreted as equivalent to ours if we constrained the distribution over games to be uniform. Instead, our theory uniquely allows one to show that rainbow is the strongest agent even if the distribution over games is chosen adversarially. 5.2 Voting Equilibrium from Human Election Data: Lost at Sea In the Lost at Sea election scenario [15], groups of four participants deliberate and then elect one member to complete a leader’s task, a quiz whose score determines the payout to the group. The election proceeds as follows. Each participant submits both a willingness-to-lead self-nomination score (wtl ∈0,…,10∈\0,…,10\) and a vote ranking the other participants. The election mechanism selects the two participants with highest wtl, splitting ties randomly, and executes a runoff between them. Note that because no one could vote for themselves, only the votes of participants that are not candidates impact the result; see more details on the election in Appx. H.2.1. Table 1: Election: (Pure) Strategies are not a CO-NE. player i combinatorial action a implicitly def. ρi(a−i) _i(a_-i) voter vote wtl pref ≻ ≻ 2 ≻ ≻ ≻ ≻ ≻ 9 ≻ ≻ ≻ ≻ ≻ 5 ≻ ≻ ≻ ≻ ≻ 10 ≻ ≻ ≻ Separately, participants submitted rankings (pref) over who is elected. Given fixed co-player actions a−ia_-i and the election outcomes oio_i resulting from each possible action ai∈ia_i _i, we can rank the actions by pref(oio_i), e.g., if for , a→o=a→ o= and a′→o′=a → o = , then a≻a′a a . Voters can manipulate the election by pulling themselves out of the race (lowering wtl). Alternatively, if they know that the other players prefer a different candidate, they can reorder their vote to put their second favorite higher, therefore increasing the odds of that candidate being elected. Therefore, each participant’s strategy space (|i|=66|A_i|=66) consists of their wtl (1111 options) and vote in the election (3!=63!=6 options). Note that because the election mechanism is stochastic, we are forced to confront the issue of how to aggregate stochastic outcomes. We can construct player i’s lottery hierarchically; first sample a−i∼x−ia_-i x_-i, then independently sample each election outcome given aia_i (more details in Appx. H.2.2). We utilize election ranking data from [54], an online variation of the Lost at Sea task. The dataset contains 115 elections involving 460 participants, interacting under pseudonymous, animal-based identifiers. Assuming each voter acted deterministically, we find that approximately 30% of the 115 elections exhibited pure maximal lottery Nash equilibrium profiles. The remaining 70% contained at least 1 player with an incentive to deviate, suggesting humans were not voting optimally with respect to their reported preferences. We select two elections for detailed analysis in Appx. H.2, one in equilibrium and one not. Election data for one of those elections is shown in Table 1. We also demonstrate solving for an equilibrium of the election, assuming Borda as the voting rule. We then re-use existing NFG solvers to approximate a limiting logit equilibrium (LLE) [47], which we then analyze. For example, in one election, would prefer itself to win, but is low-ranked by everyone. Given that is unlikely to win, the LLE strategically suggests submit a low wtl to steer the election towards , its third favorite, given its second favorite is not in the runoff. Note also that the LLEs are mixed strategies—they mix over many (vote, wtl) combos. Whereas strategic voting theory assumes well-studied election rules [49], our COG formalism enabled a black-box analysis of a bespoke one. 6 Conclusion We proposed the first (probabilistic) mixed-strategy Nash equilibrium that generalizes to games with ordinal preferences. The key was to replace expected utility maximization for aggregating payoffs with social choice functions for aggregating preferences. We prove existence, develop practical notions of approximation and algorithms with rates, and demonstrate their use in AI evaluation and (stochastic) election manipulation. References Adler et al. [2009] Ilan Adler, Constantinos Daskalakis, and Christos H Papadimitriou. A note on strictly competitive games. In International Workshop on Internet and Network Economics, pages 471–474. Springer, 2009. Agrawal et al. [2019] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. Advances in Neural Information Processing Systems, 32, 2019. Aho [1983] Alfred V Aho. Data Structures and Algorithms. Addison-Wesley, 1983. Alipour and Goyal [2026] Hamidreza Alipour and Mohak Goyal. Utilitarian distortion under probabilistic voting. arXiv preprint arXiv:2602.11152, 2026. Aliprantis and Border [2006] Charalambos D Aliprantis and Kim C Border. Infinite Dimensional Analysis: A Hitchhiker’s Guide. Springer Science & Business Media, 2006. ISBN 978-3-540-29587-7. doi: 10.1007/3-540-29587-9_17. Amor et al. [2017] Nahla Ben Amor, Hélène Fargier, and Régis Sabbadin. Equilibria in ordinal games: A framework based on possibility theory. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI’17), page 105–111, 2017. Bakhtin et al. [2022] Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H Miller, and Noam Brown. Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning. arXiv preprint arXiv:2210.05492, 2022. Bakhtin et al. [2023] Anton Bakhtin, David J Wu, Adam Lerer, Jonathan Gray, Athul Paul Jacob, Gabriele Farina, Alexander H Miller, and Noam Brown. Mastering the game of no-press diplomacy via human-regularized reinforcement learning and planning. In The Eleventh International Conference on Learning Representations, 2023. Balduzzi et al. [2018] David Balduzzi, Karl Tuyls, Julien Perolat, and Thore Graepel. Re-evaluating evaluation. Advances in Neural Information Processing Systems, 31, 2018. Balinski and Laraki [2007] Michel Balinski and Rida Laraki. A theory of measuring, electing, and ranking. Proceedings of the National Academy of Sciences, 104(21):8720–8725, 2007. doi: 10.1073/pnas.0702634104. URL https://w.pnas.org/doi/abs/10.1073/pnas.0702634104. Beck and Teboulle [2003] Amir Beck and Marc Teboulle. Mirror descent and nonlinear projected subgradient methods for convex optimization. Operations Research Letters, 31(3):167–175, 2003. Benaïm and Faure [2013] Michel Benaïm and Mathieu Faure. Consistency of vanishingly smooth fictitious play. Mathematics of Operations Research, 38(3):437–450, 2013. Benaım and Hirsch [1999] Michel Benaım and Morris W Hirsch. Mixed equilibria and dynamical systems arising from fictitious play in perturbed games. Games and Economic Behavior, 29(1-2):36–72, 1999. Biggar and Shames [2023] Oliver Biggar and Iman Shames. The graph structure of two-player games. Scientific Reports, 13(1):1833, 2023. Born et al. [2022] Andreas Born, Eva Ranehill, and Anna Sandberg. Gender and Willingness to Lead: Does the Gender Composition of Teams Matter? The Review of Economics and Statistics, 104(2):259–275, 03 2022. ISSN 0034-6535. doi: 10.1162/rest_a_00955. URL https://doi.org/10.1162/rest_a_00955. Bradbury et al. [2018] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http://github.com/google/jax. Brandl et al. [2016] Florian Brandl, Felix Brandt, and Hans Georg Seedig. Consistent probabilistic social choice. Econometrica, 84(5):1839–1880, 2016. Brandt et al. [2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. Handbook of Computational Social Choice. Cambridge University Press, 2016. Brown [1951] George W Brown. Iterative solution of games by fictitious play. Act. Anal. Prod Allocation, 13(1):374, 1951. Candogan et al. [2011] Ozan Candogan, Ishai Menache, Asuman Ozdaglar, and Pablo A Parrilo. Flows and decompositions of games: Harmonic and potential games. Mathematics of Operations Research, 36(3):474–503, 2011. Caragiannis et al. [2017] Ioannis Caragiannis, Swaprava Nath, Ariel D Procaccia, and Nisarg Shah. Subset selection via implicit utilitarian voting. Journal of Artificial Intelligence Research, 58:123–152, 2017. Conitzer [2009] Vincent Conitzer. Approximation guarantees for fictitious play. In 2009 47th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 636–643. IEEE, 2009. Conitzer [2024] Vincent Conitzer. The complexity of computing robust mediated equilibria in ordinal games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 9607–9615, 2024. Cruz and Simaan [2000] JB Cruz and Marwan A Simaan. Ordinal games and generalized Nash and Stackelberg solutions. Journal of Optimization Theory and Applications, 107:205–222, 2000. Daskalakis et al. [2024] Constantinos Daskalakis, Ian Gemp, Yanchen Jiang, Renato Paes Leme, Christos Papadimitriou, and Georgios Piliouras. Charting the shapes of stories with game theory. arXiv preprint arXiv:2412.05747, 2024. Feder et al. [2007] Tomas Feder, Hamid Nazerzadeh, and Amin Saberi. Approximating nash equilibria using small-support strategies. In Proceedings of the 8th ACM Conference on Electronic Commerce, pages 352–354, 2007. Fishburn [1984] Peter C Fishburn. Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies, 51(4):683–692, 1984. Folland [1999] Gerald B Folland. Real Analysis: Modern Techniques and Their Applications, 2nd ed. John Wiley & Sons, 1999. Fudenberg and Levine [1995] Drew Fudenberg and David K Levine. Consistency and cautious fictitious play. Journal of Economic Dynamics and Control, 19(5-7):1065–1089, 1995. Fudenberg and Tirole [1991] Drew Fudenberg and Jean Tirole. Game Theory. MIT press, 1991. Gemp et al. [2022a] Ian Gemp, Kevin R McKee, Richard Everett, Edgar Duéñez-Guzmán, Yoram Bachrach, David Balduzzi, and Andrea Tacchetti. D3c: Reducing the price of anarchy in multi-agent learning. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 498–506, 2022a. Gemp et al. [2022b] Ian Gemp, Rahul Savani, Marc Lanctot, Yoram Bachrach, Thomas Anthony, Richard Everett, Andrea Tacchetti, Tom Eccles, and János Kramár. Sample-based approximation of nash in large many-player games via gradient descent. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, pages 507–515, 2022b. Gemp et al. [2024] Ian Gemp, Luke Marris, and Georgios Piliouras. Approximating nash equilibria in normal-form games via stochastic optimization. In The Twelfth International Conference on Learning Representations, 2024. Gemp et al. [2025] Ian Gemp, Andreas Alexander Haupt, Luke Marris, Siqi Liu, and Georgios Piliouras. Convex markov games: A new frontier for multi-agent reinforcement learning. In Forty-second International Conference on Machine Learning, 2025. Gordon et al. [2008] Geoffrey J Gordon, Amy Greenwald, and Casey Marks. No-regret learning in convex games. In Proceedings of the 25th International Conference on Machine learning, pages 360–367, 2008. Harsanyi et al. [1988] John C Harsanyi, Reinhard Selten, et al. A general theory of equilibrium selection in games. MIT Press Books, 1, 1988. Hessel et al. [2018] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski, Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. Hofbauer and Sandholm [2002] Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 70(6):2265–2294, 2002. Kakutani [1941] Shizuo Kakutani. A generalization of brouwer’s fixed point theorem. Duke Mathematical Journal, 8(3):457, 1941. Kemeny [1959] John G. Kemeny. Mathematics without numbers. Daedalus, 88(4):577–591, 1959. ISSN 00115266. URL http://w.jstor.org/stable/20026529. Lanctot et al. [2023] Marc Lanctot, Kate Larson, Yoram Bachrach, Luke Marris, Zun Li, Avishkar Bhoopchand, Thomas Anthony, Brian Tanner, and Anna Koop. Evaluating agents using social choice theory. arXiv preprint arXiv:2312.03121, 2023. Legacci et al. [2024] Davide Legacci, Panayotis Mertikopoulos, Christos Papadimitriou, Georgios Piliouras, and Bary Pradelski. No-regret learning in harmonic games: Extrapolation in the face of conflicting interests. Advances in Neural Information Processing Systems, 37:123637–123674, 2024. Liu et al. [2026] Mingyang Liu, Yongshan Chen, Zhiyuan Fan, Gabriele Farina, Asuman Ozdaglar, and Kaiqing Zhang. Online learning and equilibrium computation with ranking feedback. arXiv preprint arXiv:2603.19221, 2026. Liu et al. [2025] Siqi Liu, Ian Gemp, Luke Marris, Georgios Piliouras, Nicolas Heess, and Marc Lanctot. Re-evaluating open-ended evaluation of large language models. In The Thirteenth International Conference on Learning Representations, 2025. Marris et al. [2025] Luke Marris, Siqi Liu, Ian Gemp, Georgios Piliouras, and Marc Lanctot. Deviation ratings: A general, clone-invariant rating method. arXiv preprint arXiv:2502.11645, 2025. Maura-Rivero et al. [2025] Roberto-Rafael Maura-Rivero, Marc Lanctot, Francesco Visin, and Kate Larson. Jackpot! alignment as a maximal lottery. arXiv preprint arXiv:2501.19266, 2025. McKelvey and Palfrey [1995] Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and Economic Behavior, 10(1):6–38, 1995. McMahan [2017] H Brendan McMahan. A survey of algorithms and analysis for adaptive online learning. Journal of Machine Learning Research, 18(90):1–50, 2017. Myerson and Weber [1993] Roger B Myerson and Robert J Weber. A theory of voting equilibria. American Political science review, 87(1):102–114, 1993. Nash Jr [1950] John F Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48–49, 1950. Pardalos and Vavasis [1991] Panos M Pardalos and Stephen A Vavasis. Quadratic programming with one negative eigenvalue is np-hard. Journal of Global optimization, 1(1):15–22, 1991. Perolat et al. [2021] Julien Perolat, Remi Munos, Jean-Baptiste Lespiau, Shayegan Omidshafiei, Mark Rowland, Pedro Ortega, Neil Burch, Thomas Anthony, David Balduzzi, Bart De Vylder, et al. From poincaré recurrence to convergence in imperfect information games: Finding equilibrium via regularization. In International Conference on Machine Learning, pages 8525–8535. PMLR, 2021. Procaccia and Rosenschein [2006] Ariel D Procaccia and Jeffrey S Rosenschein. The distortion of cardinal preferences in voting. In International Workshop on Cooperative Information Agents, pages 317–331. Springer, 2006. Qian et al. [2025] Crystal Qian, Aaron Parisi, Clémentine Bouleau, Vivian Tsai, Maël Lebreton, and Lucas Dixon. To mask or to mirror: Human-AI alignment in collective reasoning. 2025. URL https://arxiv.org/abs/2510.01924. Robinson [1951] Julia Robinson. An iterative method of solving a game. Annals of Mathematics, 54(2):296–301, 1951. Saari [1995] Donald G Saari. Basic Geometry of Voting, volume 12. Springer Science & Business Media, 1995. Shalev-Shwartz et al. [2012] Shai Shalev-Shwartz et al. Online learning and online convex optimization. Foundations and Trends® in Machine Learning, 4(2):107–194, 2012. Sokota et al. [2023] Samuel Sokota, Ryan D’Orazio, J Zico Kolter, Nicolas Loizou, Marc Lanctot, Ioannis Mitliagkas, Noam Brown, and Christian Kroer. A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In The Eleventh International Conference on Learning Representations, 2023. Suggala and Netrapalli [2020] Arun Suggala and Praneeth Netrapalli. Follow the perturbed leader: Optimism and fast parallel algorithms for smooth minimax games. Advances in Neural Information Processing Systems, 33:22316–22326, 2020. Appendix A Context Ordinal Equilibria A.1 Doubly Probabilistic Social Choice Functions Many voting rules satisfy or can be adapted to satisfy Definition 2 of a doubly pSCF. Scoring rules (e.g. plurality, Borda, veto, etc.) can compute solutions taking a lottery (or distribution) over preference relations as input. So can k-approval. Rules are divided into C1C1, C2C2, and C3C3 by Fishburn [27] depending on what information is needed to compute them. C1C1 uses only pairwise majority relationships (e.g., Copeland), C2C2 uses weighted pairwise majority relationships (e.g., ranked pairs, Borda), and then C3C3 is other rules (e.g., Dodgson). The lottery representation enables at least C1C1 and C2C2 rules. Axioms’ Effect on dpSCFs Social choice theory is axiomatic. We discuss a few axioms and how they are important to dpSCFs here. For example, if dictatorship was possible, player j could induce arbitrarily small mass on some action profile such that it completely overwrites player i’s best response regardless of the other outcomes possible; this would be akin to shifting mass onto an outcome with infinite payoff in an NFG. Clone-invariance asserts that duplicate actions (i.e., actions that are ranked the same under every co-player action profile) will appear symmetrically in the best response; this ensures equilibria exist that have symmetric mass and payoff across cloned actions. Paretian voting rules ensure that if a player ranks an action above another under all co-player action profiles, the aggregate voting rule will as well; translating to COGs, if an action has higher payoff than all other actions under all co-player actions, this action will be a best response. These properties can be taken for granted in classical games that use expected value to aggregate scores, but it is critical and fortuitous that social choice has already developed these tools for use in COGs. Note that Borda fails clone-invariance. It also fails Condorcet consistency, which is a major motivation for works that explore alternatives to the standard RLHF pipeline (see [46] which advocates for maximal lotteries). A.2 COGs as NFGs As mentioned in Section 3.1, scoring and positional voting rules induce normal-form games. This can be seen by filling out player i’s payoff tensor Ui(⋅,a−i)U_i(·,a_-i) one “slice” at a time. For each player i and each possible co-player action profile a−ia_-i, retrieve player i’s preference relation ρi(a−i) _i(a_-i) which results in a vector of numerical scores for each of player i’s actions: Ui(⋅,a−i)←ρi(a−i)U_i(·,a_-i)← _i(a_-i). Scoring and positional voting rules simply take an average of these scores proportional to their representation in the population of votes which is precisely equivalent to computing the expected payoff for each action as is standard in NFG calculations. A.3 Correlated Equilibria Correlated equilibria (CE) are also important in classical game theory, particularly in n-player, general-sum settings, and have natural counterparts here. A correlated equilibrium is a joint distribution x over action profiles such that no player has any incentive to unilaterally deviate even after observing their recommended action (sampled from x). As before, we represent this as a best-response inclusion problem. Define BRi(ai|)=νi(vi(x(−i|ai))) BR_i(a_i| x)= _i(v_i(x(A_-i|a_i))) where the conditional distribution x(−i|ai)=(ai,−i)/x(ai)x(A_-i|a_i)= x(a_i,A_-i)/x(a_i) and the marginal distribution x(ai)=∑a−i′∈−i(ai,a−i′)x(a_i)= _a _-i _-i x(a_i,a _-i). Define scalar-set multiplication as a⋅BRi(ai|)=a⋅v|v∈BRi(ai|)a· BR_i(a_i| x)=\a· v|v∈ BR_i(a_i| x)\. Then ∈x(ai)⋅(BRi(ai|)−eai)0∈ x(a_i)·( BR_i(a_i| x)-e_a_i) for all i represents the condition for a context-ordinal CE where eaie_a_i is the standard Euclidean basis vector. (a) Classic (b) Classic (EMD) (c) ML (EMD) (d) Borda (EMD) Figure 5: Exploitability (ϵε) landscapes for a 22-action (Swerve/Straight) Chicken game using various regularized social choice BR(p=0,q=0.1,μ=[1/2,1/2]) BR^(p=0,q=0.1,μ=[ 12, 12])s. Panel (5(a)) displays traditional exploitability based on cardinal payoffs whereas (5(b)), (5(c)), and (5(d)) measure earth mover’s distance (EMD). Maximal lotteries (ML) and Borda coincide in two candidate (action) settings. Interestingly, coarse correlated equilibria (CCE) cannot be (classically) defined in COGs. In both NE and CE, a player considers deviating from their current strategy to an alternative strategy under a fixed context, either a co-player strategy or conditional belief. In a CCE, the expected utility of a joint distribution is compared against a fixed action. This requires aggregating utility across contexts with different weights, so a player must effectively be able to compare their own actions under different co-player action profiles. In the COG definition, we specifically assume that a player can only rank their actions under a fixed co-player action profile, which rules out this possibility. However, we discussed a generalized notion of external regret in Section 4.2.2 which suggests an alternative route towards CCE. A CCE can instead be defined as a joint distribution such that no player has an incentive to deviate to any fixed strategy (in hindsight), i.e., all players simultaneously experience zero external regret. A.4 Exploitability Landscapes Figure 5 shows how CO-NE differ from classical NE on a simple 2-player, 2-action Chicken game. Panels 5(a) and 5(b) display the traditional exploitability landscape and earth mover’s distance (EMD) landscape for a classical NE respectively. Panel 5(c) shows the EMD landscape for a CO-NE defined using maximal lotteries as the voting rule. Panel 5(d) shows the same landscape but for Borda as the voting rule. Appendix B Regularized Best Response Algorithm 1 Regularized Best Response 1: Given: p, μi _i, νi _i, γ(⋅|x−i,q)γ(·|x_-i,q), M 2: BRi=|i| BR_i=0_|A_i| 3: for m=1m=1 to M do 4: x^−i∼γ(⋅|x−i,q) x_-i γ(·|x_-i,q) 5: u∼Cat(μi)u Cat( _i) 6: vu=au≻aj|j∈[|i|],j≠uv_u=\a_u a_j\,\,|\,\,j∈[|A_i|],j≠ u\ 7: vu=vu∪aj∼ak|j,k∈[|i|]/u,j≠kv_u=v_u∪\a_j a_k\,\,|\,\,j,k∈[|A_i|]/\u\,j≠ k\ 8: V=v:0|v∈(i)V=\v:0\,\,|\,\,v (A_i)\ 9: for all a−i∈−ia_-i _-i do 10: bit∼Bern(p)bit~ Bern(p) 11: freq=x^−i(a−i)freq= x_-i(a_-i) 12: if bit==1bit==1 then 13: V(vu)+=freqV(v_u) +=freq 14: else 15: V(ρi(a−i))+=freqV( _i(a_-i)) +=freq 16: end if 17: end for 18: BRi+=νi(V)/M BR_i += _i(V)/M 19: end for 20: Output: BRi BR_i We now describe our approach to regularizing best responses. Algorithm 1 provides pseudocode. Recall from Definition 3 that every action profile a−ia_-i induces a vote ρi(a−i) _i(a_-i) or ballot type and this vote is represented in a population of votes with frequency x−i(a−i)x_-i(a_-i). We will represent random perturbations as randomly swapping votes for votes from another distribution dependent on the given μi _i. Consider the following random process. Draw a random usurper from μi _i. Set the usurper ballot such that the usurper is ranked strictly first; the remaining players can be ranked arbitrarily but we set all others tied for second in experiments. For every co-player action profile, replace the original ballot with the usurper ballot with probability p. Apply the (dpSCF) voting rule to this perturbed population of votes to compute a sampled best response. Take the expectation over these sampled best responses to return an expected best response. If p=0p=0, then the best response remains the same as before. If p=1p=1, all ballots are replaced by the usurper ballot and any voting rule satisfying majority rule will select the usurper as the sampled best response. As the usurper is selected according to μi _i, the expected best response will also be equal to μi _i. At this point, we have introduced two new parameters, p and μi _i. Denote this parameterized best response by BRi(p,μi) BR_i^(p, _i). To achieve a single-valued best response, we will replace all non-singleton best responses, which are necessarily convex subsets of the simplex, with their centroid, i.e, the uniform distribution over the winning candidates. Note this now means BRi(p,μi) BR^(p, _i)_i is no longer u.h.c. as it could jump at ties, e.g., A≻B→B∼A→B≻A B→ B A→ B A leads to [1,0]→[0.5,0.5]→[0,1][1,0]→[0.5,0.5]→[0,1]. Recall one of our desiderata is to ensure continuity, a stronger condition than u.h.c. To render the best response BRi(p,μi)(x−i) BR^(p, _i)_i(x_-i) continuous with respect to x−ix_-i, we can introduce a trembling hand by taking the expectation over a Dirichlet perturbation, Dir(α)Dir(α), with density ρ where α=+1/qx−iα=1+ 1q\,x_-i with q>0q>0: BRi(p,q,μi)(x−i) BR_i^(p,q, _i)(x_-i) =x−i′∼Dir(α)[BRi(p,μi)(x−i′)]=∫−iBRi(p,μi)(x−i′)ρ(x−i′|α)x−i′. =E_x _-i Dir(α)[ BR_i^(p, _i)(x _-i)]= _X_-i BR_i^(p, _i)(x _-i)ρ(x _-i|α)dx _-i. (8) For any fixed q>0q>0, the Dirichlet density ρ(x−i′|α)ρ(x _-i|α) is continuous in its parameters α and thus also in x−ix_-i. Notice that BRi(p,μi)(x−i′) BR_i^(p, _i)(x _-i) is independent of x−ix_-i, therefore the integrand is continuous in x−ix_-i for every fixed x−i′x _-i. Because q>0q>0, this implies α≥1α≥ 1 and so the density ρ is uniformly bounded. Combined with the fact that best responses are probability distributions (and thus bounded), the integrand is dominated by a constant integrable function. We then invoke the Dominated Convergence Theorem [28][p. 56, Theorem 2.27] to conclude that BRi(p,q,μi)(x−i) BR^(p,q, _i)_i(x_-i) is continuous. Lastly, note that as limq→0+ _q→ 0^+, Dir(α)Dir(α) converges weakly to a Dirac delta at x−ix_-i, meaning we achieve continuity while recovering an element of the original best response set in the limit. The Dirichlet also as full support over the simplex for q>0q>0, consistent with the “trembling hand” interpretation of sampling all distributions with positive probability. In summary, p regularizes BRi BR_i towards μi _i; q smooths. Definition 5 (Regularized Best Response). Let BRi(p,q,μi)(x−i) BR_i^(p,q, _i)(x_-i) denote the expectation of a dpSCF (Def. 2), in which, with probability p, ballot types are replaced with ballots top-ranked by an action sampled from μi _i, non-singleton dpSCF outputs are replaced with their centroid, and the underlying voting distribution x−ix_-i is replaced with a full-support distribution γ such that γ converges to a Dirac delta distribution on x−ix_-i as q→0q→ 0 and uniform as q→∞q→∞. Proposition 1. The regularized best response function BRi(p,q,μi)(x−i) BR_i^(p,q, _i)(x_-i) with p∈[0,1]p∈[0,1], q>0q>0, and μi∈Δi _i∈ ^A_i satisfies desiderata (C1), (C3), (C4). In the limit q→0q→ 0, (C2) is satisfied. Figure 6: Best Response Regularization in Chicken. B.1 Empirical Demonstration Figure 6 displays the results of a simple experiment, regularizing a maximal lottery best response in a chicken game towards a uniform strategy. A chicken game is a symmetric game in which you prefer to go “straight” unless your co-player does, in which case you would rather “swerve” to avoid a collision, i.e., ρ(“swerve”) → “straight” ≻ “swerve” and ρ(“straight”) → “swerve” ≻ “straight”. We find that setting q=0.1q=0.1 is sufficient to achieve both continuity and correctness of the best response over the range of p. For Figures 5(a) and 5(b), the precise payoff matrices used for player 11 and 22 were U(1)=[3/41/210]U^(1)= bmatrix3/4&1/2\\ 1&0 bmatrix and U(2)=[3/411/20]U^(2)= bmatrix3/4&1\\ 1/2&0 bmatrix respectively. Appendix C Distortion Traditionally, distortion expresses the ratio of the maximum social welfare possible given knowledge of voters’ cardinal scores for each candidate to the social welfare achieved by a voting rule applied to those same voters’ preferences. Bounds on distortion are typically derived assuming voters’ cardinal scores are non-negative and sum-to-1. Many voting rules process votes as ordinal rankings which destroys the more detailed cardinal information which means distortion is commonly strictly greater than 1. We derive a lemma below that extends a distortion bound given each voter k’s scores sum-to-sks_k. In what follows, election outcomes may be probabilistic, which we represent as a distribution x over candidates. The expected welfare SWsSW^s of this election outcome given access to the scaled voting scores is SWs() SW^s( x) =1K∑kskvk⊤ = 1K _ks_kv_k x (9) where K is the number of voters and vkv_k is a vector of voter k’s unit-normalized scores for each candidate. Lemma 2. Assume ν is a voting rule that only processes ordinal rankings. Then d(ν,)≤κd(ν) d(ν, s)≤κ d(ν) (10) where κ=maxkskminkskκ= _ks_k _ks_k and d(ν)d(ν) is an upper bound on the distortion of the voting rule ν when each voter’s ballot scores are non-negative and sum-to-1. Proof. Let cs x_cs be the distribution over candidates that maximizes welfare assuming access to the voters’ scaled cardinal scores: cs x_cs =argmaxcs1K∑kskvk⊤cs. = *arg\,max_ x_cs 1K _ks_kv_k x_cs. (11) Let c x_c be the distribution over candidates that maximizes welfare assuming access to the voters’ un-scaled, i.e., unit-normalized, cardinal scores: c x_c =argmaxc1K∑kvk⊤c. = *arg\,max_ x_c 1K _kv_k x_c. (12) The social welfare of cs x_cs is then upper bounded as SWs(cs) SW^s( x_cs) =1K∑kskvk⊤cs≤1K(maxksk)(∑kvk⊤cs)≤1K(maxksk)(∑kvk⊤c). = 1K _ks_kv_k x_cs≤ 1K( _ks_k)( _kv_k x_cs)≤ 1K( _ks_k)( _kv_k x_c). (13) Let xνx_ν be the distribution over candidates returned by the voting rule ν. The social welfare of ν x_ν is then lower bounded as SWs(ν) SW^s( x_ν) =1K∑kskvk⊤ν≥1K(minksk)(∑kvk⊤ν). = 1K _ks_kv_k x_ν≥ 1K( _ks_k)( _kv_k x_ν). (14) The distortion is the ratio of the two and is upper bounded as d(ν,) d(ν, s) =SWs(cs)SWs(ν)≤maxkskminksk∑kvk⊤cs∑kvk⊤ν = SW^s( x_cs)SW^s( x_ν)≤ _ks_k _ks_k _kv_k x_cs _kv_k x_ν (15) ≤maxkskminksk∑kvk⊤c∑kvk⊤ν ≤ _ks_k _ks_k _kv_k x_c _kv_k x_ν (16) =maxkskminkskd(ν). = _ks_k _ks_kd(ν). (17) ∎ Given a strategy profile x for an n-player COG, we can use Lemma 2 above to understand the suboptimality of a player’s best response if they opt for a social choice rule (dpSCF) rather than a traditional best response using expected utility theory. To apply Lemma 2, we will assume the underlying payoffs of the game are non-negative with strictly positive sum. Note that an affine transformation of the payoff matrix does not change the set of equilibria so this assumption is without loss of generality. Simply let i s_i be a vector containing the payoff sums for player i under each possible joint action of the co-players. Then apply Lemma 2 by looking up the distortion bound for the chosen voting rule νi _i. Theorem 2. Assume ν is a voting rule that only processes ordinal rankings. Then distortion d+(ν,)≤κ++(minksk)d+(ν) d^+(ν, s)≤κ^++( _ks_k)d^+(ν) (18) where κ=(maxksk−minksk)κ=( _ks_k- _ks_k) and d+(ν)d^+(ν) is an upper bound on the additive distortion of the voting rule ν when each voter’s ballot scores are non-negative and sum-to-1. Proof. As in Lemma 2, let SWsSW^s denote the social welfare function with scaled votes. Let SWSW denote the social welfare function assuming unit-normalized scores, which implies SW≤1SW≤ 1. We are interested in the additive distortion: d+(ν,) d^+(ν, s) =SWs(cs)−SWs(ν) =SW^s( x_cs)-SW^s( x_ν) (19) ≤(maxksk)SW(c)−(minksk)SW(ν) ≤( _ks_k)SW( x_c)-( _ks_k)SW( x_ν) (20) =(maxksk−minksk)SW(c)+(minksk)(SW(c)−SW(ν)) =( _ks_k- _ks_k)SW( x_c)+( _ks_k)(SW( x_c)-SW( x_ν)) (21) ≤κ++(minksk)d+(ν). ≤κ^++( _ks_k)d^+(ν). (22) ∎ Theorem 3. The additional distortion introduced by our regularization process is d+(νp,i,ui,x−i) d^+( _p,i,u_i,x_-i) ≤κ++(minksk)(d+(ν)+(1−(1−p)|−i|)). ≤κ^++( _ks_k)(d^+(ν)+ (1-(1-p)^|A_-i| )). (23) By Bernoulli’s inequality, the quantity (1−(1−p)|−i|) (1-(1-p)^|A_-i| ) behaves as |−i|p|A_-i|p for small p. Proof. The regularized voting process replaces each vote with a usurper vote with probability p. Therefore, with probability (1−p)|−i|(1-p)^|A_-i|, no votes are replaced. The voting rule returns ν x_ν in this case. Taking the expectation of these outputs, we can then determine νp x_ _p =(1−p)|−i|ν+(1−(1−p)|−i|) =(1-p)^|A_-i| x_ν+ (1-(1-p)^|A_-i| ) z (24) where xνpx_ _p denotes the perturbed output (regularized best response) and z denotes the expected output under the remaining perturbation events. The distortion of our perturbed voting rule, denoted νp _p, can be decomposed into the distortion of the original voting rule ν and the gap between the perturbed and original: d+(νp) d^+( _p) =SW(cs)−SW(ν)⏟distortion+SW(ν)−SW(νp)⏟perturbation error = SW( x_cs)-SW( x_ν)_distortion+ SW( x_ν)-SW( x_ _p)_perturbation error (25) ≤d+(ν)+SW(ν)−SW(νp) ≤ d^+(ν)+SW( x_ν)-SW( x_ _p) (26) =d+(ν)+SW(ν)−SW((1−p)|−i|ν+(1−(1−p)|−i|)) =d^+(ν)+SW( x_ν)-SW((1-p)^|A_-i| x_ν+ (1-(1-p)^|A_-i| ) z) (27) =d+(ν)+(1−(1−p)|−i|)(SW(ν)−SW()) =d^+(ν)+ (1-(1-p)^|A_-i| ) (SW( x_ν)-SW( z) ) (28) ≤d+(ν)+(1−(1−p)|−i|) ≤ d^+(ν)+ (1-(1-p)^|A_-i| ) (29) ≤d+(ν)+|−i|p ≤ d^+(ν)+|A_-i|p (30) where (28) follows from linearity of social welfare, (29) from social welfare being bounded to [0,1][0,1], and the last step from Bernoulli’s inequality. Plugging this result into Theorem 2 achieves the claim. ∎ C.1 Weakened Fictitious-Play (WFP) We consider fictitious-play run for T rounds with approximate best responses whose error is upper bounded by d+(ν,)d^+(ν, s). We can trace the argument put forth in [22] to prove the following. Corollary 1 (Theorem 1 [22]). The fictitious-play profile T=[xT(1),xT(2)] x_T=[x^(1)_T,x^(2)_T] after T rounds is an ϵT _T-NE where ϵT≤T+12T+12d+(ν,) _T≤ T+12T+ 12d^+(ν, s). Proof. We simply trace [22, Theorem 1] with approximate best responses. By symmetry, it suffices to show that xT(1)=1T∑t=1Txt(1)x^(1)_T= 1T _t=1^Tx^(1)_t is an ϵT _T-best response to xT(2)=1T∑t=1Txt(2)x^(2)_T= 1T _t=1^Tx^(2)_t. Let BR1 BR_1 be a best response to xT(2)x^(2)_T. The corresponding best-response utility for player 11 is u1(BR1,xT(2))=1T∑t=1Tu1(BR1,xt(2))u_1( BR_1,x^(2)_T)= 1T _t=1^Tu_1( BR_1,x^(2)_t). For 2≤t′≤T+12≤ t ≤ T+1, because xt′(1)x^(1)_t is a best response to xt′−1(2)x^(2)_t -1, all utilities are non-negative, and the utilities are bilinear, we have u1(xt′(1),xT(2)) u_1(x^(1)_t ,x^(2)_T) =u1(xt′(1),1T∑t=1Txt(2)) =u_1(x^(1)_t , 1T _t=1^Tx^(2)_t) (31) =∑t=1T(1/T)u1(xt′(1),xt(2)) = _t=1^T( 1T)u_1(x^(1)_t ,x^(2)_t) (32) =∑t=1t′−1(1/T)u1(xt′(1),xt(2))+∑t=t′T(1/T)u1(xt′(1),xt(2)) = _t=1^t -1( 1T)u_1(x^(1)_t ,x^(2)_t)+ _t=t ^T( 1T)u_1(x^(1)_t ,x^(2)_t) (33) ≥∑t=1t′−1(1/T)u1(xt′(1),xt(2)) ≥ _t=1^t -1( 1T)u_1(x^(1)_t ,x^(2)_t) (34) =(t′−1T)u1(xt′(1),1(t′−1)∑t=1t′−1xt(2)) = ( t -1T )u_1(x^(1)_t , 1(t -1) _t=1^t -1x^(2)_t) (35) =(t′−1T)u1(xt′(1),xt′−1(2)) = ( t -1T )u_1(x^(1)_t ,x^(2)_t -1) (36) ≥(t′−1T)[u1(BR1,xt′−1(2))−d+(ν,)] ≥ ( t -1T )[u_1( BR_1,x^(2)_t -1)-d^+(ν, s)] (37) =u1(BR1,1T∑t=1t′−1xt(2))−∑t=1t′−1(1/T)d+(ν,) =u_1( BR_1, 1T _t=1^t -1x^(2)_t)- _t=1^t -1( 1T)d^+(ν, s) (38) =∑t=1t′−1(1/T)[u1(BR1,xt(2))−d+(ν,)] = _t=1^t -1( 1T)[u_1( BR_1,x^(2)_t)-d^+(ν, s)] (39) where (37) follows by the fact that xt′(1)x^(1)_t is an approximate best response to xt′−1(2)x^(2)_t -1; most importantly, it at least −d+(ν,)-d^+(ν, s) better than any other strategy (including BR1 BR_1) in responding to xt′−1(2)x^(2)_t -1. Continuing, for the case where player 1 plays xT(1)x^(1)_T, we have u1(xT(1),xT(2)) u_1(x^(1)_T,x^(2)_T) =u1(1T∑t′=1Txt′(1),xT(2)) =u_1( 1T _t =1^Tx^(1)_t ,x^(2)_T) (40) =∑t′=1T(1/T)u1(xt′(1),xT(2)) = _t =1^T( 1T)u_1(x^(1)_t ,x^(2)_T) (41) =(1/T)u1(xt′=1(1),xT(2))+∑t′=2T(1/T)u1(xt′(1),xT(2)) =( 1T)u_1(x^(1)_t =1,x^(2)_T)+ _t =2^T( 1T)u_1(x^(1)_t ,x^(2)_T) (42) ≥0+∑t′=2T(1/T)u1(xt′(1),xT(2)) ≥ 0+ _t =2^T( 1T)u_1(x^(1)_t ,x^(2)_T) (43) ≥∑t′=1T(1/T)∑t=1t′−1(1/T)[u1(BR1,xt(2))−d+(ν,)]summand equals 0 for t′=1 ≥ _t =1^T( 1T) _t=1^t -1( 1T)[u_1( BR_1,x^(2)_t)-d^+(ν, s)] equals $0$ for $t =1$ (44) =(1/T2)∑t=1T−1∑t′=t+1T[u1(BR1,xt(2))−d+(ν,)]re-index sum of lower triangular (t′×t) matrix =( 1T^2) _t=1^T-1 _t =t+1^T[u_1( BR_1,x^(2)_t)-d^+(ν, s)] -index sum of lower triangular ($t × t$) matrix (45) =(1/T2)∑t=1T(T−t)[u1(BR1,xt(2))−d+(ν,)]. =( 1T^2) _t=1^T(T-t)[u_1( BR_1,x^(2)_t)-d^+(ν, s)]. (46) On the other hand, u1(BR1,xT(2)) u_1( BR_1,x^(2)_T) =u1(BR1,1T∑t=1Txt(2)) =u_1( BR_1, 1T _t=1^Tx^(2)_t) (47) =(1/T)∑t=1Tu1(BR1,xt(2)) =( 1T) _t=1^Tu_1( BR_1,x^(2)_t) (48) =(1/T2)∑t=1Tu1(BR1,xt(2)). =( 1T^2) _t=1^TTu_1( BR_1,x^(2)_t). (49) It follows that the suboptimality for player 11 of playing xT(1)x^(1)_T is u1(BR1,xT(2))−u1(xT(1),xT(2)) u_1( BR_1,x^(2)_T)-u_1(x^(1)_T,x^(2)_T) ≤(1/T2)∑t=1Ttu1(BR1,xt(2))+(1/T2)∑t=1T(T−t)d+(ν,) ≤( 1T^2) _t=1^Ttu_1( BR_1,x^(2)_t)+( 1T^2) _t=1^T(T-t)d^+(ν, s) (50) ≤(1/T2)∑t=1Tt+(1/T2)d+(ν,)∑t=1T(T−t) ≤( 1T^2) _t=1^Tt+( 1T^2)d^+(ν, s) _t=1^T(T-t) (51) =(1/T2)(T+1)(T/2)+(1/T2)d+(ν,)∑t=0T−1t =( 1T^2)(T+1)( T2)+( 1T^2)d^+(ν, s) _t=0^T-1t (52) =(1/T2)(T+1)(T/2)+(1/T2)d+(ν,)(T−1)(T/2) =( 1T^2)(T+1)( T2)+( 1T^2)d^+(ν, s)(T-1)( T2) (53) =(T+1)(2T)+(T−1)(2T)d+(ν,). = (T+1)(2T)+ (T-1)(2T)d^+(ν, s). (54) ∎ C.1.1 Distortion of Regularized Best Responses The bounds above are derived for unregularized best responses. There exists a new result in the distortion literature that examines multiplicative distortion under a different perturbation model [4]. If this line of work were to continue and uncover additive bounds, we might be able to apply them here to obtain bounds for a different form of regularized best responses. C.1.2 First Order Stochastic Dominance We clarify a relationship between first order stochastic dominance (FSD) and social choice based best responses. Within the context of COGs, let xix_i and xi′x_i be two mixed strategies from which we can sample actions aia_i and ai′a_i . Let ui:→ℝu_i:A be any isotone (order-preserving) utility function that is consistent with the given preference relation ρi _i. In other words, if ai≻ai′a_i a_i in the context of a−ia_-i, then ui(ai,a−i)>ui(ai′,a−i)u_i(a_i,a_-i)>u_i(a _i,a_-i) and if ai∼ai′a_i a_i in the context of a−ia_-i, then ui(ai,a−i)=ui(ai′,a−i)u_i(a_i,a_-i)=u_i(a _i,a_-i). Then x strictly FSD-dominates xi′x_i if [ui(xi,x−i)]>[ui(xi′,x−i)]E[u_i(x_i,x_-i)]>E[u_i(x_i ,x_-i)] holds for every uiu_i where uiu_i has been extended to act on distributions in the standard way. Consider xi′x_i player i’s current strategy. Assume xix_i strictly FSD-dominates xi′x_i as above. Under which voting rules does player i have a strict incentive to deviate? Within social choice theory, the property that an aggregation rule never selects a lottery that is stochastically dominated by another is known as SD-efficiency. Both positional scoring rules and Maximal Lotteries are SD-efficient, hence, no strategies in their induced best responses sets will ever be FSD-dominated by another strategy. Appendix D Complexity It is natural to attempt to understand the complexity of computing voting equilibria. Given two-player, zero-sum games represent a natural complexity boundary in the classical payoff setting, we first explore whether this boundary translates to the voting setting. D.1 Two-Player, Zero-Sum First off, it is not immediately possible to translate the notion of 2-player, zero-sum to a COG. First, there no longer exist payoffs that can be summed. Second, players are not required to express preferences over unilateral changes in actions by the other player. As mentioned in Section 3.1, score and positional voting rules induce normal-form games with payoffs from which we can then analyze traditional two-player, zero-sum definitions. However, we show that COGs defined to be intuitively adversarial fail these necessary conditions. In particular, adversarial COGs are neither harmonic nor strictly-competitive. Harmonic games [20, 42] generalize the classical two-player, zero-sum definition in a way that relies on only the weighted response graph, a graph of joint action nodes with arrows indicating favorable (including ties) deviations for players. Strictly competitive games [1] are two-player, zero-sum up to shift and scale of each player’s payoffs. We provide a practical example of this phenomenon in Figure 7 motivated by game-theoretic evaluation [44, 45], specifically Nash averaging [9]. In that setting, one often considers games where it is unclear how to compare performance on one task X (e.g., measured with perplexity) with another task Y (e.g., measured with accuracy), whereas ranking models on a common task is clear. Figure 7: Adversarial COGs are not necessarily strictly competitive, nor harmonic, however, they are preference-zero-sum. Preferences over agents for each task are indicated in (7(a)) by gold, silver, and bronze. Preferences over tasks are directly opposed and are indicated in (7(b)) by 0 (not preferred) and 11 (preferred). The gold arrow in (7(a)) highlights that the agent player can improve their outcome by switching from agent C (silver) to agent A (gold) when playing task X. Assuming Borda as the voting rule (and the payoffs induced in its associated NFG representation), the corresponding black arrow in (7(b)) shows the task player is indifferent (although recall preferences over agents are not explicitly represented in a COG for the task player). Hence, this game is not strictly competitive either. The associated (weighted) response graph is shown in (7(c)); weights are calculated again assuming Borda. Appx. D.1.1 shows that there does not exist a node weighting that makes the net flow at every node zero, ruling out the game as harmonic. However, if one reverses all horizontal edges in the graph (gray), it is possible to construct a common payoff game (values in gray) with the same (unweighted) response graph, proving the game is preference-zero-sum. (a) Agent Preferences Tasks Agents X Y A B C (b) Task Preferences Tasks Agents X Y A 0 1 B 1 0 C 0 1 (c) (Weighted) Response GraphAXAYBXBYCXCY+1+2+1+1+1+1+1+2+1210210 D.1.1 Harmonic A finite (cardinal) game is harmonic [42, Def. 1] when it admits a collection of action weights βi,ai∈(0,∞) _i,a_i∈(0,∞), ai∈ia_i _i, i∈[N]i∈[N], such that ∑i∑ai′∈iβi,ai′[ui()−ui(ai′,a−i)]=0∀∈. _i _a _i _i _i,a_i [u_i( a)-u_i(a_i ,a_-i)]=0 ∀ a . (55) In other words, there exists a weighting of the weighted response graph such that the net flow at every (joint action) node is zero. The condition above is linear in the action weights, so we can simply construct a matrix A of the terms ui()−ui(ai′,a−i)u_i( a)-u_i(a_i ,a_-i) and check if there exists weights β=[β1A,β1B,β1C,β2X,β2Y]β=[ _1A, _1B, _1C, _2X, _2Y] that set Aβ=Aβ=0, i.e., check that A is full column-rank (equiv., empty null-space). In the case of Figure 7, the terms ui()−ui(ai′,a−i)u_i( a)-u_i(a_i ,a_-i) are indicated in black next to the directed edges. The rows of A are ordered [AX,AY,BX,BY,CX,CY][AX,AY,BX,BY,CX,CY]: A A =[0210−10−1110−20−101102−10−1100−1−1−2010]. = bmatrix0&2&1&0&-1\\ 0&-1&1&1&0\\ -2&0&-1&0&1\\ 1&0&2&-1&0\\ -1&1&0&0&-1\\ -1&-2&0&1&0 bmatrix. (56) This matrix has full column-rank, therefore its null space contains only the zeros vector. So there does not exist an action weighting β with βi,ai∈(0,∞) _i,a_i∈(0,∞) to render the net flow zero. Therefore, it is not harmonic. D.1.2 Preference-Zero-Sum While COGs do not admit a direct payoff structure, they do provide corresponding (unweighted) response graphs. The COG in Figure 7 does satisfy the definition of preference-zero-sum [14] which relies only on the unweighted response graph. A preference zero-sum game’s corresponding response graph has only one sink component [14, Corollary 4.11], which we can calculate in time linear in the graph Θ(V+E) (V+E), polynomial in the size of the game, using, e.g., Kosaraju-Sharir’s algorithm [3, Algorithm p. 224 & 229]. The sink component conveys information about evolution, learning, and omits strictly dominated strategies. Nevertheless, we are unaware of any efficiency results for computing equilibria only assuming the preference-zero-sum property. Hence, two-player, zero-sum does not appear to represent a complexity boundary in COGs similarly to classical NFGs. D.2 Two-Player, Known-Support We now consider instead the even simpler problem of computing an equilibrium of a 22-player game given we know the support. Probabilistic voting rules are sometimes avoided simply due to humans’ aversion to a randomized election outcome. However, given our context-ordinal Nash equilibrium solution concept already allows for randomized play, it seems natural to consider them. Here, we specifically consider maximal lotteries as the underlying voting rule of a 22-player COG. Maximal lotteries (ML) are a probabilistic, Condorcet consistent voting rule, i.e., they select the action that beats every other action in a heads up comparison if one exists; otherwise, they specify a distribution over candidates that will be preferred to every other voting rule by a majority of voters in expectation. The maximal lottery problem can be formulated as a symmetric, two-player, zero-sum bi-matrix game (minxmaxyx⊤Ay _x _yx Ay) where each entry in A, called the margin matrix, equals the net frequency with which one candidate was ranked above another in the population of votes. Here, we assume the NE has full support. Therefore, the maximum lottery best response must return a fully-mixed result. In a COG, the margin matrix depends on the population of votes through the other player’s strategy. Let the margin matrix be Ai∈ℝ|i|×|i|A_i ^|A_i|×|A_i|. AiA_i here depends on x−ix_-i, i.e., Ai=Ai(x−i)A_i=A_i(x_-i). The value of a symmetric, zero-sum game is zero and all actions in the support achieve this value at the NE, so we know that Aiy=Aixi=uiML(xi)=A_iy=A_ix_i=u^ML_i(x_i)=0; we are looking for a symmetric NE of that game so y=x=xiy=x=x_i. It can be shown that Aixi=[x−i⊤Wiℓxi]ℓ=A_ix_i=[x_-i W_i x_i]_ =0 where WiℓW_i is a constant matrix dependent only on the fixed preference data ρi _i and ℓ∈[|i|] ∈[|A_i|]. Therefore, we are looking for an xix_i and x−ix_-i that satisfy x−i⊤Wiℓxi=0∀i,ℓx_-i W_i x_i=0\,\,∀ i, subject to xix_i restricted to the given support for each player. Empirically, we find that the resulting quadratic constraints are generally not convex (the relevant matrices are not positive semi-definite). This ultimately results in a system of quadratic equality constraints (QCQP), an NP-hard problem [51]. Note a solution exists; we state QCQP complexity to express the general difficulty of computing its solution. Appendix E Metrics E.1 Meta-Game Analysis Continued The meta-game analysis in Section 4.2.2 suggested measuring regret as the probability of electing a fixed hindsight action over the online algorithm for fixed regularization parameters p. Alternatively, we can deploy our regularized best response to plot a curve showing the probability of selecting one of the algorithms (xi,tx_i,t or zi∗z_i^*) as we vary the noise p from 0 to 11 with μi _i as uniform and q≪1q 1 held fixed. Area between the curve and a constant line at 0.50.5 would provide a notion of how strong the selection bias is towards one algorithm or another. We present the probability of hindsight being selected by BRi(p,q=0.1,μi=[1/2,1/2]) BR_i^(p,q=0.1, _i=[ 12, 12]) in Figure 8(b) along with this accompanying area metric in Figure 8(c). E.2 Game Space (a) Exploitability (b) Hindsight Winrate (c) AUC of (8(b)) (d) Hindsight MoV Figure 8: We evaluate our (SGF-based) FTRL approach (psp_s is the solver’s parameter) on the Atari evaluation game according to the metrics in Section 4.2 and Appx. E. (8(a)) EMD as defined in Section 4.2.1, eqn. (5); (8(b),8(c)) Hindsight winrate and area measurement from Section 4.2.2—(8(c)) plots the ’s seen in (8(b)) at t=100t=100 with p on the x-axis; (8(d)) margin of victory (MoV) as described in Section E.2. Panels (8(b)) and (8(d)) set ps=1/t+1p_s= 1t+1. FTRL can also be considered a smoothed-FP approach. The classical approach (3) can be reinterpreted as taking the game as fixed, then finding the closest strategy z to xix_i that achieves optimality (rationality) for player i, and finally reporting the difference between those two strategies in payoff space. Instead, we can take the strategy xix_i as fixed, find the “closest” game such that player i’s current strategy is rationalized, and then report the difference between those two games. This dual approach, also considered in other works [25, 31], is actually analogous to the standard view taken in social choice. Specifically, margin of victory counts the number of votes that must be altered for a given candidate to win the election. In our lottery / infinite voter population model, it is easy to solve; we simply calculate what proportion of votes in the population need to be altered for candidates to tie. Moreover, this concept extends to the online setting via the meta-game approach described above by measuring how many votes must be altered in the vote population generated across all T rounds. Figure 8(d) displays this approximation metric. Appendix F Algorithms We discuss several practical learning algorithms inspired by work on normal-form games. A best response operator regularized towards strategy μi _i with regularizer R(z,μi)R(z, _i), pt>0p_t>0, BRi(pt,q,μi)([x−i,t]) BR_i^(p_t,q, _i)([x_-i,t]) =argmaxz−ptR(z,μi)+u¯i,t(z,[x−i,t]) = *arg\,max_z\-p_tR(z, _i)+ u_i,t(z,[x_-i,t])\ (57) forms the crux of many of these techniques including: • Follow the regularized leader [48, 59] is a no-regret learning algorithm with time-average convergence to coarse-correlated equilibria [35]; set xi,0=argminzR(z,μi)x_i,0= *arg\,min_zR(z, _i); then xi,t+1 x_i,t+1 =argmaxz−1t+1R(z,μi)+∑t′=1t1t+1ui,t′(z,x−i,t) = *arg\,max_z\- 1t+1R(z, _i)+ _t =1^t 1t+1u_i,t (z,x_-i,t)\ (58) =argmaxz−1t+1R(z,μi)+u¯i,t(z,[x−i,t]) = *arg\,max_z\- 1t+1R(z, _i)+ u_i,t(z,[x_-i,t])\ (59) which, c.f. (57), suggests BR(pt,q,μi)(x−i,t) BR^(p_t,q, _i)(x_-i,t) with pt=1/(t+1)p_t=1/(t+1); • Fictitious play is a related algorithm in which each player best responds to the historical play of its co-players [19, 55]; smooth (regularized) variants enjoy regret guarantees [38, 29, 12, 13], • Homotopy [32] and adaptive regularization [58, 52] methods all guide the algorithm through solving a curricula of games (using regularized best responses) that ends at the solution of the original game of interest. And, in the case where a voting rule (e.g., scoring rule) induces a traditional normal-form game (see Appx. A.2), we can re-use any normal-form game solver as well. We examine both the follow the regularized leader (FTRL) and homotopy style of approaches in Section 5. Appendix G Visualization The ability to visualize and analyze an equilibrium solution is important for diagnostics, particularly in game-theoretic evaluation [44, 45]. In these works, an action aia_i’s rating is its expected payoff at equilibrium, and visualizations are given to show how each of another player’s actions aja_j contribute to the rating of aia_i. Here, we aim to provide analogous tools for COGs despite the lack of utility functions. As mentioned earlier, some voting rules induce NFGs, for which we can reuse prior visualization and analysis techniques. For the more general case, we can consider breaking down the probability mass placed on an action aia_i at equilibrium into its contributions from each of player j’s actions. To do so, we leverage techniques in cooperative game theory, specifically Shapley values, although other power indices are possible. Shapley values satisfy an efficiency property that ensures the sum of the contributions from each action aja_j equals the probability mass placed on aia_i (xi,aix_i,a_i). The key primitive used in defining a Shapley value, and cooperative game theory general, is the characteristic function which acts on sets of actions. We define the characteristic function, cic_i applied to a subset of actions, ^j⊆j A_j _j, to be the probability mass placed on aia_i in player i’s best response when only actions ^j A_j are available to player j; we select the uniform distribution over winning actions as the unique best response value. We define player j’s strategy over ^j A_j to be proportional to its original distribution over ^j A_j (i.e., normalized to sum to 11), akin to omitting abstained votes. For example in Chicken, the Shapley value breakdown of the final expected rank for the row player’s actions at NE, [0.5,0.5][0.5,0.5], are: [swervestraightswerve-0.250.75straight0.75-0.25]. bmatrix&$swerve$&$straight$\\ $swerve$&$-0.25$&$0.75$\\ $straight$&$0.75$&$-0.25$ bmatrix. (60) When the row player swerves, if the column player swerves, the row player could have achieved a better outcome by going straight, so the column player’s decision to swerve contributes negatively (−0.25-0.25) to the row player’s rating of swerve. On the other hand, if the column player goes straight, the row player’s decision to swerve achieves a much better outcome than if the row player had chosen to go straight which would have resulted in a collision. Appendix H Experiments H.1 Atari In the Atari experiments, the two sources of stochasticity arise from a) the random usurper ballots and b) the Dirichlet sampling process described in Section 4.1. Recall that this noise is used to regularize and render the best response operator continuous. We use this regularized best response operator BRi(p,q,μi) BR_i^(p,q, _i) both as part of the FTRL-inspired update and to evaluate the learned strategy profile (see Section 4.2). We fix a solver_seed for the random noise generated for the FTRL solver as well as a separate eval_seed to evaluate the solution returned by the solver. Every time the regularized best response operator is evaluated, we sample a best response according to the procedure described in Section 4.2 (and Algorithm 1) num_samples times; we then average the sampled best responses to give the regularized best response. Table 2 lists the hyperparameters used in the Atari experiments. Figure 3 displays the mean and standard error over this set of random experiments. q μi _i # of solver_seeds # of eval_seeds num_samples Figures 3(a) & 8(c) 0.10.1 uniform 1010 10001000 100100 Figures 3(b) & 8(d) 0.10.1 uniform 1010 100100 100100 Table 2: Atari Hyperparameters. H.2 Lost at Sea H.2.1 Election instructions The following reproduces the exact instructions on the election process provided to participants in the Lost at Sea dataset from [54]. Below is an overview of the election process. 1. Indicating interest - You will first be asked to indicate how much you want to become the group leader on a scale from 0 to 10. 2. Ranking your teammates - You will rank your three teammates, with your preferred leader at position 1, the second most preferred leader at position 2, and the third most preferred leader at position 3. You cannot vote for yourself. We will use your answers to these two questions to select the leader: • The two group members who express the most interest in becoming the leader will be selected as candidates for the election. If several group members choose the same number, the computer will randomly determine the order of these group members. • The highest-ranked candidate among the two will be elected as leader. If both candidates tie, the decision will be made randomly. With this process, you are asked to rank your team members before knowing who the candidates are. Only the rankings of the two group members who are not candidates will be considered. This ensures that you cannot vote strategically to increase your own chances of being elected as the leader. Therefore, it is in the interest of all group members to provide their true, preferred ranking of the other group members. H.2.2 Stochastic Outcomes To handle stochastic election outcomes, we consider the distribution defined by the following stochastic process. First sample a co-player action profile a−i∼x−ia_-i x_-i. Then, independently sample a single (counterfactual) election outcome for every one of player i’s actions given a−ia_-i. We then rank player i’s actions given that realized set of outcomes. We then repeat and aggregate these preferences using the chosen social choice voting rule. Figure 9: Election (Table 1) LLE Equilibrium. H.2.3 Election Case Study: Human Play Not in Equilibrium We examine the election data in Table 1, which contains both the actions the players took (wtls & votes) as well as their prefs for election outcomes. We do not know whether the players’ actions were sampled from a mixed strategy. For the sake of this analysis, we assume the players chose the actions listed in the table deterministically. Under this assumption, calculations suggest the strategy profile listed in Table 1 is not a maximal lottery (ML) NE. In particular, Koala is not playing a best-response. It is identified that if they reduced their wtl to remove themselves from the runoff, then the two competing candidates would be Lion and Chicken ranked 1st and 2nd by their preference rankings (pref). Across the players, Chicken wins once against Lion (Pig’s vote) and loses once (Koala’s vote). The winner is then either Chicken or Lion with equal probability. This is compared to the status quo where Koala enters a high wtl such that Koala and Lion enter the runoff. Koala beats Lion twice (Pig and Chicken both rank it higher) so Koala is deterministically elected, however, strangely, Koala ranks itself 3rd in its own preference ranking (pref) despite its high wtl. Player Chicken is identified as not playing a best response by our sample best response estimate (p=0p=0, q=0.1q=0.1, num_samples=100 num\_samples=100), but this is false. The sample best response we compute actually achieves the same value, but probabilistically. This is likely due to the sample estimate not having converged yet. The suggested best response is to submit a much higher wtl (10) in order to force the runoff to be between Lion and Chicken, ranked 0 and 2 by Chicken. They have equal wins so will be selected randomly giving Lion an average score of 1 for the outcome regardless of the vote they pair with wtl=10 since their vote cannot contain a comparison between Chicken (themselves) and Lion by rules of the election. Next, we demonstrate solving for an equilibrium of the voting game. In this demonstration, we use Borda as the voting rule. As mentioned earlier, Borda is a scoring rule which induces a normal-form game on the COG. We then re-use existing NFG solving techniques to approximate a limiting logit equilibrium (LLE) [47]. We use the Jax [16] package polarix with min_temperature 0.10.1 to compute the LLE. Note that we use Borda here for efficiency sake, but it is possible to apply the same general technique to maximal lotteries with differentiable convex optimization libraries such as cvxpylayers in JAX [2, 16]. In the LLE shown in Figure 9, Chicken and Lion spread most mass over high wtl actions, so they are likely to be in the running. This means Pig and Koala’s votes will have impact in the election. Both Chicken and Lion want themselves to win and are ranked favorably by Pig and Koala although not in the same order. Pig prefers Chicken. Koala prefers Lion. Expectedly, Pig ranks Chicken above Lion in all its votes in the LLE support. Koala ranks Lion higher in all its votes. This should lead to Lion and Chicken being elected with equal probability (confirmed empirically in simulation). According to the players’ outcome preferences (pref), the essential (bipartisan) set of a Maximal Lottery consists of Koala, Chicken, and Lion. Why are Chicken and Lion in the support of the LLE, but Koala is not? Koala actually prefers both Lion and Chicken to itself, so it withdraws from the election to steer the result towards either of the two (preferably Lion). The story is similar with Pig, who ranks themselves last. H.2.4 Election Case Study: Human Play in Equilibrium We similarly examine the election data in Table 3. Calculations suggest each player’s strategy listed in Table 3 is a max-entropy, maximal lottery best response to each other (i.e., a Nash equilibrium). We use the same settings as before (p=0p=0, q=0.1q=0.1, num_samples=100 num\_samples=100). In particular, computing the max-entropy, maximal lottery for Bear reveals its best responding actions (essential set). We summarize Bear’s best response strategies as follows: • When wtl ≤ 6, Bear always ranks Rabbit over Frog because it is possible Bear is not selected in a runoff (wtl=6), and therefore its vote (and Dog’s) matters. In this case, Rabbit wins, which is Bear’s ideal outcome; • If Bear’s wtl >> 6, then Bear is selected as the candidate against Rabbit and Bear’s vote doesn’t matter (Dog and Frog’s do). Rabbit wins, which is Bear’s ideal outcome. Table 3: Election A: (Pure) Strategies are in Equilibrium. voter vote wtl pref Bear ≻ ≻ 5 ≻ ≻ ≻ Rabbit ≻ ≻ 8 ≻ ≻ ≻ Dog ≻ ≻ 3 ≻ ≻ ≻ Frog ≻ ≻ 6 ≻ ≻ ≻ Borda LLE Computing an LLE of this election using Borda (Table 3), we find the following equilibrium description with equilibrium presented in Figure 10. Rabbit and Dog spread most of their mass over low wtl actions, which removes them from the running. Bear and Frog spread their mass over high wtl actions, so they are likely to be in the running. Dog would prefer itself to win, but Dog is low-ranked by everyone. Given that others might not let Dog win the election, Dog submits a low wtl to steer the election towards Bear, its third favorite, given Rabbit is not in the runoff. Rabbit is high ranked by all but wants to avoid Frog being elected, which could happen if Rabbit and Frog are in a runoff. By submitting a low wtl, Rabbit can influence the election away from Frog and towards Bear which is Rabbit’s 2nd ranked option. Bear ranks itself lower than Frog, so would be happy with Frog winning. Frog essentially feels similarly, but with itself and Bear swapped in the ranking. After sampling ten thousand election outcomes under the LLE, we observe that Bear is elected > 99% of the time. It is interesting that the LLE arrives at Bear being elected because Rabbit is the strong Condorcet winner. Figure 10: Election (Table 3) LLE Equilibrium.