acceptodds
Under review as a conference paper at ICLR 2027

Learning in Continuous Games from Pairwise Preference Feedback

Abstract

We study learning in continuous games when players receive only pairwise preference feedback, revealing which of two actions is preferred but neither payoff values nor preference magnitudes. We first show that standard external regret and coarse correlated equilibria are not identifiable from this ordinal information: the same sequence of play can incur zero and linear regret in two ordinally equivalent games, while the distributions that remain CCE across all cardinal representations consistent with the same preferences are exactly those supported on pure Nash equilibria. Motivated by this gap, we develop a first-order ordinal theory based on normalized unilateral preference directions, introducing an ordinal directional regret benchmark and corresponding equilibrium notions. We show that block-normalized pseudogradient dynamics achieve sublinear ordinal regret and, under additional structure, Nash-convergence guarantees. We then use a one-bit comparison estimator to implement these dynamics from finite pairwise comparisons. With one comparison per player and round, the resulting algorithm achieves sublinear finite-resolution ordinal regret against arbitrary opponent behavior and, in ordinal potential games, almost-sure last-iterate convergence to the Nash set. Our results provide regret, dynamics, and equilibrium guarantees directly from preference feedback without reconstructing cardinal utilities.

Primary area:
learning theory
Keywords:
learning in games, online learning, pairwise comparison feedback, no-regret learning, continuous games, Nash equilibrium

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_CYe3OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies learning in continuous games where players only have the access to noisy pairwise comparisons, without seeing the actual payoffs. It first shows that standard external regret and coarse correlated equilibria (CCE) cannot be uniquely determined from such ordinal feedback. In particular, Theorem 3.1 shows that the distributions remaining CCE under all equivalent utility representations are exactly those supported on pure Nash equilibria. The authors solve this with a framework based on the normalized gradient, showing that this projected normalized gradient play achieves sublinear ordinal regret. More interestingly, Under additional assumptions on ordinal potential games, Theorem 5.2 also establishes almost-sure last-iterate convergence to the Nash set. However, the whole paper is purely theoretical, and there is no experimental evaluation. To be very honest, I am not able to verify all the proofs in the appendix, particularly the stochastic approximation argument for Theorem 5.2, which is actually one of the critic strengths on my mind.

Critical strengths

I like the observation that standard learning objectives in games can change under different numerical representations of the same preferences. The example in Figure 1 is particularly useful. Even though the games have identical preferences, standard gradient play can behave differently because the gradients of individual players are scaled differently. Normalizing each player's gradient addresses this particular issue. Together with Theorem 3.1, this gives a good motivation for studying learning objectives that depend only on ordinal information. Besides I also find Theorem 5.2 interesting. Establishing almost-sure convergence to Nash equilibria using only noisy comparisons is a stronger result than simply bounding a newly defined regret measure. The discontinuity of normalized gradients near stationary points also makes the convergence analysis nontrivial. I appreciate that the authors address this issue through differential inclusions.

Critical weaknesses

My biggest concern is whether the proposed framework and its regret guarantees constitute a sufficiently new contribution.

Ordinal directional regret is essentially linearized regret with each player's gradient normalized. Given this definition, Theorem 4.1 seems to follow from the standard online gradient descent analysis. The connection between ordinal regret and the proposed equilibrium residual in Equation (7) also appears to be a direct consequence of the definitions. While these results are mathematically reasonable, I do not see much technical novelty in them.

I have a similar concern about Theorem 5.1. The comparison-based estimator is closely related to existing gradient estimation methods, and the regret bound is established for the finite-resolution field that the estimator targets. The main issue is that this is not the original ordinal directional regret introduced earlier in the paper. In fact, Proposition E.1 gives a strongly convex example where the finite-resolution regret stays bounded while the original ordinal regret grows linearly.

Theorem 5.2 is probably the most interesting technical result. However, the convergence guarantee is restricted to ordinal potential games. In this setting, all players' comparisons are consistent with a common potential function, making the algorithm closely related to comparison-based optimization of that potential. I would like to understand what additional difficulties arise from the multi-agent setting, and how much of the analysis goes beyond existing results for comparison-based optimization. As it stands, I find the result interesting but its novelty somewhat difficult to assess.

