The Computable but Not Learnable Information-Value-Free Equilibria and Regulation of Algorithmic Collusion

Chang Wang; Chenhao Zhang; Jason D. Hartline

REVIEW 3 major objections 5 minor 5 references

The Computable but Not Learnable Information-Value-Free Equilibria and Regulation of Algorithmic Collusion

T0 review · 3 major / 5 minor · reviewed 2026-07-30 · grok-4.5

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Rationalizable learning cannot reach equilibria that generate no valuable information, even though those equilibria are easy to compute offline.

desk verdict Solid offline/online separation for a new CE refinement, but the antitrust punchline overreaches the existential lower bound. read the letter →

arxiv 2607.27128 v1 pith:EKATFBGD submitted 2026-07-29 cs.GT

Jason D. Hartline , Chang Wang , Chenhao Zhang This is my paper · ORCID

classification cs.GT

keywords information-value-freeequilibriumalgorithmiccollusionno-swap-regretlearningsmoothlearnerscorrelatedvaluableinformationantitrustregulationonlineingames

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces information-value-free equilibria: correlated equilibria in which no player is strictly better off than by playing some fixed action, so the correlation carries no valuable private information. These equilibria always exist and can be found offline by a simple linear program. Yet the paper proves they cannot be learned online. When one player uses any no-swap-regret algorithm and the other uses any smooth learner (algorithms that gradually abandon a slightly worse action), the empirical history of play stays a fixed positive distance from every information-value-free equilibrium. The same barrier rules out time-average convergence to Nash. The authors read the result as showing that rationalizable learning must generate valuable information, so antitrust rules that try to ban all implicit information exchange among pricing algorithms are incompatible with competitive learning itself.

What carries the argument

The smooth-learner property (Definition 3.1): when two arms differ by a vanishingly small payoff gap, the algorithm still shifts probability mass only gradually, admitting a long decreasing weight subsequence whose first-half versus second-half gap is linear in T. This property is used to construct stage games in which any no-swap-regret column player is forced into persistently valuable correlation.

What would settle it

Exhibit a smooth no-swap-regret algorithm pair whose empirical play on the paper's constructed family of games approaches an information-value-free equilibrium (distance tending to zero), or show that a standard pricing algorithm fails the smooth-learner definition yet still satisfies no swap regret.

Watch

Extended reading notes

Core claim

Although an information-value-free equilibrium can be computed in polynomial time from the normal-form game, no pair consisting of a no-swap-regret learner and a smooth learner can make the empirical distribution of play converge to one: the distance remains bounded below by a positive constant that depends only on the smoothness of the opponent.

Load-bearing premise

The impossibility holds only when the opponent is a smooth learner that cannot abruptly abandon a slightly worse action; algorithms that jump discontinuously fall outside the result.

Editorial extensions

If this is right

Rationalizable learning of correlated equilibria necessarily generates valuable information.
Blanket bans on implicit information exchange among pricing algorithms are incompatible with competitive learning.
Time-average convergence to Nash is informationally impossible for the same broad class of smooth learners.
Offline tractability of an equilibrium concept need not imply online learnability under uncoupled dynamics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Regulators seeking competitive prices may need outcome- or audit-based tests rather than communication bans, because any algorithm that fully exploits its own payoff history will create usable correlation.
The same smooth-learner barrier may obstruct other refinements that simultaneously demand no swap regret and non-negative external regret.
If practical pricing algorithms turn out to be non-smooth, the informational lower bound leaves open the possibility that they could still learn information-value-free play.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The real contribution is clean: they define IVFE (CE plus non-negative external regret), show it is poly-time via finitely many LPs, and prove that no-swap-regret vs any smooth learner stays a constant distance from every IVFE on a constructed sequence of games. That offline/online gap is new relative to the Foster–Vohra / Hart–Mas-Colell canon and the usual Nash hardness story. The appendices check out—Prop 3.2’s closed forms for MWU/FTPL/OGA and the Blum–Mansour lifts are careful, and the B.1/B.2 contradiction arithmetic is tight.

