| paper | d4-conf-wine-2019-0016 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Exact maximization is solvable in time polynomial in \(m,\tau,d,k,L\), with unrestricted \(d\). An optimal obedient assignment uses at most \(k\) active messages and at most \(k\tau\) nonzero entries. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3
Given a rational distribution \(\mu_A\) over episode types \(a\), where each type specifies its conditional law of \((B,E)\), and a \(k\)-piecewise-linear convex score function \(G\), choose message-assignment masses \(x_{a,s}\geq 0\) satisfying \(\sum_s x_{a,s}=\mu_A(a)\). Use recommendation messages \(s=(i_0,(i_b)_{b\in\mathcal B})\), with each recommendation obedient for the posterior induced by positive mass on \(s\), both before and after each Bob signal \(b\). Compute a feasible assignment maximizing the per-episode sender objective \(J(x)=\sum_s[q_sG(p_s)-\sum_b q_{s,b}G(p_{s,b})]\), where \(q_s=\sum_a x_{a,s}\), \(q_{s,b}=\sum_a x_{a,s}\Pr(b\mid a)\), and \(p_s,p_{s,b}\) are the corresponding event posteriors. Theorem 3 gives a polynomial-time algorithm in \(k^{|\mathcal B|},|\mathcal A|,|\mathcal E|\).
A continuum of independent market episodes with a shared disclosure policy. The society is a distribution over complete episode types \(a\), each carrying mass \(\mu_A(a)\); the decision variables \(x_{a,s}\) allocate that mass to messages, and the objective is the paper’s expected sender payoff per episode.
For independent episodes with no shared constraints, the mass variables and objective are exactly the original randomized signaling scheme, so the population interpretation adds no new optimization structure.
fatal: False
The mirror covers Theorem 3’s exact commitment computation and the approximate commitment regimes of Theorems 4 and 5. It does not cover the approximate-PBE result connecting commitment to the uncommitted market or establish hardness.
The strongest case is a continuous population of parallel prediction-market episodes. Picture a forecasting service processing millions of independent consultations under one disclosure policy. Each episode has an Alice-side information type \(a\), a Bob-side private signal \(b\), and an outcome \(e\). Types include every feature that affects the policy or payoffs, including the conditional law of \((B,E)\) and the market’s scoring setup. Episodes of the same type are interchangeable. The number \(N\) of episodes can be enormous while the support size \(\tau=|\operatorname{supp}(\mu_A)|\) stays small.
The service commits to a policy that assigns episodes of type \(a\) to public messages \(s\). Let \(x_{a,s}\) be the mass of type-\(a\) episodes assigned message \(s\). Then \(x_{a,s}\geq 0\) and \(\sum_s x_{a,s}=\mu_A(a)\). The policy is the same object as the paper’s signaling scheme: \(x_{a,s}=\Pr(A=a,S=s)\). It maximizes Alice’s per-episode market objective,
\[
J(x)=\sum_s\left[\Big(\sum_a x_{a,s}\Big)G(p_s)
-\sum_b\Big(\sum_a \Pr(b\mid a)x_{a,s}\Big)G(p_{s,b})\right],
\]
where \(p_s\) and \(p_{s,b}\) are the event posteriors given the message, and given the message and Bob’s private signal, respectively. A solution is a feasible mass allocation \(x\), or equivalently a committed signaling policy, with maximum \(J\). This is a population interpretation of the paper’s sender-commitment problem: its Theorem 2 gives the same prior and sender objective in the equivalent private-receiver persuasion model. The connection and the algorithmic results below are proved in the paper. [Published chapter PDF](https://bpb-us-e1.wpmucdn.com/sites/harvard.edu/dist/b/845/files/2025/01/anunrojwong2019_chapter_computingequilibriaofpredictio.pdf)
My lead is Mass-Commitment-Exact, mirroring Theorem 3. Its instance is a finite rational prior \(\mu\) over \((A,B,E)\) and a convex expected-score function \(G\) with \(k\) linear pieces. A message can be taken to be a recommendation tuple \(s=(i_0,(i_b)_{b\in\mathcal B})\): it recommends an action when Bob has not revealed a signal and one for each possible \(b\). Choose masses \(x_{a,s}\) summing to \(\mu_A(a)\), subject to obedience: for every positive-mass message, each recommended action maximizes its conditional expected \(U_G\)-utility, both before and after each \(b\). Maximize the per-capita sender objective \(J\); the output is an optimal mass allocation and its induced recommendations. Theorem 3, proved here, states that Alice’s optimal commitment can be computed in time \(\operatorname{poly}(k^{|\mathcal B|},|\mathcal A|,|\mathcal E|)\). With bounded \(|\mathcal B|\), this is polynomial in \(k,\tau,|\mathcal E|\), so this mirror is Class A in that regime. Its recommendation formulation yields an LP with at most \(k^{|\mathcal B|+1}\) message labels and linear obedience constraints. Further questions include whether large \(|\mathcal B|\) admits a more efficient method and how to round an optimal mass policy to \(N\) discrete episodes with a proved additive error.
Two additional anchors extend the case to other parameter regimes. Mass-Commitment-Approx-A, mirroring Theorem 4, has the same instance and objective, with \(|\mathcal A|=\tau\) constant and \(G\) locally Hölder continuous and bounded in \([-L,L]\). The question is to return a signaling policy whose sender objective is within \(\delta\) of optimal. Theorem 4, proved here, states that this can be done in time \(\operatorname{poly}(|\mathcal B|,|\mathcal E|,1/\delta,L)\). It gives an approximate Class A mirror when the sender-side type support is small, even as the receiver signal and event spaces grow. The next questions are whether the constant-support promise can be relaxed and what guarantees persist when the prior is estimated from data.
Mass-Commitment-Approx-BE, mirroring Theorem 5, uses the same mass-policy problem with \(|\mathcal E|\) and \(|\mathcal B|\) constant, and locally Hölder, bounded \(G\); \(|\mathcal A|\) may vary. Theorem 5, proved here, states that an optimality-gap-\(\delta\) signaling scheme can be computed in time \(\operatorname{poly}(|\mathcal A|,1/\delta,L)\). This is another approximate Class A regime, with the complexity polynomial in the number of sender-side types. Further questions include whether the small event and receiver-signal promises can be weakened and where hardness appears beyond the theorem’s guarantees. The stated bounds suppress the bit length of the rational input; a ChoCo formulation should make that encoding dependence explicit.
The authors would have a direct route to recognizing these questions: the messages, conditional posteriors, scoring objective, and committed policy are those of their problem, while the mass \(x_{a,s}\) represents the shares of a large cohort assigned each message. The paper also proves that an optimal committed scheme yields an approximate PBE in the uncommitted Alice–Bob–Alice market, which connects the policy problem back to market equilibrium.
My weakest point is the scenario. The paper studies two strategic players in one market; this mirror treats many independent market episodes as a population. Its prior \(\mu\) is a probability distribution over one episode’s signals and outcome, not itself a population distribution. The parallel-episode scenario supplies the population interpretation, but the policy was already randomized in the original model, so mass allocation may add little algorithmically beyond that interpretation. I think the mirror is plausible because the mass is a literal share of a large, typed cohort and the objective is the paper’s objective averaged across episodes. It is a focused mirror of the commitment computation, not a claim that the paper’s single-market game already contains a continuous population.
Finally, the paper has no named hardness anchor: its conclusion says intractability results are not yet known. These three anchors therefore support tractability questions, not the ChoCo question of whether a continuous relaxation dissolves discrete hardness. The mirror is strongest as a Class A case; the hard boundary remains open.
The strongest case against is not that the parallel-episode story is impossible. It is that, under the story that makes it plausible, all three proposed mirrors are already the paper’s signaling problem under a population interpretation. The identification is exact: \(x_{a,s}=\pi(s,a)\). The paper’s \(\mu_A(a)\) is the probability of Alice’s signal, and \(\pi(s,a)\) is the probability mass assigned to message \(s\) conditional on that signal. The proposed per-capita objective is the paper’s expected objective. Calling those probabilities fractions of a large cohort does not create a new population-level decision variable or constraint.
That undercuts Mass-Commitment-Exact. Theorem 3’s recommendation labels and obedience constraints already give the finite LP for choosing those masses. In a batch of independent episodes, applying the policy to each episode gives expected aggregate utility equal to the number of episodes times the same per-episode objective. There is no shared capacity, resource, or cross-episode interaction for a continuous allocation to resolve. If the proposed mirror instead requires exact realized quotas or couples decisions across episodes, that may be a worthwhile new batch-design problem, but the coupling is an added assumption; it is not forced by taking the population limit, and the theorem’s mirror no longer specifies it.
The same issue defeats Mass-Commitment-Approx-A and Mass-Commitment-Approx-BE. Their parameters count possible values of signals and event outcomes in one market instance. They are not the number of agents, nor the support size of a population of agents. Treating many episodes as a cohort makes those alphabets look like cohort types, but then the mass policies are still just randomized signaling schemes. Theorems 4 and 5 already optimize those schemes approximately. Their grids discretize posteriors—a probability and belief representation—not a population allocation that the paper previously lacked. That distinction matters for ChoCo’s scope: continuity in a message or posterior space does not itself continuize the society.
The best version of the proponent’s scenario—millions of independent consultations under one disclosure policy—therefore faces a fork. If the policy is applied independently, its continuous mass formulation is only a relabeling of the paper’s existing probabilities and objective. If the service centrally allocates messages across episodes subject to shared quotas, or otherwise makes episodes interact, it has introduced a new batch mechanism-design problem. Such a project might be interesting, but its central question comes from the added coupling, not from a continuous mirror of the paper’s results.
I would not argue that the paper lacks computational results, or that its answers are already known and therefore uninteresting. It has clear algorithmic theorems, and the absence of hardness results is beside the point. The negative case is narrower: none of the three anchors yields a distinct high-multiplicity computational problem without adding structure that the paper does not study. This case is weakest against the cohort interpretation itself. A reader could reasonably accept a population of repeated market episodes as a sensible regime; the harder claim to sustain is that merely calling the prior’s probability masses population shares makes that regime a worthwhile new continuization for ChoCo.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.