Moreover, the practical motivation is not entirely clear to me. The paper assumes that comparisons have a fixed error probability independent of the difference between the two actions. This is a rather specific noise model. In settings such as RLHF or recommendation systems, comparisons between nearly identical choices are often less reliable. As the authors note, other noise models may allow numerical information to be recovered through repeated comparisons. I would like to see a clearer discussion of when the proposed purely ordinal setting is the right model, especially since the paper does not provide experiments or a concrete application.

Questions for authors
  1. Can the authors give a more concrete interpretation of small ordinal directional regret in terms of players' preferences? For example, under convexity or other additional assumptions, can it be related to the improvement achievable by a fixed deviation?

  2. Theorem 5.1 only bounds regret for the finite-resolution field, and Proposition E.1 shows that this does not generally imply sublinear regret for the original normalized field. Are there reasonable additional assumptions under which the algorithm can guarantee the original ordinal directional regret? I think this would substantially strengthen the result.

  3. What is the main technical difference between Theorem 5.2 and existing convergence results for comparison-based optimization? Since the theorem assumes an ordinal potential game, it would be helpful to clarify which parts of the proof are specific to the multi-agent setting.

3 comments

We thank the reviewer for their time, useful feedback and constructive questions.

Technical contributions. Theorem 4.1 uses the standard projected OGD inequality; we will make this explicit and cite Zinkevich (2003). Equation (7) is the associated regret–residual identity, and the comparison estimator builds on existing work as discussed in the paper. Our technical contributions include the exact ordinally robust CCE characterization (Theorem 3.1) which we believe is of independent interest, finite-resolution regret and its separation from the original benchmark even for smooth strongly convex costs (Theorem 5.1 and Proposition E.1), and almost sure Nash convergence (Theorem 5.2). Our response to Q2 below adds a bound on the (original) ordinal regret as suggested, and our response to Q3 discusses the significance and the convergence analysis of Theorem 5.2. In particular, the proof requires graph consistency of the finite-comparison fields and a projected Lyapunov analysis near stationary blocks to establish the result. It also yields a standalone single-agent pseudoconvex optimization guarantee.

Responses to questions:

Q1. Can the authors give a more concrete interpretation of small ordinal directional regret in terms of players' preferences? For example, under convexity or other additional assumptions, can it be related to the improvement achievable by a fixed deviation?

Ordinal directional regret measures the cumulative normalized first-order incentive to move toward a fixed alternative.

For a fixed unilateral alternative yiy_i, let hi,t(yi)=⟨Di(xt),xi,t−yi⟩h_{i,t}(y_i)=\langle D_i(x_t),x_{i,t}-y_i\rangle and gi,t=∥∇iJi(xt)∥.g_{i,t}=\|\nabla_iJ_i(x_t)\|.

Along the feasible unilateral move xi,t(λ)=(1−λ)xi,t+λyix_{i,t}(\lambda)=(1-\lambda)x_{i,t}+\lambda y_i for λ∈[0,1]\lambda \in [0,1], the chain rule gives at λ=0\lambda=0, ddλJi(xi,t(λ),x−i,t)=−gi,thi,t(yi).\frac{d}{d\lambda} J_i(x_{i,t}(\lambda),x_{-i,t}) = -g_{i,t} h_{i,t}(y_i).

Thus hi,t(yi)>0h_{i,t}(y_i)>0 means that a sufficiently small move toward yiy_i is strictly preferred. Since Regi,TD=sup⁡yi∈Xi∑t=1Thi,t(yi),Reg_{i,T}^{D} = \sup_{y_i\in\mathcal X_i}\sum_{t=1}^{T}h_{i,t}(y_i), sublinear ordinal directional regret means that no fixed alternative provides a persistent positive average of these normalized first-order gains.

  • Under blockwise pseudoconvexity, every strictly preferred full deviation also has positive directional gain: Ji(yi,x−i,t)<Ji(xt)⟹hi,t(yi)>0.J_i(y_i,x_{-i,t})<J_i(x_t) \Longrightarrow h_{i,t}(y_i)>0. The converse need not hold for a full deviation because the move can overshoot.

  • Under convexity of JiJ_i with respect to its iith variable, Ji(xt)−Ji(yi,x−i,t)≤gi,thi,t(yi)J_i(x_t)-J_i(y_i,x_{-i,t})\le g_{i,t}h_{i,t}(y_i). Hence every fixed yiy_i satisfies $\sum_{t:g_{i,t}>0} \frac{J_i(x_t)-J_i(y_i,x_{-i,t})}{g_{i,t}} \le \operatorname{Reg}_{i,T}^{D}.$ Each numerator is the signed cost reduction from switching completely to yiy_i. At zero-gradient rounds, convexity implies that the current action is already a unilateral minimizer, so no positive deviation gain is omitted. Thus, sublinear ordinal regret bounds the cumulative gain of every fixed deviation on this normalized scale. It does not, in general, imply sublinear ordinary (unnormalized) external regret.

