acceptodds
Under review as a conference paper at ICLR 2027

Sharp Accuracy Thresholds for Entropy-Regularized Binary Games

Abstract

Entropy regularization yields smooth, unique best responses, yet equilibrium computation can remain hard. For binary games, we quantify this limitation through an explicit threshold for the largest unilateral improvement in regularized payoff. On every fixed bounded interval of interaction strength, tolerances above the threshold admit polynomial-time algorithms, whereas finding solutions below it is PPAD-complete, with inverse-polynomial margins. Both bounds follow from a scalar identity linking contraction algorithms and hardness reductions. Moreover, hardness persists with fixed regularization, bounded payoffs, and sparse interactions, showing that local smoothness alone does not ensure tractability.

Primary area:
optimization
Keywords:
Entropy-regularized games, logit equilibria, approximate fixed points, PPAD-completeness.

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_T7GxOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies entropy-regularized binary games. Every player i∈{1,…,n}i \in \{1, \dots, n\} has two actions, and each player has a mixed strategy encoded by xi∈[−1,1]x_i \in [-1, 1], the probability of the first minus the second action. The interactions are given by a matrix A and vector b. The matrix AA has a zero diagonal, so that each player's response depends only on the strategies of the others. The objective is to compute an equilibrium of the entropy-regularized game.

Parameters of interest are λ\lambda ('inverse temperature') and κ\kappa (the 'gain'), where λ−1\lambda^{-1} is the contribution of the entropy-part in the objective. And κ\kappa is related to how much variation the matrix introduces, defined as the spectral radius of matrix A under taking element-wise absolute values. At first glance, the promised results seem reasonable and natural. For κ<1\kappa < 1 the map is a contraction, for κ≤1\kappa \leq 1 the equilibrium is unique and iteration converges, and for κ>1\kappa > 1 the authors show matching accuracy thresholds: polynomial-time algorithms above them and PPAD-completeness below them, under margin conditions.

Critical strengths

abstract. I think the results may be interesting in their own right; it seems like a promising algorithmic game theory or (PPAD) complexity paper. This might fit with the theoretical results on AI/learning.

Critical weaknesses

Although such theory results are acceptable for ICLR, I think the paper is not sufficiently self-contained and is clearly targeted at a specialized niche audience. It assumes a well-versed reader, is heavy on notation, uses a lot of short-hand notation in the statements and proofs, and re-uses symbols.

For example, the authors state very briefly in the first paragraph "Adding a positive multiple of entropy to each player's payoff ...", which shows that the players are rewarded by having more uniformly random strategies, in a way. Nowhere in the introduction do the authors explicitly state the entropy penalization, whereas I believe this is required to understand what's going on. The structures AA and bb define a function F(x)=tanh⁡(Ax+b)F(x) = \tanh(A x + b), where tanh⁡\tanh applies pointwise on the resulting vector, and fixed points correspond to equilibria of the entropy-regularized game. The authors add an entropy-regularization term to each player's payoff, and this is what produces the tanh⁡\tanh in the function FF. The authors only call FF the "softmax best response" and do not derive it in the main text, and the regularized objective with the explicit entropy term is only written out in Appendix F.

Further, on a scan of the document: The caption of Figure 1 seems incorrect. The number of subfigures does not match: I expect 3 based on the description, whereas there are only two. The description for the right figure does not match the figure (there is not even a dotted line there). The left figure seems irrelevant to me, it just plots tanh⁡(t)\tanh(t) and its clipped version χa\chi_a, and a single sentence could have conveyed the same meaning. The figures are just not helpful.

Questions for authors

none

2 comments
AuthorsOpenReview ↗

Response to reviewer T7Gx

Thank you for identifying the missing explanation and figure error. All locations refer to the revised manuscript.

1. Background, shorthand, and reused symbols.

We agree that the model should be understandable before the fixed-point notation. The revised introduction now gives the regularized payoff explicitly (Equation (1), p. 1), illustrates it with two users choosing routes, and derives the softmax and tanh response from the first-order condition (Equation (2), p. 1). Equation (5) then explains accuracy as each player's remaining incentive to change strategy. Points 2–3 below give these formulas.

The computational question is whether smooth, uniquely determined individual responses make a joint equilibrium easy to find. We identify matching payoff-error thresholds on fixed bounded gain intervals under the stated margin conditions. The strengthened algorithmic bounds additionally allow arbitrary gain and exponentially small supplied margins; the hardness statement retains its stated restrictions.