What the paper does well is make the information-economics reading precise (Table 1, Lemma 2.11) and keep the math self-contained. The smoothness definition is a legitimate scope condition; it honestly excludes guess-and-verify dynamics that can hit Nash.

The soft spot is not a proof gap. Theorem 3.3 is existential and diagonal: for every L and smooth A there exist games G_T (payoffs calibrated to A’s own weight sequence) on which liminf d ≥ c. That is fine as a worst-case lower bound. The abstract and §4.1 then upgrade it to “valuable information exchange is unavoidable under rationalizable learning” and therefore that bans on implicit communication are incompatible with learning. Inside the paper’s own citations that upgrade fails: the same smooth learners (MWU, OGA, etc.) are already known to converge to Nash ⊂ IVFE in first-price auctions and Bertrand competition—the exact markets the collusion debate cares about. So the hard family is disjoint from the motivating applications. The authors half-acknowledge this; they still write the policy sentence as if it were theorem-strength. That is the part that needs tightening before anyone treats the regulatory claim as settled.

For theory people who care about regret refinements and learnability separations this is worth reading. For the antitrust audience the math is solid but the leap is not. I would send it to referees; they will force the quantifiers and the policy language into alignment. Engage the theory result; quote the policy claim only with the existential caveat attached.

Referee Report

3 major / 5 minor

Summary. The paper introduces information-value-free equilibrium (IVFE): a correlated equilibrium in which each player's equilibrium payoff is no higher than what some fixed action would yield against the opponents' equilibrium play (Definition 2.1). The authors show NE ⊊ IVFE ⊊ CE (Proposition 2.2) and that an IVFE always exists and is computable in polynomial time via finitely many LPs (Theorem 2.3). The main result (Theorem 3.3) is a lower bound: for any no-swap-regret learner L facing any "smooth learner" A (Definition 3.1, a gradual-response condition on two-arm experiments), there exists a sequence of games {G_T} such that empirical play stays a constant distance from every IVFE. Proposition 3.2 certifies MWU, FTPL, OGA, and their Blum–Mansour reductions as smooth learners, with closed-form weight-sum computations. Corollaries derive unilateral non-learnability against adversaries (3.4) and an informational obstruction to time-average Nash convergence (3.5). The authors interpret the lower bound information-economically (rationalizable learning generates valuable information) and draw policy conclusions for algorithmic-collusion regulation.

Significance. If the results hold — and on my reading the technical core is sound — the paper makes two genuine contributions. First, the offline/online separation is novel: to my knowledge IVFE is the first natural equilibrium concept that is poly-time computable from the normal form yet provably not learnable by a broad, explicitly verified class of uncoupled dynamics. This inverts the usual pattern (CE: easy both ways; Nash: hard both ways) and is of independent interest to learning-in-games. Second, the proof is fully constructive and checkable: the lower-bound game family is explicit (Table 2 with parameters w̄, β = A/8T), the smoothness verifications in §B.1 are closed-form, and the contradiction arithmetic in §B.2–B.7 is elementary and transparent. The paper is also unusually honest about its own scope: it states that guess-and-verify dynamics escape the result, flags the worst-case nature of the construction in §4.1, and lists the right open questions in §4.2. The policy connection to algorithmic-collusion regulation is timely, though, as detailed below, the strength of the stated policy conclusion currently exceeds what the theorem supports.

major comments (3)