We will add these interpretations and the convexity bound to the revised manuscript.

Q2. Theorem 5.1 only bounds regret for the finite-resolution field, and Proposition E.1 shows that this does not generally imply sublinear regret for the original normalized field. Are there reasonable additional assumptions under which the algorithm can guarantee the original ordinal directional regret? I think this would substantially strengthen the result.

Yes, suppose $J_i(x_i,x_{-i}) =\phi_i\left(q_i(x_i,x_{-i})\right),$ where ϕi′>0,\phi_i'>0, and qi(⋅,x−i)q_i(\cdot,x_{-i}) is quadratic for every fixed opponents’ profile. Then Diδ(x)=Di(x)D_i^\delta(x)=D_i(x) for every comparison radius δ>0\delta> 0 for which the symmetric queries are feasible. Consequently, the finite-resolution and original ordinal regrets coincide pathwise, and all guarantees of Theorem 5.1 apply unchanged to the original ordinal regret under the same feedback assumptions, stepsizes, and comparison radii. This uses one comparison per player and round against arbitrary opponents. Only the dependence on the player’s own action must admit a quadratic representation; its coefficients may depend on the opponents’ actions. Convexity and potential structure are unnecessary for this regret result.

(Response to Q1 (continued))

Proof of the field identity Diδ(x)=Di(x)D_i^\delta(x)=D_i(x) above. For a quadratic unilateral cost, the second-order terms cancel in the symmetric difference, giving the exact identity $q_i(x_i+\delta u,x_{-i}) - q_i(x_i-\delta u,x_{-i}) = 2\delta\langle\nabla_iq_i(x),u\rangle$. The regular increasing transformation preserves both the comparison sign and the normalized gradient direction. Thus the finite comparison sign equals sgn⁡⟨∇iJi(x),u⟩\operatorname{sgn}\langle\nabla_iJ_i(x),u\rangle. For a nonzero block gradient, spherical symmetry gives $D_i^\delta(x) = \frac{1}{\kappa_{d_i}} \mathbb E_{U_i}!\left[\operatorname{sgn}\langle\nabla_iJ_i(x),U_i\rangle,U_i\right] =\frac{\nabla_iJ_i(x)}{|\nabla_iJ_i(x)|} =D_i(x).$ At a stationary block, ϕi′>0\phi_i'>0 implies that ∇iqi(x)=0\nabla_iq_i(x)=0 as well. The quadratic difference identity then shows that the two symmetric query costs are equal for every direction. Hence every comparison sign is zero, giving Diδ(x)=Di(x)=0D_i^\delta(x)=D_i(x)=0. The field identity therefore holds even at stationary blocks, without requiring gradient norms to be bounded away from zero.

We thank the reviewer for suggesting this extension. We will add this corollary and its proof to the revised manuscript.

Q3. What is the main technical difference between Theorem 5.2 and existing convergence results for comparison-based optimization? Since the theorem assumes an ordinal potential game, it would be helpful to clarify which parts of the proof are specific to the multi-agent setting.

We agree that ordinal potential games admit a comparison-based optimization interpretation: every unilateral cost comparison coincides with the corresponding potential comparison, as stated in Section 5.3.

Theorem 5.2 already yields a single-agent result of independent interest. Taking N=1N=1 and Φ=J\Phi=J, it establishes almost sure convergence of the actual iterates to the global minimizer set of a smooth pseudoconvex objective over a compact convex feasible set, using one noisy comparison per iteration under the stated assumptions. This guarantee is not established by the smooth convex optimization results of Saha et al. (2021).

