💰 quantitative finance

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games

This paper generalizes the Nash equilibrium to "context-ordinal" games by replacing numerical utilities with ordinal preference rankings aggregated via social choice theory, thereby establishing existence conditions, complexity bounds, and learning rules for equilibria derived directly from human preferences without requiring precise utility elicitation.

Original authors: Ian Gemp, Crystal Qian, Marc Lanctot, Kate Larson

Published 2026-05-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ian Gemp, Crystal Qian, Marc Lanctot, Kate Larson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to figure out the best move in a game, like Rock-Paper-Scissors, but you don't have a scoreboard. You don't know that winning gives you "10 points" and losing gives you "0 points." All you know is your own feelings: "I prefer winning to tying, and I prefer tying to losing."

For decades, game theory (the math of strategy) has struggled with this. The famous "Nash Equilibrium"—a state where no one wants to change their strategy—usually requires knowing those exact point values. If you don't have the numbers, the math breaks down.

This paper, "Nash without Numbers," proposes a clever new way to solve this problem. It suggests we stop trying to invent fake numbers and instead use the tools of voting theory (social choice) to find the best move.

Here is the breakdown of their idea using simple analogies:

1. The Problem: The "Silent" Game

In a normal game, if your opponent plays Rock 25% of the time, Paper 30%, and Scissors 45%, you calculate your "expected score" for every move you could make. You pick the one with the highest score.

But in this new setting, you can't calculate a score. You only have a list of preferences. If your opponent plays Rock, you might say, "I prefer Paper over Scissors over Rock." If they play Paper, you might say, "I prefer Scissors over Rock over Paper."

The old math asks: "What is the average score?"
The new math asks: "If we held a vote among all these different scenarios, who would win?"

2. The Solution: The "Crowd Vote" Metaphor

The authors imagine a scenario where your opponent's mixed strategy (their random mix of moves) creates a crowd of voters.

The Analogy: Imagine your opponent's strategy is a weather forecast. It's 25% Sunny, 30% Cloudy, and 45% Rainy.
The Votes: For every type of weather, you have a different preference for what to wear.
- If it's Sunny, you vote: "Shorts > Jeans > Coat."
- If it's Cloudy, you vote: "Jeans > Shorts > Coat."
- If it's Rainy, you vote: "Coat > Jeans > Shorts."
The Election: Now, imagine a massive election where 25% of the voters are "Sunny voters," 30% are "Cloudy voters," and 45% are "Rainy voters."
The Winner: You don't calculate an average temperature. Instead, you run a voting rule (like Borda Count or Maximal Lotteries) on this crowd. The item that wins the election is your "Best Response."

The paper calls this a Context-Ordinal Nash Equilibrium. It's a stable state where, if everyone plays their "voting winner," no one has an incentive to switch their strategy.

3. Why This Matters: Real-World Humans

The paper argues that this is how humans actually think in many situations.

Elections: Voters don't usually say, "I give Candidate A 8.4 points and Candidate B 7.9 points." They just rank them: "A > B > C."
AI Evaluation: When testing AI agents, we often just know which one is "better" in a specific game, but we don't have a universal scorecard to compare them across all games.

The authors tested this on two real-world scenarios:

Video Game Agents: They evaluated AI agents playing Atari games. Instead of using raw scores, they ranked the agents based on how well they did against different tasks. Their new method found a stable "best" mix of agents that was robust against any opponent.
Human Leadership Elections: They analyzed data from a "Lost at Sea" experiment where groups had to elect a leader. They found that humans often didn't vote in a way that matched a perfect equilibrium (they made mistakes or acted strategically in confusing ways). However, their new math could successfully calculate what the "perfect" strategic voting would look like in that messy, real-world scenario.

4. The "Regularization" Trick

One technical hurdle is that voting can be "jumpy." If one extra person changes their vote, the winner might suddenly flip from Candidate A to Candidate B. This makes it hard to learn or find the equilibrium.

The authors introduced a "regularization" trick. Think of it as adding a little bit of noise or confusion to the voting process.

Imagine that occasionally, a voter gets confused and votes for a random option, or the "weather forecast" is slightly fuzzy.
This smooths out the "jumps," making the voting result change gradually rather than suddenly. This allows computers to use standard learning algorithms (like gradient descent) to find the equilibrium, just like they do in games with numbers.

Summary

The paper replaces the concept of "calculating an average score" with "running a weighted election."

Old Way: "If I play Rock, I get 5.2 points on average."
New Way: "If I play Rock, and we hold a vote based on how my opponent plays, Rock wins the election."

By doing this, they created a new kind of Nash Equilibrium that works even when players only have rankings and no numbers, proving that you can find stable, rational strategies without ever needing to assign a specific value to a win or a loss.

Technical Summary: Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games

Problem Statement

Classical game theory relies on the Nash Equilibrium (NE), a concept fundamentally grounded in the maximization of expected numerical utilities. However, in many strategic scenarios—such as elections, human preference elicitation, and agent evaluation—precise cardinal utilities are unavailable or difficult to elicit. While players can often provide ordinal rankings of outcomes, the standard definition of a "best response" (maximizing expected utility) becomes ill-defined when co-players employ mixed (probabilistic) strategies. Previous attempts to address this have either abandoned probability theory for possibility theory, introduced mediated equilibria requiring a third-party coordinator, or restricted analysis to pure strategies. The central challenge is to define a mixed-strategy equilibrium that relies solely on ordinal preferences without assuming access to underlying cardinal utilities.

Methodology

