| paper | d4-conf-ijcai-2015-0587 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | no |
The paper has no named result about computing equilibria or classifying their complexity. Theorem 4 proves that some instances lack a pure Nash equilibrium, which does not meet the stated computational-result gate. The proposed constituency model also collapses to two aggregate valuation vectors, so its type distribution adds no population structure to the game.
fails bit a — no named computational result to mirror
The proposed mirror targets Theorem 4. It leaves aside Theorems 5–9 on approximate and informed-tie-breaking equilibria, Theorems 10–12 on equilibrium fairness and welfare, and Theorems 1–3 on characterizations.
I can’t identify a named complexity result in this paper of the kind the ChoCo brief asks for: none of its theorems classifies a problem as NP-hard, polynomial-time solvable, FPT, or similar. The strongest honest positive-side case is therefore provisional: it uses a named equilibrium-existence result, but that result is not a computational-complexity anchor.
A plausible population setting is a bilateral settlement between two large constituencies, each represented by one negotiating party. Constituents value \(m\) divisible issues or resources. On side \(k\in\{A,B\}\), each type \(t\) has a strictly positive normalized valuation vector \(v^{k,t}\in\mathbb Q_{>0}^m\), and type \(t\) has mass \(\mu^k_t\), with \(\sum_t\mu^k_t=1\). The representative’s true valuation is the constituency average
\[
\bar v^k_j=\sum_t\mu^k_t v^{k,t}_j.
\]
Each representative reports a positive normalized vector; Adjusted Winner applies to the two reports, and each side’s payoff is its constituency’s average utility for the allocation. The regime could have arbitrarily many constituents but a fixed, small support \(\tau_A+\tau_B\). Constituents share types; the two representatives remain the strategic players.
The closest anchor is Theorem 4, proved in this paper. It states that Adjusted Winner with continuous strategies and lexicographic tie-breaking is not guaranteed to have a pure Nash equilibrium. The paper proves this with a two-item instance whose true valuations satisfy \(b_1>a_1>a_2>b_2>0\), showing that every possible strategy profile admits a profitable deviation. For example, normalized aggregate valuations \(a=(0.6,0.4)\) and \(b=(0.7,0.3)\) meet those inequalities. A constituency population can realize them directly, even with one type per side.
The corresponding problem, Mass-AW-PNE Existence, is: given \(m\), the finite rational type supports and masses for both constituencies, and their type valuation vectors, decide whether the representatives’ continuous-strategy Adjusted Winner game has a pure Nash equilibrium. A YES solution is an equilibrium report pair; a NO solution is a proof that none exists. Theorem 4 supplies a NO instance, but does not classify the decision problem. For this mirror, the paper’s nonexistence phenomenon survives; it does not establish algorithmic hardness or tractability. Since the type distributions collapse to two average valuation vectors, I would expect any eventual complexity classification to come from the resulting two-player game, rather than from population multiplicity. The paper gives no result that lets me place the problem in Class A, B, or C.
The scope is only the equilibrium-existence question behind Theorem 4. I would not claim this mirrors the paper’s characterizations or its welfare bounds. The constituency interpretation is plausible in the paper’s dispute-settlement setting, and the mirror makes the population continuous in the utilities that determine the parties’ payoffs.
The weakness is substantial: once the type masses are averaged, the population disappears from the game. The paper already studies continuous valuation vectors and continuous strategies; the proposed mirror adds a population interpretation but no new computational structure. It may be a sensible application of Theorem 4, but without a named complexity result in the paper, it is a weak fit for a programme specifically about the complexity landscape of continuous populations.
Theorem 4 is the proponent’s strongest anchor, but it is an equilibrium-existence result, not a complexity result. It proves that some two-player instances lack a pure Nash equilibrium; it gives no algorithmic classification of deciding, for an arbitrary instance, whether one exists. That decision problem could be posed, but it would be a new computational question built around the theorem, not a computational result from the paper that continuization reveals.
The proposed constituency model does not give that question a substantive population dimension. For side \(k\), if type \(t\) has mass \(\mu^k_t\) and valuation \(v^{k,t}\), then its average utility for an allocation \(W\) is
\[
\sum_t \mu^k_t \sum_j v^{k,t}_j w^j
= \sum_j \bar v^k_j w^j,
\qquad
\bar v^k_j=\sum_t\mu^k_t v^{k,t}_j.
\]
So the game, its best responses, and its equilibria depend only on the two average valuation vectors. Every such population input collapses exactly to an ordinary two-player instance; conversely, a singleton type represents any rational average vector. The support size and the distribution over types add no structure for the equilibrium question.
A stronger constituency interpretation does not fix this while preserving the paper’s result. If representatives report average valuations, the collapse remains. If individual constituents report or act strategically, the model needs a new aggregation or delegation mechanism, and Theorem 4 no longer supplies the anchor. The paper’s applications make large constituencies imaginable, but that makes a plausible story for the averages; it does not make the population the computational object. This is not an objection that the continuous answer might be dull. It is that the proposed mirror’s computation never uses the continuous society.
The negative case is strongest on that narrow ground: no named complexity result to mirror, and the best proposed population model quotients away its types before the game begins. It is not airtight as a claim that no worthwhile question exists. One could study the complexity of equilibrium existence for continuous-strategy Adjusted Winner games, and a constituency interpretation may help motivate it. But that would be a question about the original two-player game on aggregate valuations, not a complexity landscape created by continuizing the population.
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.