[Abstract, §1, §4.1 vs. Theorem 3.3] The headline claim — 'valuable and implicit information exchange is unavoidable under rationalizable learning, and traditional antitrust regulation against such exchange is therefore incompatible with rationalizable learning' (abstract; repeated in §1.1 and §4.1) — is a near-universal statement, but Theorem 3.3 is existential over opponent-calibrated game sequences: for each (L, A) the construction in §B.2 builds G_{2T} from statistics of A's own weight sequence (w̄, β = A/8T) in the two-arm experiment with ε = ε(2T), and each horizon gets a different game. This is a legitimate worst-case/diagonal lower bound, but it does not show that valuable information arises in any particular game of economic interest. Worse for the policy framing, there is countervailing evidence inside the paper's own frame: Proposition 3.2 certifies MWU, FTPL, and OGA as smooth, and the works the paper itself cit
[Definition 3.1 and §B.2] The entire impossibility rests on Definition 3.1, a bespoke condition (existence of a weakly decreasing weight subsequence of length T(1−h(T)) with an Ω(T) first-half/second-half mass gap in the two-arm experiment). The paper verifies it for three algorithms and their Blum–Mansour reductions, which is commendable, but two clarifications are needed for the result to be properly assessed. (a) Is the weakly-decreasing-subsequence requirement essential to the proof or an artifact of it? Several standard algorithms may satisfy the mass-gap property without admitting such a subsequence (e.g., algorithms with oscillatory but drifting weights); a sentence on what fails in §B.2 without monotonicity would help. (b) The class excludes exactly the dynamics known to reach Nash (Foster–Young, Hart–Mas-Colell, Germano–Lugosi), and the exclusion is doing real work: the theorem should be read as 'no smoo
[§B.2, Theorem 3.3 statement] The game family {G_T} varies with the horizon T and depends on the opponent algorithm A's realized behavior. Two consequences deserve explicit discussion. First, the result does not rule out convergence to IVFE in any fixed stage game; Corollary 3.4 gives a fixed game only for the unilateral/adversarial case. Whether a fixed-game version of Theorem 3.3 holds for smooth opponents is a natural strengthening (or refutation) target and should be stated as an open question, since a time-varying, opponent-tailored game family is a weaker notion of 'inherent' than the introduction suggests. Second, the construction requires knowing A's weight statistics (w̄, A, β); the lower bound is therefore a diagonalization against a known opponent, not against an unknown smooth learner. This is standard for such results but should be said plainly where the theorem is stated, since it bears on how the 'inco

minor comments (5)

[§B.2 and §B.1] Notation collisions impede checking: A denotes both the opponent algorithm (Theorem 3.3 statement) and the quantity Σ_{t: w_t > w̄}(w_t − w̄) in §B.2; η denotes both the MWU/FTPL learning rate in §B.1 and the distance threshold η = β² in §B.2; h(T) is used for the 2T-round run with a parenthetical acknowledging the ambiguity. Please rename at least the §B.2 instances.
[Definition 2.1, Theorem 2.3] The IVFE definition and the computation result are stated for two-player games only, while the abstract and introduction speak of 'games' generally. Either state the two-player restriction up front or note that the LP-enumeration argument extends to n players with running time polynomial in the normal-form representation.
[§B.2, Analysis paragraph] The reduction 'assume d < η, then there exist infinitely many horizons with negative-BIH magnitude < 2ηT + O(TR(T)); take such a subsequence and re-index' is compressed. A sentence explaining why the liminf hypothesis yields this subsequence (and why re-indexing preserves the smoothness invocation with ε = ε(2T)) would make the contradiction argument self-contained.
[§3, proof sketch] The simplified adversarial-Nature sketch is helpful, but the mapping from its three claims to the actual Lemmas B.1–B.6 (which replace Nature's state switch with the smooth learner's weight drift) should be made explicit in one or two sentences; currently the reader must infer that the counterfactual row player of Claim B.5 plays the role of Nature continuing in state 1.
[References / §1.2] The discussion of Blum et al. (2018) and Camara et al. (2020) would benefit from one sentence stating precisely what breaks in those settings if IVFE-style guarantees are demanded (the current text says the approach 'would not be successful' without specifying whether this is a corollary of Theorem 3.3 or of Corollary 3.4).

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: IVFE, distance, and the smooth-learner lower bound are independently defined; the proof is a standard diagonal construction, not a fit or self-citation loop.

full rationale

