- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies entropy-regularized binary games. Every player has two actions, and each player has a mixed strategy encoded by , the probability of the first minus the second action. The interactions are given by a matrix A and vector b. The matrix 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 ('inverse temperature') and (the 'gain'), where is the contribution of the entropy-part in the objective. And 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 the map is a contraction, for the equilibrium is unique and iteration converges, and for 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 and define a function , where 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 in the function . The authors only call 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 and its clipped version , and a single sentence could have conveyed the same meaning. The figures are just not helpful.
Questions for authors
none
2 comments
some of the issues have been resolved in the revised version, I'm changing the score to 3
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),
where p is the probability of action +, ui+,ui− are its expected action payoffs against the others' strategy profile x−i, and
H(p)=−plogp−(1−p)log(1−p),0log0=0.
The coefficient 1/λ>0 rewards randomization. Equivalently, H(p)=log2−DKL((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∗, whose first-order condition is
ui+−ui−+λ−1logpi∗1−pi∗=0.
Solving gives the two-action softmax response
pi∗=eλui++eλui−eλui+,2pi∗−1=tanh!(2λ(ui+−ui−)).
Writing xi=2pi−1, the following paragraph explains how the game determines the matrix and bias: pairwise interactions give ui+−ui−=2(Cx+c)i, hence A=λC, b=λc, and 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); 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=za,
tanh(aP)−χa(aP)=tanh(aP)−P=B(a).
The new example below Figure 1 (p. 5) makes this correspondence concrete: at a=1.5, P≈0.439 and tanh(aP)≈0.577, so the gap is approximately 0.138. An input at least P therefore remains encoded as 1 after any response error up to this gap. The figure illustrates the common mechanism behind the algorithmic and hardness thresholds (Theorem 2.2).