| paper | d4-conf-atal-2017-0186 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
Theorem 3 is a named computational hardness result. But in the proposed atomless model, an individual deviation changes no score, so the uncapped bonus makes approving every alternative the unique best response; this changes the strategic problem rather than merely making its answer easy. The proponent acknowledges the loss of pivotality but does not establish that the resulting nonatomic equilibrium question is one the authors would recognize as their problem.
fails bit b-changes — the continuum limit changes the question
The proponent notes that atomlessness removes unilateral pivotality, but does not answer the remaining point: this changes the finite voters’ strategic equilibrium problem into a nonatomic one with no individual influence.
fatal: True
The proposed question covers Theorem 3’s uncapped-bonus results for \(\exists NE\) and \(\exists NETIE\) . It leaves the other uncapped results and the capped-bonus trembling-hand analysis aside; the proposed coverage does not yield a surviving mirror.
The cleanest positive mirror is a nonatomic Doodle poll game. I would anchor it on the paper’s hardness result, while being explicit that the continuum version changes the strategic effect of an individual vote.
The anchor is Theorem 3, proved in this paper (the proof is omitted for space). It states that, with uncapped social bonus \(\kappa=|C|\), uniform random tie-breaking, and trichotomous voter preferences, both \(\exists NE\)—whether a given game has a pure Nash equilibrium—and \(\exists NETIE\)—whether it has a pure Nash equilibrium whose provisional-winner set contains more than one candidate—are NP-complete. The theorem concerns the paper’s Doodle poll games, where each voter chooses an approval ballot and gets utility from the election outcome plus a bonus for approved candidates.
A plausible regime is a large workplace or university choosing among meeting times: perhaps \(10^4\) participants but only tens or hundreds of distinct preference types, because people share recurring shift patterns and availability. A type must specify the participant’s complete preference and utility vector over the time slots; mass \(\mu_t\) is the fraction of participants with that type. This is a high-multiplicity regime, though exact agreement on cardinal utilities makes the scenario less routine than grouping people by availability alone.
Here is the lead question, nonatomic Doodle-NE existence. An instance consists of a finite candidate set \(C\), the paper’s bonus parameter \(\beta>0\) and uncapped bonus \(\kappa=|C|\), and a finite list of trichotomous utility types \(t\), each with binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Assume \(\beta\) satisfies the paper’s restriction that the social bonus cannot outweigh preference differences. Model the population as atomless. A measurable ballot assignment \(b\) gives each participant a subset of \(C\); candidate \(c\)’s score is \(s_c=\lambda\{\omega:c\in b(\omega)\}\), where \(\lambda\) is population mass. The provisional winners are the maximum-score candidates, with ties broken uniformly at random. Each type \(t\) receives its expected outcome utility plus \(\beta |b(\omega)|\).
The question is: does this population game have a pure Nash equilibrium, and, if so, return a measurable ballot assignment that is one? A unilateral deviation changes no score in an atomless population, so it leaves the election outcome fixed. Since \(\beta>0\) and the bonus is uncapped, every participant’s best response is to approve all of \(C\). Thus the all-approve assignment is an equilibrium for every instance, and is the unique equilibrium up to a null set. The problem is tractable: return that assignment in time linear in the support representation. I expect the finite NP-hardness to dissolve in this mirror; no hardness transfer follows from Theorem 3.
I think the authors could recognize this as their approval game with the population continuized: it keeps their alternatives, ballots, type utilities, social bonus, tally, tie-breaking, and equilibrium question. Its scope is deliberately narrow: it mirrors Theorem 3’s uncapped, random-tie equilibrium-existence results, not the paper’s capped-bonus trembling-hand analysis.
The weak point is also the reason the answer becomes easy. Atomlessness removes unilateral pivotality, which is central to finite voting games; the continuum equilibrium is therefore a natural population limit of their model, but a poor account of finite voters’ strategic incentives. That makes the mirror a credible test of whether this hardness survives population continuization, not a claim that the continuum result explains Theorem 3’s reduction. The next useful question would be how equilibrium existence changes as individual voter mass becomes small but remains positive.
Theorem 3 is a genuine computational anchor: it proves NP-completeness for pure Nash equilibrium existence with uncapped bonuses, random tie-breaking, and trichotomous preferences. So the objection is not that the paper lacks a result to mirror. The problem is that the proposed continuum changes what a unilateral deviation can do.
In an atomless population, changing one participant’s ballot changes each candidate’s mass score by zero. The election outcome is therefore fixed from that participant’s perspective. With an uncapped positive bonus, approving every alternative is then strictly best, regardless of the voter’s preferences or the current scores. The continuum equilibrium does not retain the pivotality that drives the finite game’s strategic incentives; it removes it by definition. That makes the proposed question a poor mirror of Theorem 3’s equilibrium-existence problem, even if its easy answer is itself a valid result.
The paper’s capped-bonus analysis does not restore the missing connection. In the same atomless model, a participant cannot make an alternative win by approving it, so there is no strategic reason to choose “safe” unpopular alternatives. Theorem 4’s trembling-hand refinement likewise loses its outcome-selection role: an individual’s intended ballot, or tremble, has zero effect on aggregate scores. This applies to the paper’s most plausible alternative computational anchor as well as to Theorem 3.
One could preserve pivotality by making each voter type a strategic bloc whose entire mass changes ballots together. But that treats a type—a group of otherwise identical individuals—as a coordinated player. Allowing arbitrary positive-mass coalitions to deviate instead would ask about coalition stability, not the individual Nash or trembling-hand equilibria studied in the paper. Either might support a separate project, but neither repairs this mirror without changing the strategic object.
A large electorate with a small set of shared utility types is plausible, and I would not argue that the paper has no high-multiplicity regime. The negative case is narrower: for its equilibrium results, population continuization makes each voter negligible precisely where the paper’s analysis depends on individual influence. That is a substantial reason to reject this particular anchor, though it does not establish the universal claim that no worthwhile continuous mirror exists in any scenario.
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.