| paper | d4-conf-ijcai-2018-0983 |
| 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: Polynomial-time solvable in \(m,\tau,L\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite package set \(O\), two binary-rational distributions \(\mu^1,\mu^2\) over complete strict rankings of \(O\), and a valid current VAOV history, suppose each distribution induces a strict transitive majority ranking. What move does the Theorem 10 SPE prescribe at that history, and what agreement outcome follows if both representatives continue using its strategies?
Each constituency is a society whose types are complete rankings of the finite package set \(O\), with type masses summing to \(1\). Pairwise majority comparisons induce each representative’s strict transitive ranking. The representatives then play the paper’s VAOV protocol; the computation returns the prescribed offer or response and the continuation agreement.
The theorem sees only two rankings after majority aggregation, so population mass affects the result only through a newly chosen collective-preference rule that the paper does not study.
fatal: False
The mirror covers Theorem 10’s full-information SPE strategy and continuation outcome. It leaves aside the RC comparison and monotonicity results, and the no-information, maxmin, and asymmetric-information results.
My strongest case is a Majority-Mandate VAOV-SPE query: two large constituencies each authorize a representative to negotiate over a finite set of policy or contract packages. The members of constituency \(k\) have strict rankings of the packages, and \(\mu^k_t\) is the fraction with ranking \(t\). Define the constituency’s preference by weighted pairwise majority: \(o\succ_{\mu^k}o'\) when more than half its mass ranks \(o\) above \(o'\). Restrict inputs to profiles where this relation is strict and transitive. That restriction fits settings such as single-peaked package preferences, where majority gives a coherent ranking.
A concrete regime might have millions of members in each constituency but only tens or hundreds of distinct rankings. A member’s type is their complete ranking; its mass is their fraction of the constituency. The representatives alternate offers of packages, cannot repeat an offer, and accept or reject according to their constituencies’ induced rankings. Each representative maximizes that ordinal mandate. The packages remain finite; the population distributions are the continuous objects.
The anchor is Theorem 10, proved in this paper. It says Strategies 1 and 2 specify a subgame-perfect equilibrium. In Strategy 1, the current proposer offers an outcome in the intersection of the two parties’ low-ranked sets if that intersection is nonempty; otherwise, the proposer offers the responder’s least-preferred available outcome. In Strategy 2, the responder accepts an offer if it is at least as good, by their ranking, as the continuation outcome \(o_a(H)\) implied by following the offering strategy from the next round; otherwise they reject. The proof also says that, from any given state, computing the prescribed strategy takes time linear in the number \(m\) of outcomes. The theorem statement is an equilibrium result rather than a separately labeled “in P” theorem, so this is the paper’s constructive algorithmic anchor, not a formal complexity classification. Its result is proved here; the paper cites earlier work for related VAOV results.
For the continuous query, the instance is a finite outcome set \(O\), two binary-rational distributions \(\mu^1,\mu^2\) over supported strict rankings, and a valid current VAOV history. The majority-order promise above supplies the representatives’ rankings. The question is: what move does the Theorem 10 SPE prescribe at this history, and what agreement outcome follows if both representatives continue to use its strategies? A solution gives the current offer or accept/reject decision and the induced continuation outcome. It need not list the exponentially large game tree: the paper’s strategy is evaluated from the supplied state.
I expect this query to be tractable. The pairwise majority rankings can be computed from the supported types in time polynomial in \(m\), \(\tau_1+\tau_2\), and the encoding length \(L\); then Theorem 10 supplies the equilibrium action and continuation in linear time in \(m\), given the rankings. The paper’s theorem therefore gives a direct algorithmic core for the mirror. Further questions include how equilibrium recommendations change when small mass shifts alter a majority comparison, and how to handle profiles with tied or cyclic majority relations.
The scope is deliberately narrow: this mirrors Theorem 10’s SPE computation, not the paper’s no-information or maxmin results. The weakest point is that the strategic players here are constituency representatives, while the paper studies two agents directly. Turning member distributions into representative rankings adds a majority-aggregation layer and rules out cycles by assumption. That makes this a plausible collective-bargaining extension, but the authors might regard it as an extension of VAOV rather than the direct continuous form of their original two-agent problem. Also, once the majority rankings are computed, the masses no longer affect the game unless they change those rankings. So this is a defensible population mirror, though it does not reveal a new continuous-optimization phenomenon or test whether population-driven hardness disappears.
Theorem 10 is a genuine computational anchor: it gives strategies that specify an SPE and can be computed from a state in time linear in the number of outcomes. The difficulty is that its strategic society has exactly two members. Each is already represented by one complete ranking; the theorem contains no population whose members’ actions or outcomes interact.
The proposed constituency mirror adds a majority rule to turn each distribution into a representative’s ranking. That is coherent, and on a single-peaked domain the majority order can be represented by the median member’s ranking. It is also a separate institutional choice: the paper gives no reason to use majority mandates rather than another way of forming a group preference. After the mandate rankings are formed, the masses leave the VAOV game. The question then combines an aggregation step with the original two-player theorem; it does not make the population itself part of the negotiation problem.
A cleaner population construction would distribute mass over independent negotiation instances, with each type specifying both parties’ rankings. If \(F(r_1,r_2)\) is the SPE outcome, the mass assigned to outcome \(o\) is simply
\[
\nu_o=\sum_{(r_1,r_2):F(r_1,r_2)=o}\mu_{r_1,r_2}.
\]
This is a well-defined population statistic, but it batches applications of Theorem 10. There is no cross-type constraint or population-level decision for the continuous model to resolve. Letting the population members themselves make offers would create a different protocol and a different strategic game.
So the strongest negative case is that every plausible route either compresses the population into two rankings before applying the theorem, or aggregates outcomes from independent games after applying it. Neither gives Theorem 10 a computational question about a continuous society. The case is weakest at the constituency example: delegated bargaining between large, single-peaked constituencies is plausible, and its authors might regard that extension as worthwhile. I can argue that it studies mandate formation wrapped around VAOV, rather than a continuous mirror of the paper’s two-party problem; I cannot rule out its value in a broader study of collective bargaining.
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.