The paper is a self-contained definition–theorem–proof theory paper. IVFE (Def. 2.1) is a static refinement of CE (NE ⊊ IVFE ⊊ CE, Prop. 2.2) defined by payoff inequalities, not by learning dynamics. Offline poly-time existence (Thm. 2.3) is a finite family of LPs. The learning side equates convergence of empirical play to IVFE with no swap regret plus non-negative best-in-hindsight regret (Defs. 2.4–2.6, Prop. 2.9, Lemma 2.11) by the usual regret-to-equilibrium accounting; none of these objects is defined in terms of the impossibility conclusion. Smooth learners (Def. 3.1) are an external regularity class; Prop. 3.2 verifies MWU/FTPL/OGA and their Blum–Mansour reductions by direct closed-form or integral bounds. Theorem 3.3 is an existential worst-case statement: for every no-swap-regret L and every smooth A there exist games {G_T} (payoffs built from A’s own two-arm weight statistics w̄, A, β) such that liminf d_{G_T}(τ_T) ≥ c. Calibrating the hard instance to A is ordinary diagonalization, not fitting a parameter and re-predicting it, and the B.1/B.2 contradiction does not assume the conclusion. Self-citations (Hartline et al. 2024/2025) appear only in the collusion-policy discussion (§1.1, §4.1), not as lemmas inside the impossibility. Scope tension between the existential theorem and the abstract’s regulatory rhetoric is a separate correctness/overclaim issue, not circularity. Score 0; steps empty.

Assumptions & free parameters 0 free parameters · 5 assumptions · 2 invented entities

The central impossibility rests on standard regret-to-equilibrium equivalences, the paper's own smooth-learner axiom that excludes discontinuous dynamics, full-feedback uncoupled observation, and the definitional package of IVFE. No empirical free parameters. The invented objects are the IVFE concept and the smooth-learner predicate; both are mathematical definitions with internal consistency checks (NE ⊂ IVFE ⊂ CE; MWU/FTPL/OGA satisfy smoothness) but no external empirical handle.

assumptions (5)

standard math No-swap-regret empirical play converges to correlated equilibrium; no external regret converges to coarse correlated equilibrium (Foster–Vohra; Hart–Mas-Colell).
Used throughout §2.2 and Proposition 2.9 to equate learning guarantees with equilibrium notions.
domain assumption Players observe full own-payoff feedback each round and do not observe opponents' actions directly (uncoupled full-feedback model).
Setup in §2.2; standard in the no-regret learning-in-games literature the paper builds on.
ad hoc to paper Definition 3.1: a smooth learner facing arms 0 and ε admits a long weakly decreasing weight subsequence whose first-half/second-half gap is Ω(T) for small enough ε(T).
Load-bearing restriction that makes the adversarial Nature simulation work and excludes guess-and-verify Nash learners; introduced in §3.
domain assumption Reward vectors may be treated as expectations of opponent mixed strategies (concentration omitted).
Footnote in §2.2; classical and stated as w.l.o.g. via concentration.
standard math Nash equilibria exist for finite normal-form games (Nash 1950), hence IVFEs exist.
Invoked in Theorem 2.3 existence argument.

invented entities (2)

Information-value-free equilibrium (IVFE)
purpose: Refine CE by requiring each player has a fixed action matching equilibrium payoff; target of the computable-but-not-learnable separation.
Definition 2.1; equivalent to CE plus non-negative best-in-hindsight regret in the empirical distribution. Independent mathematical object, but motivated by the paper's information-economics narrative.
Smooth learner (Definition 3.1)
purpose: Capture gradual abandonment of slightly worse arms so the lower-bound opponent can simulate slow state switches.
New predicate; verified for MWU, FTPL, OGA and Blum–Mansour reductions, but defined to fit the proof rather than taken from prior literature.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The Computable but Not Learnable Information-Value-Free Equilibria and Regulation of Algorithmic Collusion." pith.science (2026). https://pith.science/paper/EKATFBGD

@misc{pith2026260727128,
  author       = {Pith},
  title        = {Pith review of: The Computable but Not Learnable Information-Value-Free Equilibria and Regulation of Algorithmic Collusion},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EKATFBGD}},
  note         = {Machine review of arXiv:2607.27128}
}

read the original abstract