In the multi-agent setting, the theorem analyzes simultaneous, projected, block-normalized updates from noisy unilateral comparisons. The additional distinctions compared to the optimization setting concern the available oracle, the block dynamics, and the convergence target:

  • Unilateral comparison oracle. Each player compares two of its own actions while opponents’ actions remain fixed. The oracle does not provide comparisons between arbitrary joint profiles. For example, the comparisons with a global best-so-far candidate used by Saha et al. (2021) are not generally available.

  • Separate block normalization. The single-valued preference-direction field DD (defined in eq. (3)) normalizes each player’s gradient separately, rescaling the blocks by different factors. This field can be discontinuous at profiles where one gradient block vanishes while others remain nonzero, even though the globally normalized potential gradient is continuous there. Figure 1 also illustrates that block normalization makes learning trajectories invariant under regular increasing cost transformations.

  • Assumptions and convergence target. The theorem does not require joint convexity of the potential. Under the stated nondegeneracy assumption, blockwise pseudoconvexity of the players’ costs identifies constrained stationary points of the potential with Nash equilibria. Such equilibria need not globally minimize the potential. Consequently, the smooth convex optimization guarantees of Saha et al. (2021) do not directly establish the claimed convergence result.

The main technical challenge we address. The comparison estimator satisfies E[D^t∣Ft]=Dδt(xt)\mathbb{E}[\widehat{D}_t |\mathcal{F}_t] = D^{\delta_t}(x_t). Vanishing comparison radii do not generally imply ∥Dδt(xt)−D(xt)∥→0\|D^{\delta_t}(x_t)-D(x_t)\|\to0 along moving iterates near stationary blocks. This difficulty already occurs with one player; block normalization additionally requires handling it when only some players are stationary. Thus, the convergence argument cannot simply treat the updates as asymptotically unbiased estimates of a continuous normalized field.

The proof addresses this through the following steps. We complete the normalized potential field with the closed unit ball at each zero-gradient block. Lemma E.2 establishes graph consistency of the finite-resolution fields with this completion. Lemma E.3 then represents the feasible noisy updates as projected stochastic approximation to the corresponding differential inclusion. Lemma E.4 shows that the potential Φ\Phi is a Lyapunov function for the projected limiting differential inclusion: its directional derivative is nonpositive for every admissible velocity and vanishes exactly at constrained stationary points of Φ\Phi. Finally, Lemma E.6 identifies this set with the Nash set. These properties allow us to apply the result of Majewski et al. (2018), yielding almost-sure convergence of the actual iterates to the Nash set using one comparison per player and round, and to a single equilibrium when the Nash set is finite.

We will clarify these distinctions and the main proof steps in the main text. Appendix E.3.1 provides the full proof, beginning with an outline.

Comparison noise model. Our model isolates learning from ordering information: repeated comparisons improve confidence in a preference but cannot identify utility gaps. It covers exact comparisons and comparison labels subject to independent corruption, as also considered by Saha et al. (2021). Human judgments can exhibit gap-dependent errors; with a known, calibrated, invertible link, such feedback can additionally reveal numerical gap information. We will clarify the distinction between these information models and the scope of our guarantees.

LLM-routing application and toy experiments. We have added simulations of a synthetic LLM-routing game in Appendix F. LLM routing selects which model should answer each prompt; for example, RouteLLM [Ong et al., ICLR 2025] learns this selection from response-level preference data. Our application introduces strategic interaction: two independently managed applications adapt their routing policies while sharing inference capacity. Changing one application’s routing policy changes congestion and therefore the other application’s preferences, creating a continuous game.

Each application chooses the fractions of its requests to send to each of two LLM services. We use human comparisons from Chatbot Arena to calibrate the response-quality component of the costs, which we combine with modeled operating and congestion costs. A simulated evaluator compares two nearby routing policies for one application while holding the other’s policy fixed, and returns only a noisy preference label. Our CNGP algorithm updates from these unilateral comparisons without observing numerical costs or cost differences.

The costs are constructed to give an ordinal potential game satisfying all assumptions of Theorem 5.2. In the two-dimensional setting, Figure 2 (left) in Appendix F of the revised manuscript shows routing trajectories approaching the unique Nash equilibrium from different initializations, illustrating the theorem’s last-iterate convergence conclusion. Figure 2 (right) shows decreasing mean distance to Nash over 64 runs per noise level, with larger terminal errors as comparisons become less reliable (see also Figure 3). A six-dimensional extension with three traffic classes per application also shows decreasing distance to Nash. Appendix F provides a detailed description of the application and the experimental setting.