For the proof, Section 1.1 explains PPAD, Section 1.3 gives the roadmap, and Section 4 introduces the players before the gate calculations. The main text defines a “latch” as a coupled pair and a “terminal” as the last coordinate of its chain. It uses distinct symbols for circuit nodes and norm weights. The new NOR example works through one gate (p. 9).

2. The introduction does not state the entropy-regularized objective.

We agree that this objective belongs in the introduction. Equation (1) (p. 1) now explicitly states

Vi(p;x−i)=p,ui+(x−i)+(1−p)ui−(x−i)+λ−1H(p),V_i(p;x_{-i})=p\\,u_i^+(x_{-i})+(1-p)u_i^-(x_{-i})+\lambda^{-1}\mathsf H(p),

where pp is the probability of action ++, ui+,ui−u_i^+,u_i^- are its expected action payoffs against the others' strategy profile x−ix_{-i}, and

H(p)=−plog⁡p−(1−p)log⁡(1−p),0log⁡0=0.\mathsf H(p)=-p\log p-(1-p)\log(1-p),\qquad 0\log0=0.

The coefficient 1/λ>01/\lambda > 0 rewards randomization. Equivalently, H(p)=log⁡2−DKL((p,1−p)∣(1/2,1/2))\mathsf H(p)=\log2-D_{\mathrm{KL}}((p,1-p)\\|(1/2,1/2)), so the regularizer penalizes departure from uniform randomization up to an additive constant. The new two-route example (p. 1) illustrates the trade-off: the user favors the less congested route while assigning positive probability to both. The payoff-gap/KL identity is then stated in Equation (5) (p. 2) and proved in Appendix F.2.

3. The softmax response is not derived in the main text.

Equation (2) (p. 1) now derives the response directly from the objective. Strict concavity gives a unique interior maximizer pi∗p_i^*, whose first-order condition is

ui+−ui−+λ−1log⁡1−pi∗pi∗=0.u_i^+-u_i^-+\lambda^{-1}\log\frac{1-p_i^*}{p_i^*}=0.

Solving gives the two-action softmax response

pi∗=eλui+eλui++eλui−,2pi∗−1=tanh⁡!(λ(ui+−ui−)2).p_i^*=\frac{e^{\lambda u_i^+}}{e^{\lambda u_i^+}+e^{\lambda u_i^-}},\qquad 2p_i^*-1=\tanh\\!\left(\frac{\lambda(u_i^+-u_i^-)}2\right).

Writing xi=2pi−1x_i=2p_i-1, the following paragraph explains how the game determines the matrix and bias: pairwise interactions give ui+−ui−=2(Cx+c)iu_i^+-u_i^-=2(Cx+c)_i, hence A=λCA=\lambda C, b=λcb=\lambda c, and F(x)=tanh⁡(Ax+b)F(x)=\tanh(Ax+b). This makes the connection from the game objective to the analyzed fixed-point problem explicit in the main text.

4. Figure 1's caption describes the wrong panels and curves.

The caption was incorrect. We have redrawn Figure 1 and replaced the caption (p. 5). There are exactly two labeled panels: response approximation on the left and sign preservation on the right. Both mark the same threshold B(a)\mathfrak B(a); the caption now describes the curves and markers actually displayed.

5. The left panel adds little beyond plotting two functions.

We have given the panels a shared proof interpretation. The left marks the extremal approximation error; the right shows that the same quantity is the largest error compatible with preserving a Boolean encoding. At P=zaP=z_a,

tanh⁡(aP)−χa(aP)=tanh⁡(aP)−P=B(a).\tanh(aP)-\chi_a(aP)=\tanh(aP)-P=\mathfrak B(a).

The new example below Figure 1 (p. 5) makes this correspondence concrete: at a=1.5a=1.5, P≈0.439P\approx0.439 and tanh⁡(aP)≈0.577\tanh(aP)\approx0.577, so the gap is approximately 0.1380.138. An input at least PP therefore remains encoded as 11 after any response error up to this gap. The figure illustrates the common mechanism behind the algorithmic and hardness thresholds (Theorem 2.2).

some of the issues have been resolved in the revised version, I'm changing the score to 3

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

The paper studies entropy-regularized games with two actions per player and pairwise interactions. It investigates the tradeoff between interaction strength and the accuracy with which an approximate equilibrium can be computed. Theorem 1.1 gives polynomial-time algorithms when the allowed error is above certain thresholds, while Theorem 1.2 gives PPAD-hardness results below them. These guarantees require inverse-polynomial separation from the thresholds. For the maximum regularized payoff gain, the bounds match on fixed bounded ranges of interaction strength. The residual hardness result has an additional restriction on the error tolerance.