A correlated equilibrium is information-value-free if every player has an action that yields the same payoff as their equilibrium strategy when all other players follow their respective equilibrium strategies. An equilibrium is learnable if the empirical history of play generated by certain learning algorithms using only full feedback on each player's own payoff converges to it. Our main result is that although an information-value-free equilibrium can be computed efficiently offline, it is not learnable by a broad class of learning algorithms. This separation stands in sharp contrast to canonical equilibrium concepts, where offline computation and online learning typically have comparable difficulty. In information-economics terms, our results imply that learning correlated equilibria in games cannot avoid generating valuable information, which has implications for current debates on the regulation of algorithmic collusion: Valuable and implicit information exchange is unavoidable under rationalizable learning, and traditional antitrust regulation against such exchange is therefore incompatible with rationalizable learning. Our results also imply an informational impossibility result for time-average convergence to a Nash equilibrium by a broad class of learning algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

5 extracted references · 1 linked inside Pith

[1]

Multiplicative Weights Update,
[2]

In16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Algorithmic Collusion Without Threats. In16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 1–21. 5 John Asker, Chaim Fershtman, and Ariel Pakes. 2022. Artificial intelligence, algorithm design, and pricing. InAEA Papers and Proceedings, Vol. 112. American Economic Association 2014 B...

arXiv 2025
[3]

τX t=1 1[a t =L]G (t) L +1[a t =M]G (t) M # ≥ 3 4 A−o(T) = Ω(T). Lemma B.2.We have E

Online Gradient Ascent (also known as Projected Gradient Ascent (Zinkevich, 2003)). The corresponding Blum–Mansour reductions (Blum and Mansour, 2007) of these algorithms are also smooth learners. Multiplicative W eights UpdateAssume without loss of generality thatw 1 = 1 2 . Given any MWU algorithm with a learning rateηsuch thatη=o(1) andηT→ ∞, letε= 2/η...

2003
[4]

Follow-the-Perturbed-Leader,
[2025]

3, 6, 13 Mete S ¸eref Ahunbay and Martin Bichler

Referred to the Committee on the Judiciary. 3, 6, 13 Mete S ¸eref Ahunbay and Martin Bichler. 2025. Semicoarse Correlated Equilibria and LP-Based Guarantees for Gradient Dynamics in Normal-Form Games. InProceedings of the 26th ACM Conference on Economics and Computation. 91–91. 5, 11, 25 Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron ...

2025

Pith tools

Reviewed July 30, 2026 · model on record in the stance chip above.

[1] [1]

Multiplicative Weights Update,

[2] [2]

In16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Algorithmic Collusion Without Threats. In16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik, 1–21. 5 John Asker, Chaim Fershtman, and Ariel Pakes. 2022. Artificial intelligence, algorithm design, and pricing. InAEA Papers and Proceedings, Vol. 112. American Economic Association 2014 B...

arXiv 2025

[3] [3]

τX t=1 1[a t =L]G (t) L +1[a t =M]G (t) M # ≥ 3 4 A−o(T) = Ω(T). Lemma B.2.We have E

Online Gradient Ascent (also known as Projected Gradient Ascent (Zinkevich, 2003)). The corresponding Blum–Mansour reductions (Blum and Mansour, 2007) of these algorithms are also smooth learners. Multiplicative W eights UpdateAssume without loss of generality thatw 1 = 1 2 . Given any MWU algorithm with a learning rateηsuch thatη=o(1) andηT→ ∞, letε= 2/η...

2003

[4] [4]

Follow-the-Perturbed-Leader,

[5] [2025]

3, 6, 13 Mete S ¸eref Ahunbay and Martin Bichler

Referred to the Committee on the Judiciary. 3, 6, 13 Mete S ¸eref Ahunbay and Martin Bichler. 2025. Semicoarse Correlated Equilibria and LP-Based Guarantees for Gradient Dynamics in Normal-Form Games. InProceedings of the 26th ACM Conference on Economics and Computation. 91–91. 5, 11, 25 Eshwar Ram Arunachaleswaran, Natalie Collina, Sampath Kannan, Aaron ...

2025