[Ong et al., ICLR 2025] Ong, Isaac, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, Mohammed Kadous, and Ion Stoica. RouteLLM: Learning to Route LLMs from Preference Data. ICLR 2025.

Reviewer_4tisOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies learning in continuous games from pairwise action feedback rather than utilities. Instead of feedback from a utility function, learning happens directly from the preference relation between two actions. This feedback gives the sign of the cost difference between the two actions, but not its magnitude. The paper establishes that the classical notions of external regret and the CCEs that no-regret algorithms typically converge to are not identifiable in this setting, since they change under monotone transformations. The authors then develop theory for first order minimization of regret over ordinal feedback and propose an algorithm based on a one-bit comparison estimator that achieves sublinear regret against arbitrary opponents and converges to Nash in ordinal potential games.

Critical strengths

Well-motivated setting. The paper formulates an important problem clearly. Learning strictly from preferences is an important gap in no-regret learning theory, which the authors do a good job motivating (e.g. with RLHF / LLMs) by showcasing a clear gap through the non-identifiability results.

Identifiability results. The identifiability propositions provide strong evidence for the author's main point about the gap in existing work. Theorem 3.1 gives a precise characterization of why classical CCEs are not attainable from ordinal information alone and seems like the strongest result in the paper.

Critical weaknesses

Difficult to follow, but not necessarily the authors fault. I found this paper quite difficult to follow at times, possibly because I am not sufficiently familiar with some of the prior work.

Technical contribution. Beyond the identifiability results, the technical contribution of the paper seems somewhat thin. The learning results largely apply existing tools. For example, Theorem 4.1 seems to follow directly from the projected online gradient descent bound of Zinkevich (2003) with unit norm gradients. That work should also probably be cited if that's the case. The novelty in this work seems more about the framing than the analysis.

Lack of experiments While this is understandably primarily a theoretical contribution, the lack of experiments means there is nothing substantive that connects back to the motivation (e.g. RLHF in LLMs). Paired with the above point, some empirical evidence supporting the method would improve the validation of the proposed method substantially.

Questions for authors

Could the authors provide some experimental results, even on a toy domain, during the response period to address the lack of empirical validation?

4 comments

We thank the reviewer for their valuable feedback, and for recognizing the importance of the setting and the non-identifiability results (Theorem 3.1 in particular which is of independent interest). We appreciate their time in engaging with our work. We highlight our technical contributions regarding the learning results below, and report new toy experiments motivated by an LLM-routing application to illustrate our theoretical contributions.

Technical contributions beyond Theorem 4.1 and the identifiability results

Indeed, the proof of Theorem 4.1 follows similar steps to the standard proof of projected online gradient descent, upon using boundedness of the normalized gradients. We will add the reference to the standard work of Zinkevich (2003) as suggested by the reviewer. Its role is to establish a no-regret guarantee for the ordinal first-order benchmark we propose. The subsequent learning results address the additional difficulties introduced by implementing learning through finite noisy comparisons.

Finite comparisons and regret. Theorem 5.1 establishes sublinear expected finite-resolution ordinal regret against arbitrary opponents using one comparison per player and round. The comparison estimator targets DδD^\delta, and its relationship to the infinitesimal field DD is a substantive technical issue: vanishing comparison radii do not generally make the fields close along moving iterates near stationary blocks. Proposition E.1 demonstrates the consequence for regret: finite-resolution regret can remain bounded while the original regret grows linearly, even for a smooth strongly convex cost and vanishing radii. Thus, the passage from finite comparisons to the infinitesimal benchmark cannot be justified by a routine vanishing-bias argument.

