Fundamental Limits of Game-Theoretic LLM Alignment: Smith Consistency and Preference Matching

Zhekun Shi, Kaizhao Liu, Qi Long, Weijie J Su, Jiancong XiaoSubmission to ICLR 2026 · Rejected

TL;DR

Game-theoretic alignment frameworks like Nash Learning from Human Feedback (NLHF) are remarkably robust: social choice guarantees such as Condorcet and Smith consistency hold under a wide range of noisy or transformed payoff functions as long as symmetry and majority signs are preserved. However, the authors prove a fundamental impossibility result: no smooth, scale-invariant game-theoretic payoff can achieve exact preference matching (preserving the exact distribution of diverse human opinions), revealing an intrinsic trade-off in game-theoretic LLM fine-tuning.

What Problem Does This Paper Address?

Standard Reinforcement Learning from Human Feedback (RLHF) often collapses under cyclic or conflicting human preferences because it assumes choices follow a simple scalar reward model (the Bradley-Terry-Luce, or BTL, model). To handle cyclic preferences, recent approaches frame alignment as a two-player zero-sum game called Nash Learning from Human Feedback (NLHF).

Prior work showed that when players play a game whose payoff is the true human preference probability $P(y \succ y')$, NLHF satisfies key social choice axioms:

  1. Condorcet consistency: Always outputting a candidate that beats every other candidate in pairwise majority comparisons, when one exists.
  2. Smith consistency: Always selecting from the smallest set of responses that pairwise dominate all alternatives outside the set (the Smith set).
  3. Diversity via mixed strategies: Avoiding collapse to a single deterministic output when no single winner exists.

In practice, however, the true preference matrix is never known. We only have access to a noisy, learned preference model $\Psi(P)$. This paper asks two foundational questions:

  • Under what transformations $\Psi$ do these desirable alignment properties survive?
  • Can game-theoretic alignment preserve minority viewpoints through preference matching—producing a policy whose output probabilities match the exact ratio of human preference?

Methods

The authors analyze the generalized two-player zero-sum game: $$\max_{\pi} \min_{\pi'} \mathbb{E}_{x \sim \rho} \left[ \mathbb{E}_{y \sim \pi, y' \sim \pi'} \left[ \Psi\left(P(y \succ y' \mid x)\right) \right] \right]$$ where $\Psi: [0, 1] \to \mathbb{R}$ transforms the preference probabilities (and can even be stochastic).