The hardness persists even with a fixed entropy coefficient, bounded payoffs, and a constant number of neighbors per player. This shows that smooth, unique individual best responses can coexist with computationally difficult equilibrium problems.

Critical strengths

S1. The paper studies entropy-regularized games, an interesting model in game theory.

S2. It gives both efficient algorithms and matching hardness results for the regularized payoff gap within the stated parameter ranges.

S3. The hardness holds even with fixed regularization, bounded payoffs, and only a constant number of neighbors per player.

Critical weaknesses

W1. I found the presentation hard to follow, especially the model and the reduction. Introducing the regularized payoff explicitly and explaining the role of the entropy term would help, along with a short explanation of the main results in plain language. In Section 4, a clearer overview of the players, their interactions, and the main parameters before the technical details would make the reduction easier to follow. A worked example of one gadget would also help.

W2. Some regimes remain open, including the gap between the residual bounds at larger interaction strengths. The matching results for the regularized payoff gap also assume bounded interaction strength and inverse-polynomial separation from the thresholds. These limitations are acknowledged in Table 1 and the conclusion. I view them as modest limitations of scope and natural directions for future work.

Questions for authors

Q1. The paper identifies the unresolved regimes in Table 1 and the conclusion. Could you briefly explain how significant these limitations are for the model? In particular, does the gap in the residual bounds at larger interaction strengths leave an important regime unresolved?

Q2. Could you expand on the motivation for adding entropy to players’ payoffs? In particular, how should we interpret this term, and what is a simple setting where this model is useful? A brief motivating example would help.

1 comment
AuthorsOpenReview ↗

Response to reviewer CcCZ

We appreciate the suggestions on exposition and scope. All locations refer to the revised manuscript.

W1. Make the model and reduction easier to follow.

We expanded the model presentation to connect the regularized payoff, its derived softmax response, and the payoff interpretation of KL accuracy (Equations (1), (2), and (5), pp. 1–2). A routing example explains the entropy term (Q2 below). Section 1.1 explains the results before their formal statements. Section 4 (p. 7) introduces the players, coupled pairs, chains, and construction parameters before the gate proofs. Longer chains preserve encoded values while reducing feedback's weighted contribution, allowing the construction to stay within its prescribed gain budget.

The new worked NOR example (Section 4.3, p. 9) treats gain near one. Here r1,r2r_1,r_2 are the last input-chain coordinates, P>0P > 0 is the encoding threshold, and h>0h > 0 exceeds the forcing threshold for the permitted loss. These coordinates lie in [−Q,Q][-Q,Q] with Q=5P/2Q=5P/2. Equation (23) gives the output pair's external field:

HNOR/h=−8(r1/P+r2/P)−14.H_{\rm NOR}/h=-8(r_1/P+r_2/P)-14.

Two inputs encoding 00 satisfy r1,r2≤−Pr_1,r_2≤-P, hence HNOR≥2hH_{\rm NOR}≥2h, forcing output 11. If one input encodes 11, say r1≥Pr_1≥P, the largest possible field occurs at r1=P,r2=−5P/2r_1=P,r_2=-5P/2 and equals −2h-2h, forcing output 00 even when the other input is unspecified. The forcing lemma fixes the output pair's sign, and the chain preserves it.

W2. Open cases and the assumptions for the bounds.

The revision removes both algorithmic restrictions: Theorem 1.1 (p. 2) accepts every positive rational margin δδ with running time polynomial in the input bit length and log⁡(2+1/δ)\log(2+1/δ), and the KL upper bound now holds at arbitrary gain. Appendix B (pp. 19–20) proves this without a numerical gain factor; Proposition B.8 (p. 21) extends automatic margin search as well. The upper bound also covers entropy coefficients decreasing as the instance grows, with accuracy still subject to the KL threshold.

The fixed gain cap K0K_0 and inverse-polynomial separation remain conditions on hardness. Residual hardness additionally uses a fixed tolerance cap gˉ<2/3\bar g < 2/3 (Table 1, p. 3).

A fixed gain cap is natural in the normalized model highlighted by the paper. If total pure payoffs lie in [−1,1][-1,1], the affine payoff difference 2(Cx+c)2(Cx+c) satisfies

∣ci∣+∑j∣Cij∣≤1,κ=λρ(∣C∣)≤λ.|c_i|+\sum_j|C_{ij}|≤1,\qquad κ=λρ(|C|)≤λ.