Comparison-based Nash convergence. Theorem 5.2 establishes almost sure last iterate convergence to the Nash set under its stated assumptions despite the finite-resolution difficulty above. We establish graph consistency of the finite-comparison fields with a completed normalized field at stationary blocks (Lemma E.2) and represent the feasible, noisy recursion as projected stochastic approximation (Lemma E.3). We show that the potential Lyapunov inequality holds for every selection of the projected limiting inclusion (Lemma E.4). Under blockwise pseudoconvexity and nondegeneracy, we prove that its zero-dissipation set coincides with the Nash set (Lemma E.6). These steps allow us to apply the stochastic approximation result of Majewski et al. (2018) using differential inclusions, without requiring joint convexity of the potential. Appendix E.3.1 provides the full proof, beginning with a proof outline.

The block structure matters because separate normalization implies that the preference field can be discontinuous at profiles where only some players’ gradients vanish. The theorem also yields a standalone optimization guarantee: taking N=1N=1 and Φ=J\Phi=J gives almost sure convergence of the actual iterates to the global minimizer set of a smooth pseudoconvex objective over a compact convex feasible set, using one noisy comparison per iteration under the stated assumptions.

Question: Could the authors provide some experimental results, even on a toy domain, during the response period to address the lack of empirical validation?

LLM-routing application and toy experiments. We have added simulations of a synthetic LLM-routing game in Appendix F. LLM routing selects which model should answer each prompt; for example, RouteLLM [Ong et al., ICLR 2025] learns this selection from response-level preference data. Our application introduces strategic interaction: two independently managed applications adapt their routing policies while sharing inference capacity. Changing one application’s routing policy changes congestion and therefore the other application’s preferences, creating a continuous game.

Each application chooses the fractions of its requests to send to each of two LLM services. We use human comparisons from Chatbot Arena to calibrate the response-quality component of the costs, which we combine with modeled operating and congestion costs. A simulated evaluator compares two nearby routing policies for one application while holding the other’s policy fixed, and returns only a noisy preference label. Our CNGP algorithm updates from these unilateral comparisons without observing numerical costs or cost differences.

The costs are constructed to give an ordinal potential game satisfying all assumptions of Theorem 5.2. In the two-dimensional setting, Figure 2 (left) in Appendix F of the revised manuscript shows routing trajectories approaching the unique Nash equilibrium from different initializations, illustrating the theorem’s last-iterate convergence conclusion. Figure 2 (right) shows decreasing mean distance to Nash over 64 runs per noise level, with larger terminal errors as comparisons become less reliable (see also Figure 3). A six-dimensional extension with three traffic classes per application also shows decreasing distance to Nash. Appendix F provides a detailed description of the application and the experimental setting.

[Ong et al., ICLR 2025] Ong, Isaac, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, Mohammed Kadous, and Ion Stoica. RouteLLM: Learning to Route LLMs from Preference Data. ICLR 2025.

I thank their authors for their detailed response to my questions and concerns. I find the new experimental results make the paper much more complete and have updated my score as a result.

We thank the reviewer again for their valuable feedback and for engaging with our rebuttal.

Reviewer_nLbqOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies learning in continuous games from ordinal pairwise comparison feedback. It first establishes limitations of standard external regret and coarse correlated equilibrium under this information structure, then introduces ordinal directional regret and ordinal coarse variational equilibrium. It develops learning dynamics and a comparison-based algorithm, providing regret guarantees and, under additional assumptions in ordinal potential games, almost-sure last-iterate convergence to the Nash equilibrium set.

Critical strengths
  1. The paper rigorously establishes the limitations of classical learning objectives when players observe only unilateral preference comparisons. In particular, the characterization of ordinally robust coarse correlated equilibria in Theorem 3.1 is a strong theoretical result.

  2. The formulation of learning algorithms under this feedback model, together with their regret and convergence guarantees, constitutes an important contribution.

Critical weaknesses

The strategic significance of the proposed alternatives remains insufficiently clear. In particular, the paper could better explain what the proposed framework reveals about strategic behavior beyond analyzing a particular cardinal representation consistent with the same unilateral preferences.

Questions for authors

Compared with choosing and analyzing a particular cardinal representation consistent with the same unilateral preferences, what additional strategic insights does the proposed framework provide?

5 comments

We thank the reviewer for their time and valuable feedback.

Compared with choosing and analyzing a particular cardinal representation consistent with the same unilateral preferences, what additional strategic insights does the proposed framework provide?

Beyond a particular cardinal representation. Our framework establishes learning guarantees from unilateral comparisons without requiring players to select or reconstruct a cardinal utility representation. It identifies which strategic conclusions remain valid when the numerical representation changes but the unilateral preferences do not.

