| paper | d4-conf-sagt-2024-0001 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 6.1 rules out a mechanism guarantee but does not show that computing anything is hard. The proposed continuum version is another mechanism-existence question without a computational task, and its positive-mass cohorts also remove the theorem’s pivotal single-agent deviation.
fails bit a — no named computational result to mirror
The proposed question covers only the EF1 arm of Theorem 6.1; it leaves the MMS arm, the positive fair-equilibrium mechanisms, and the other results unaddressed.
The strongest honest anchor is Theorem 6.1, proved in this paper. It is a mechanism impossibility, not a complexity result: the paper contains no named theorem asserting that a problem is in P, NP-hard, FPT, or similar. The positive mechanism results in Theorems 3.1, 4.1, and 5.1 also give existence guarantees, not running-time classifications. So this paper cannot directly anchor a ChoCo complexity claim.
Theorem 6.1 says that no interdependent-value allocation mechanism can guarantee, for every signal vector, both the existence of a pure Nash equilibrium and fairness of all its equilibria with respect to the true signals—under either MMS or EF1. The impossibility holds even for additive dichotomous valuations. Its EF1 construction is the best mirror candidate: there are \(n\) equally entitled agents and \(2n\) goods; only agent 1 has a nontrivial signal, in \(\{0,1\}^{2n}\); and every agent values a bundle \(A\) at \(\sum_{j\in A}s_{1j}\). At the all-ones signal, EF1 requires every agent to receive exactly two goods. Take any equilibrium allocation \(A\), then change agent 1’s signal so that only the goods in \(A_1\) have value. The same reports remain an equilibrium: agent 1 already has both valuable goods, and everyone else’s incentives still depend on the reports. But every other agent values their own disjoint bundle at zero and envies \(A_1\) even after one good is removed. This contradicts EF1.
A plausible high-multiplicity setting is a large public program assigning indivisible equipment or aid to households, where many households share a small number of complete types and their values depend on a shared assessment signal about the goods. For example, there could be two types, \(H\) and \(L\), with masses \(\mu_H=\rho\) and \(\mu_L=1-\rho\), for a fixed \(\rho>0\). Then the population size \(N\) can be large while support size \(\tau=2\). The deliberate change from the theorem is that \(H\) is a cohort with positive mass, rather than one signal-holder among \(N\).
One precise question to hand a prover is Mass-IDV All-Equilibria EF1. An instance has a finite set \(M\) of goods; finitely many complete types \(T\), with binary-rational masses \(\mu_t>0\) summing to one; signal domains \(S_t\); public interdependent valuation rules \(v_t\); and per-capita supplies \(q_j\in[0,1]\) with \(\sum_{j\in M}q_j=2\). Each person must receive an integral bundle \(A\subseteq M\), while aggregate assignments meet the supplies exactly. For the theorem’s special valuation family, take a type \(H\) with signal \(s_H\in\{0,1\}^{|M|}\) and let every agent value \(A\) at \(\sum_{j\in A}s_{Hj}\).
A mechanism receives each person’s report of their own signal and guesses about other types’ signals. It maps the report profile to a measurable assignment of integral bundles, with the mass assigned to each bundle recording the type-level average. Ask whether there is a mechanism such that, for every true signal profile, it has at least one pure equilibrium and every pure equilibrium is EF1 for almost every pair of people under their true values. In this atomless model, an individual deviation leaves the population’s report frequencies unchanged, though the mechanism may still use that person’s own report to determine their bundle. An answer is a mechanism with a proof of these guarantees, or an impossibility proof. This mirrors only the EF1 arm of Theorem 6.1; it does not try to mirror the MMS construction, whose goods supply grows quadratically with population.
I would expect a negative answer to this question to require a new, continuum-specific mechanism argument. The paper’s trichotomy is about computational complexity, so it does not literally classify this mechanism-existence question; no hardness-transfer claim follows from Theorem 6.1. The mirror would prompt useful follow-ups: does the answer change as \(\mu_H\) tends to zero, can approximate EF1 hold in all equilibria, and how does the atomless equilibrium notion relate to finite high-multiplicity games?
The weakest point is the pivotal agent. In the theorem, one person’s signal matters to everyone, while that person has mass \(1/n\); in the proposed mirror, a positive-mass type shares the signal, and a single deviation no longer changes the aggregate reports. That may defeat the proof’s central move. The question remains a credible extension of the paper’s all-equilibria fairness problem, but it is not the paper’s result carried over unchanged.
Theorem 6.1 is a mechanism impossibility, not a computational result. The paper states no complexity classification for a problem over populations, so it gives ChoCo no computational target to continuize. The proposed Mass-IDV question preserves the theorem’s *kind* of claim, but it is still an existence question over mechanisms: the paper places no finite representation on the mechanisms, and the proposal supplies no input encoding or algorithmic task. Choosing a finite mechanism class could create a computational problem, but that would be a new question rather than a mirror of Theorem 6.1.
The theorem’s EF1 argument also depends on a very particular population structure. One agent’s signal determines everyone’s values. After fixing an equilibrium allocation, that agent changes their signal so that only their own bundle is valuable; the other agents’ incentives still depend on the same reports. A finite high-multiplicity version can retain this pivot by giving that agent mass \(1/n\) and the other agents the remaining mass. But it is just the discrete construction written in proportions, with the pivotal type’s mass vanishing as \(n\) grows. In an atomless model, a positive-mass type sharing the signal is a cohort, and an individual deviation no longer changes its aggregate report mass. The proof’s pivotal-agent step therefore does not transfer. Treating the whole cohort as one deviator might restore influence, but changes the equilibrium notion from individual PNE to a coordinated deviation.
That leaves a coherent possible extension: ask whether all equilibria can be EF1 when a positive-mass cohort shares a signal. I can’t rule out that this is worthwhile mechanism-design research. But it is not a computational mirror under ChoCo’s stated scope, and the paper gives no reason to expect a new complexity question from it. The negative case is strongest on that scope boundary; it does not establish that every continuum mechanism question inspired by the paper lacks value.
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.