Thus fixed entropy coefficient 1/λ1/λ already bounds gain independently of player count. Classification below the threshold at growing gain, equality at a positive KL threshold, and hardness at finer separation margins remain open. Equality at a positive residual threshold cannot occur for rational inputs (Theorem A.4, p. 16).

Q1. How significant are the open cases, especially the residual gap?

For the main payoff criterion, thresholds match on every fixed bounded gain interval under the stated margin conditions, including intervals above Kaff≈6.27099K_{\mathrm{aff}}≈6.27099. The strengthened KL upper bound additionally holds at arbitrary gain. The exact identity

max⁡iGap⁡i(x)=λ−1Ld(x;F)\max_i\operatorname{Gap}_i(x)=λ^{-1}{\cal L}_d(x;F)

means that KL tolerance gg bounds every player's available improvement in regularized payoff by g/λg/λ. The residual gap therefore does not create a corresponding gap in this payoff classification.

The residual question nevertheless leaves a meaningful regime of coarse strategy approximation unresolved: 2/3≤g<B(K)2/3≤g < \mathfrak B(K) when K>KaffK > K_{\mathrm{aff}}. Since xi=2pi−1x_i=2p_i-1, these correspond to tolerances of at least 1/31/3 for error in action probabilities relative to best responses. Residual hardness is uniform only under each fixed cap gˉ<2/3\bar g < 2/3 and does not classify this interval. On every fixed gain range 1<K≤K0<Kaff1 < K≤K_0 < K_{\mathrm{aff}}, residual thresholds match under the stated margin conditions. See Section 1.1 and Table 1 (p. 3).

Q2. Why add entropy, and when is the model useful?

Entropy models a preference for randomized decisions alongside high expected payoff. Since H(p)=log⁡2−DKL((p,1−p)∣(1/2,1/2)){\sf H}(p)=\log2-D_{\mathrm{KL}}((p,1-p)\\|(1/2,1/2)), adding entropy is equivalent, up to a constant, to penalizing departure from uniform randomization. Its coefficient controls this trade-off and makes each best response unique and smooth.

The new routing example (p. 1) illustrates this interpretation. Two users choose between two routes, paying 11 if they choose the same route and 00 otherwise. If the other user chooses Route 1 with probability 0.750.75, entropy coefficient 1/21/2 gives

p∗=11+e≈0.269.p^*=\frac1{1+e}≈0.269.

The user favors the less congested route while retaining randomization; the response varies smoothly with the other user's choice probability.

The example also connects to our computational question: its gain is κ=λ/2κ=λ/2, where 1/λ1/λ is the entropy coefficient (p. 1). Stronger regularization lowers gain. Our results quantify the payoff accuracy achievable when interactions exceed the uniform uniqueness regime.

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

This work studies the computational complexity of entropy regularized binary games. In a binary game each player has a [-1, +1] value corresponding to the difference of the probabilities assigned to their two actions. With entropy regularization the goal of finding an equilibrium becomes to find an x in [-1, +1]^n such that x = tanh(A x + b) where A, b are a given payoff matrix and vector respectively. The authors study finding x that approximates the optimal in the sense that || x - F(x) ||_\infty should be small or that the KL divergence between the induced binary distributions of each coordinate x_i is close to the corresponding distribution of the i-th coordinate of tanh(Ax + b).

They identify \kappa = \rho(|A|) (the spectral radius of coordinatewise absolute value |A|) as the critical quantity that controls when the problem admits polynomial time algorithms and when it is PPAD-complete. They show that when target ell-infinity approximation error is >= B(\kappa) + \delta (B(\codt) is a simple 1-d function defined in the paper) then a polynomial time algorithm exists and (roughly) when g <= B(\kappa) - \Delta. They show a similar result for KL divergence approximation of the optimal solution.

Critical strengths
  1. Clear contribution and result: I think this paper presents good progress to the problem of finding equilibria for entropy regularized games.

  2. Well motivated problem: I think that the problem studied here is interesting and connects with a lot of existing work in the field. The fact that a nice and sharp characterization of hardness is possible in this setting is interesting.

  3. The algorirthm proposed for the upper bound is relatively simple and elegant: they show that a fixed point iteration with a slightly smoother proxy than the tanh(\cdot) (they use a ramp-like aproximation) works.

Critical weaknesses
  1. Is it possible to improve the dependence on \delta to \log(1/\delta)? For polynomial time in the size of the input we need the runtime to be poly in \log(1/\delta).
Questions for authors

See weaknesses.

2 comments
AuthorsOpenReview ↗