The authors derive necessary and sufficient mathematical conditions on $\Psi$ under the mild assumption of no exact ties ($P(y \succ y') \neq 1/2$):

  • Condorcet consistency: Requires only that $\Psi(t) \ge \Psi(1/2)$ for $t \ge 1/2$ and $\Psi(t) < \Psi(1/2)$ for $t < 1/2$.
  • Diversity (mixed strategy when no Condorcet winner exists): Requires continuity at $1/2$ plus $\Psi(t) + \Psi(1-t) \ge 2\Psi(1/2)$.
  • Smith consistency: Requires the game to be symmetric up to a constant shift: $\Psi(t) + \Psi(1-t) = 2\Psi(1/2)$ along with $\Psi(t) < \Psi(1/2)$ for $t < 1/2$.
  • Preference Matching Impossibility: Using Karush–Kuhn–Tucker (KKT) conditions, the authors prove that no payoff matrix whose off-diagonal entries depend smoothly on probability ratios $f(\pi^*_i / \pi^*_j)$—independent of total response count $n$—can have a unique Nash equilibrium matching an arbitrary target policy $\pi^*$.

Datasets

The authors validate their theoretical findings using:

  • TL;DR dataset: Used as the prompt collection dataset for summarization fine-tuning via the Transformer Reinforcement Learning (TRL) library.
  • Pythia-1B: Pre-trained and SFT models (pythia-1b-deduped-tldr-sft) used as the base LLM policy.
  • Pythia-1B Reward Model: (pythia-1b-deduped-tldr-rm) used in combination with the BTL formulation to construct baseline preference probabilities.

No new benchmark datasets were introduced.

Key Insights and Ideas

  • Condorcet consistency is surprisingly forgiving: You do not need an accurate reward scale or monotonic mapping. As long as your preference model correctly predicts which response is above or below $1/2$, the policy is guaranteed to converge to the Condorcet winner.
  • Smith consistency requires skew-symmetry: Enforcing $\Psi(t) + \Psi(1-t) = 2\Psi(1/2)$ guarantees that the model only outputs candidates in the top cycle (Smith set) and automatically outputs a mixed strategy if $|S_1| > 1$. Interestingly, the log-odds mapping $\Psi(t) = \log(t / (1 - t))$ satisfies this, offering a natural generalization of RLHF to cyclic preferences.
  • Many current preference models break Smith consistency: Models that fail to satisfy skew-symmetry (i.e., $P_\theta(y \succ y') + P_\theta(y' \succ y) \ne 1$) lose Smith consistency guarantees unless explicitly skew-symmetrized.
  • The Impossibility of Preference Matching: While mixed strategies prevent total mode collapse, a zero-sum game cannot be tuned to uniquely reproduce target preference ratios without knowing the total action space size $n$ or the raw unnormalized policy values. Game-theoretic alignment is inherently a tool for finding dominant winners, not for proportional representation.

Key Results

  • Empirical Robustness to Noise: Training with the Nash-MD algorithm on $4\times$ NVIDIA A800 GPUs with random perturbation levels ($\sigma = 0.15$) near $1/2$ did not hurt alignment. In fact, it slightly improved the training reward margin and implicit reward accuracy compared to the unperturbed baseline.
  • Random vs. Deterministic Perturbations: While random noise near or away from $1/2$ maintains or improves training stability, deterministic bias (e.g., systematically shifting probabilities away from or toward $1/2$) degrades convergence speed, margins, and accuracy, confirming the theoretical importance of unbiasedness around $1/2$.

Limitations and Future Work

  • No-Tie Assumption: Theoretical results rely on $P(y \succ y') \neq 1/2$. Extending proofs to account for exact ties remains an open problem.
  • Smoothness in Impossibility: The preference matching impossibility theorem assumes $\Psi$ (and the payoff generator $f$) is smooth ($C^1$); whether it holds for non-smooth or merely continuous mappings is still unknown.
  • Reference Model Regularization: The analysis focuses on pure zero-sum objectives without the KL-divergence regularizers typically added in practical RLHF/NLHF pipelines.
  • Skew-Symmetric Architectures: Since several popular preference models violate skew-symmetry, future work must focus on architectures that natively guarantee $P_\theta(y \succ y') + P_\theta(y' \succ y) = 1$.

Summary updated

Abstract

Nash Learning from Human Feedback (NLHF) is a game-theoretic framework for aligning large language models (LLMs) with human preferences by modeling learning as a two-player zero-sum game. When the payoff is defined by the true underlying preference, the framework guarantees desirable alignment properties. However, the ground-truth preference matrix is often unavailable in practice due to limited or noisy data, which substantially constrains the effectiveness of this game-theoretic approach to LLM alignment. In this paper, we systematically study what payoff based on the pairwise human preferences can yield desirable alignment properties. We establish necessary and sufficient conditions for Condorcet consistency, diversity through mixed strategies, and Smith consistency. These results provide a theoretical foundation for the robustness of game-theoretic LLM alignment. Further, we show the impossibility of preference matching, i.e., no smooth and learnable mappings of pairwise preferences can guarantee a unique Nash equilibrium that matches a target policy, even under standard assumptions like the Bradley-Terry-Luce model. This result highlights a fundamental limitation of game-theoretic LLM alignment.
BibTeX
@misc{shi2025fundamental,
  author = {Zhekun Shi and Kaizhao Liu and Qi Long and Weijie J Su and Jiancong Xiao},
  title = {{Fundamental Limits of Game-Theoretic LLM Alignment: Smith Consistency and Preference Matching}},
  year = {2025},
  eprint = {2505.20627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.20627},
}
Figure