The authors propose a Context-Ordinal Game (COG) framework and a corresponding Context-Ordinal Nash Equilibrium (CO-NE).

1. Context-Ordinal Games (COG)

Unlike traditional Ordinal Games (OG) where players rank joint outcomes globally, a COG assumes players can only rank their own actions conditional on the specific joint actions of their co-players.

Definition: A COG is a tuple $\langle N, A, \rho \rangle$ , where $\rho_i$ maps a co-player's joint action $a_{-i}$ to a preference relation over player $i$ 's actions $A_i$ .
Best Response via Social Choice: To define a best response against a mixed strategy $x_{-i}$ , the authors aggregate the "votes" (ordinal rankings) generated by every possible $a_{-i}$ weighted by its probability $x_{-i}(a_{-i})$ . This creates a population of votes. A Doubly Probabilistic Social Choice Function (dpSCF) is then applied to this population to determine the set of winning actions.
CO-NE: A strategy profile $x$ is a CO-NE if every player's mixed strategy places mass only on actions that win according to the dpSCF applied to the votes generated by the other players' strategies.

2. Existence and Regularization

Existence: The authors prove the existence of a mixed CO-NE under mild conditions. They show that if the dpSCF is upper hemicontinuous (u.h.c.), a fixed point exists via Kakutani's Fixed Point Theorem. They identify that many standard voting rules (e.g., Borda, Maximal Lotteries, Scoring rules) satisfy this when viewed as returning distributions rather than single winners.
Regularization: To ensure continuity and single-valuedness (facilitating learning), the authors introduce a Regularized Best Response. This involves:
1. Perturbation: Randomly replacing a fraction $p$ of the vote population with "usurper" ballots (where a sampled action is top-ranked).
2. Smoothing: Applying a Dirichlet perturbation to the co-player strategy distribution $x_{-i}$ to handle discontinuities at ties.
  This regularization ensures the best-response operator is continuous and single-valued, enabling the use of gradient-based learning.

3. Learning and Approximation Metrics

Since utilities are absent, traditional exploitability metrics cannot be used directly. The paper introduces:

Strategy Space Distance: Measuring the distance (e.g., Earth Mover's Distance) between a player's current strategy and the set of best responses.
Hindsight Winrate: A meta-game analysis comparing the online strategy against a fixed hindsight strategy aggregated via the voting rule.
Distortion Bounds: The paper derives bounds on the suboptimality of CO-NE compared to a classical NE (if utilities existed). It shows that the additive distortion is bounded by the distortion of the voting rule itself, scaled by the variation in payoff sums across different co-player actions.

Key Contributions

Generalization of Nash Equilibrium: The paper provides the first definition of a probabilistic mixed-strategy Nash equilibrium that operates solely on ordinal preferences, generalizing the classical NE.
Theoretical Existence: It establishes the existence of such equilibria under standard conditions on social choice functions, bridging game theory and social choice theory.
Algorithmic Framework: It develops learning rules (specifically Follow the Regularized Leader, FTRL) and regularization techniques to compute these equilibria, addressing the computational challenges of discontinuous voting rules.
Complexity Analysis: The authors demonstrate that computing CO-NE is generally not polynomial-time solvable (NP-hard in certain settings), contrasting with some prior work that sought equilibria in P by sacrificing the traditional factorized structure.
Distortion Analysis: It quantifies the cost of using ordinal information instead of cardinal utilities, providing theoretical bounds on the loss of optimality.

Results and Applications

The authors validate their theory through two distinct applications:

General Agent Evaluation (Atari):
- Setup: Evaluating AI agents against a set of tasks using a performance matrix where agents and tasks are players.
- Method: Agents and tasks are treated as players in a COG. The "payoffs" are replaced by ordinal rankings (e.g., quartile-based grades).
- Outcome: Using FTRL with Social Grading Functions (SGF) and Borda counts, the authors compute a CO-NE. The results show that the "Rainbow" agent emerges as the strongest even under adversarial task distributions, demonstrating robustness. The learning curves indicate convergence and low exploitability.
Human Election Data (Lost at Sea):
- Setup: Analysis of human data from a "Lost at Sea" leader selection task involving 460 participants in 115 groups. Participants submit a willingness-to-lead score and a ranking of teammates.
- Method: The election mechanism is modeled as a stochastic COG. The authors analyze whether human behavior constitutes a CO-NE.
- Outcome: Approximately 30% of elections exhibited pure maximal lottery Nash equilibrium profiles. In the remaining 70%, humans showed incentives to deviate (e.g., strategically lowering willingness-to-lead scores to manipulate the runoff). The authors successfully computed a Limiting Logit Equilibrium (LLE) for specific elections, revealing strategic behaviors (e.g., a player withdrawing from a race to steer the outcome toward a preferred candidate) that align with the CO-NE theory.

Significance and Claims

The paper claims to provide a generalization of the Nash equilibrium that is directly applicable to elicited preferences, which are the fundamental data of human interactions. By replacing expected utility maximization with social choice aggregation, the framework allows for equilibrium analysis in settings where numerical utilities are unknown or non-existent.

The authors emphasize that their approach:

Does not require the discovery of underlying cardinal utilities.
Maintains the factorized structure of traditional mixed strategies (unlike mediated equilibria).
Is robust to mis-specification of utilities, as long as the ordinal ranking remains consistent.
Offers a theoretical and practical toolkit for analyzing strategic behavior in elections and evaluating AI agents without relying on arbitrary numerical scoring.

The work positions itself as a "mathematics without numbers" approach to game theory, leveraging centuries of social choice theory to solve the problem of equilibrium in ordinal settings.