Response to reviewer EBPk

Thank you for suggesting this improvement.

1. Can the dependence be improved to log⁡(1/δ)\log(1/\delta)?

Yes. We have replaced the iteration-based solver by a finite-precision ellipsoid solver and proved the requested logarithmic dependence in Theorem 1.1 (p. 2): both losses now have running time polynomial in the input bit length and log⁡(2+1/δ)\log(2+1/\delta), at arbitrary gain. For example, a supplied margin δ=2−p\delta=2^{-p} contributes polynomial dependence on pp, rather than 2p2^p.

The scalar surrogate and accuracy thresholds are unchanged. The new ingredients are a weighted Euclidean norm and residual cuts that need only nonexpansiveness; they avoid the inverse contraction-gap factor. Lemma B.4 and Proposition B.5 (p. 19) include evaluation precision and arithmetic costs. The derivation is below. The hardness results retain their original inverse-polynomial separation assumption.

For M=∣A∣M=|A| and rational q>ρ(M)q > \rho(M), compute positive rational weights satisfying

Mv≤qv,MTvL≤qvL,D2=diag⁡(viL/vi).Mv\le qv,\qquad M^{\mathsf T}v^{\rm L}\le qv^{\rm L},\qquad D_2=\operatorname{diag}(v_i^{\rm L}/v_i).

Normalize D2D_2 to have minimum diagonal entry one. For S(x)=χα(Ax+b)S(x)=\chi_\alpha(Ax+b) with α>max⁡1,q\alpha > \max\\{1,q\\}, weighted Cauchy–Schwarz gives nonexpansiveness in this norm (Lemma B.4, p. 19). Extend SS by T(y)=S(Πy)T(y)=S(\Pi y), where Π\Pi projects onto the strategy cube. For a fixed point x∗x^* and RT(y)=y−T(y)R_T(y)=y-T(y),

⟨D2RT(y),y−x∗⟩≥12∣RT(y)∣D22.\langle D_2R_T(y),y-x^*\rangle\ge\tfrac12\\|R_T(y)\\|_{D_2}^2.

These ellipsoid cuts require only nonexpansiveness and avoid the inverse contraction-gap factor. Proposition B.5 (p. 19) proves logarithmic dependence on the target residual, including evaluation and arithmetic costs.

The KL threshold G\mathfrak G is globally 1/41/4-Lipschitz, controlling bias uniformly in gain. Use e=δ0/2e=\delta_0/2 for residuals or e=δ0/[8(1+R)]e=\delta_0/[8(1+R)] for KL, where δ0=min⁡δ,1\delta_0=\min\\{\delta,1\\} and RR bounds absolute fields. Weights have polynomial encoding length, and the field bound enters the required precision through log⁡(1+R)\log(1+R) (Section 3.2, p. 7, and Appendix B.4, p. 20).

Proposition B.8 (p. 21) also finds a margin at arbitrary gain.

Thank you for your answer. I will be maintaining my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers

We thank the reviewers. New and revised material is marked in blue. Page references are to the revised manuscript.

1. Algorithmic precision. Theorem 1.1 (p. 2) now gives running time polynomial in the input bit length and log⁡(2+1/δ)\log(2+1/\delta) for both losses. The KL upper bound now holds at arbitrary gain. Section 3.2 and Algorithm 1 (pp. 6–7) present the finite-precision ellipsoid solver. Lemma B.4 and Proposition B.5 (p. 19) give the weighted norm and the bit-complexity proof. Proposition B.8 (p. 21) extends the KL margin search to arbitrary gain.

2. Model and interpretation. The introduction now states the regularized payoff, derives the softmax and tanh formulas from the first-order condition, and illustrates the role of entropy with a two-user routing example (Equations (1)–(2), p. 1). Section 1.1 adds a plain-language summary (p. 2). Table 1 records the stronger upper bounds, and the text below it explains how a residual tolerance of 2/32/3 translates to an error allowance of 1/31/3 in an action probability (p. 3).

3. Figure 1. We redrew the two panels and corrected the caption (p. 5). The example below the figure uses a=1.5a=1.5 to show how the approximation error marked on the left gives the sign-preservation tolerance on the right.

4. Reduction and notation. Section 4 now opens with an overview of the players and construction parameters (p. 7). Section 4.3 works through a NOR gate with Q=5P/2Q=5P/2 (p. 9). The main text now uses distinct symbols for circuit nodes and norm weights. Appendix F.2 clarifies the notation for action distributions, and Appendix G distinguishes the interpolation mesh from the output grid.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.