Choosing a compatible numerical representation fixes gain and loss magnitudes that the comparisons do not reveal. A fixed deviation that helps against some opponents’ actions and hurts against others may therefore be profitable on average under one representation and unprofitable under another. Consequently, the same distribution can be a CCE under one representation but not another. Theorem 3.1 characterizes exactly which distributions remain CCE under every compatible representation: those assigning probability one to pure Nash equilibria.

Strategic meaning of the ordinal benchmarks. Our ordinal directional regret measures the first-order incentive to move toward a fixed alternative action. A positive term means that a sufficiently small move toward that action is preferred; sublinear regret rules out a positive long-run average of these normalized incentives for any fixed alternative. These incentives are invariant under regular increasing cost transformations. Moreover, at a single action profile, the ordinal equilibrium condition is equivalent to Nash equilibrium under blockwise pseudoconvexity (Proposition 3.3).

Convergence to Nash from comparisons. The comparison-based algorithm establishes what players can achieve from the available feedback: under the assumptions of Theorem 5.2, its actual iterates converge almost surely to the Nash set using only noisy unilateral comparisons. Changing numerical costs while preserving the comparison oracle leaves the algorithm’s behavior and the Nash set unchanged. This gives an equilibrium learning guarantee without selecting or reconstructing numerical utilities.

We will make these interpretations explicit in the revised manuscript.

The authors' response helped clarify the interpretation of ordinal regret as a measure of first-order incentives for improvement that is invariant under regular increasing transformations of the cost functions.

However, my main concern remains. The proposed framework does not seem to resolve the issue that the expected benefits of deviations can differ across ordinally equivalent games. In particular, achieving OCVE does not guarantee that the resulting distribution is a CCE in all compatible games. While OCVE is a natural first-order equilibrium concept, I am still not fully convinced of its additional strategic value compared with conventional equilibrium concepts or approaches based on reconstructing a compatible cardinal representation.

Nevertheless, I consider the rigorous characterization of the limits of what can be guaranteed from ordinal information, as well as the Nash convergence guarantee using only pairwise comparisons under additional assumptions, to be solid theoretical contributions.

Therefore, despite my remaining concern, I maintain my current rating (Weak Accept).

We thank the reviewer for engaging with our rebuttal. We appreciate their feedback. We would like to clarify the following points in response to their follow-up comments.

OCVE and CCE across ordinally equivalent games. Indeed, as noted by the reviewer, an OCVE of a game G\mathcal G is not necessarily a CCE for all games ordinally equivalent to G\mathcal G. Theorem 3.1 shows that a distribution is a CCE for every ordinally equivalent game if and only if it is supported on the set of pure Nash equilibria of the game G\mathcal G. The goal of our contribution is precisely to provide alternative equilibrium concepts and benchmarks when only preference feedback is available to the players. This information does not identify the cardinal benefits of deviations that can differ across ordinally equivalent games.

Strategic interpretation of OCVE:

  • Strategically, an OCVE provides a certificate of average normalized first-order incentives: no fixed alternative offers a positive average normalized directional gain. This criterion is invariant under regular increasing cost transformations. Equation (7) connects this criterion to the players’ ordinal regrets: when every player has sublinear ordinal directional regret, the empirical distribution has asymptotically vanishing ordinal coarse equilibrium violation (see lines 336–337).
  • Moreover, under blockwise pseudoconvexity (Assumption 3.1), we show in Proposition 3.3 and line 330 in Section 3.3 that a deterministic OCVE is a Nash equilibrium: δx is an OCVE⟺Gap⁡D(x)=0⟺x∈NE⁡(G)\delta_x\text{ is an OCVE} \Longleftrightarrow \operatorname{Gap}_D(x) = 0 \Longleftrightarrow x\in\operatorname{NE}(\mathcal G).

Selecting a cardinal representation. Even if a compatible representation is selected, its numerical gain–loss trade-offs across opponents’ profiles remain unidentified by the comparison feedback. Its CCE condition can therefore depend on that additional choice. Our framework instead establishes guarantees for an invariant first-order criterion and, under the additional assumptions of Theorem 5.2, almost sure last iterate convergence to the set of Nash equilibria using only comparisons.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.