| paper | d4-conf-ecai-2016-0265 |
| 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: Every valid instance admits a rational stable allocation, constructible in time polynomial in \(m,\tau,L\). The decision problem is in \(\mathrm{P}\). · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given a candidate set \(M\), a tie-break order \(\triangleright\), and a binary-rational distribution \(\mu\) over a finite support \(T\) of strict rankings, is there a rational allocation \(q_{t,a}\ge 0\), with \(\sum_{a\in M}q_{t,a}=\mu_t\), such that no positive-mass coalition whose members all prefer some \(y\) to the current winner \(w\) can reassign its veto ballots to make \(y\) the tie-broken minimum-veto winner? If so, construct such an allocation.
The society is a distribution \(\mu\) over strict-ranking types \(t\in T\). Each type's mass is split among veto ballots by \(q_{t,a}\); candidate \(a\)'s veto total is \(\sum_t q_{t,a}\), and the winner is the minimum-veto candidate under \(\triangleright\). A strong deviation may reassign any measurable submass of eligible types, provided every participating voter strictly prefers the resulting winner to \(w\).
The discrete construction is polynomial in the explicit electorate, so the continuous version may offer mainly an algorithm for succinct high-multiplicity inputs; the proponent identifies the encoding gap but does not establish the compact search problem's payoff.
fatal: False
The mirror covers Proposition 3 and its antiplurality strong-equilibrium construction. It leaves the considerate-equilibrium theorems, results for other voting rules, and convergence results outside the mirror.
The strongest honest anchor is Proposition 3, proved in this paper: with strict preferences, every antiplurality voting game has a strong equilibrium. The proof constructs one using a feasible elimination procedure; the authors state immediately afterward that the construction is polynomial-time. The procedure’s general existence result is cited from Peleg and Peters [22]. This is an algorithmic anchor, though the paper does not present it as a complexity-class theorem. It offers no named hardness result, so this mirror would study how equilibrium construction behaves under continuization, not whether discrete hardness disappears.
A plausible regime is a large association choosing among a fixed set of proposals by veto ballot: every member vetoes one proposal, and the proposal with the fewest vetoes wins under a fixed tie-break. Let a type be a strict ranking of the proposals. Many members may share each ranking, so the number of voters is large while the support size \(\tau\) is relatively small. A type describes everything relevant here: preferences over outcomes. Members retain individual veto ballots; their type’s mass can be divided among those ballots.
I would call the resulting problem Antiplurality Strong-Equilibrium Search\(_\infty\). An instance gives candidates \(M\), a tie-breaking order \(\triangleright\), and rational masses \(\mu_t\) over a finite support of strict rankings, with \(\sum_t\mu_t=1\). A proposed ballot allocation is \(q_{t,a}\ge 0\), where \(q_{t,a}\) is the mass of type \(t\) vetoing \(a\), and \(\sum_a q_{t,a}=\mu_t\). The veto total for \(a\) is \(v_a=\sum_t q_{t,a}\); the winner \(w\) has the fewest vetoes, with ties broken by \(\triangleright\).
The question is whether there is such an allocation \(q\) with no strong improving deviation, and, if so, to output one. Precisely, a deviation to a candidate \(y\ne w\) may move any measurable mass from existing type–ballot groups to new veto ballots, leaving the rest unchanged. It is improving if every participating type \(t\) satisfies \(y\succ_t w\) and \(y\) becomes the winner. Because the population is nonatomic within each type, any fractional submass up to the available \(q_{t,a}\) can participate. A solution is an exact rational allocation \(q\) for which no such deviation exists. There is no separate welfare or cost objective: the task is to find a stable ballot allocation.
This is a credible mirror of Proposition 3 because it preserves the rule, the individual action, and the strong-equilibrium criterion the proposition studies. It does not add the social-network consideration condition: Proposition 3 concerns strong equilibrium, where any coalition may deviate. That keeps the mirror tied to its anchor rather than extending it to the paper’s other results.
My first guess is Class A: with finitely many preference types and ballot choices, a fractional version of the elimination construction may yield a polynomial algorithm in \(m,\tau,L\). But that is a conjecture, not a consequence of Proposition 3. The main obstacle is whether the construction survives normalization: the finite proof uses integer ballot counts and can rely on a one-vote margin, which vanishes as a fraction of a growing electorate. The continuum may require strict score margins or may admit distributions with no equilibrium.
The mirror covers only Proposition 3 and its construction for antiplurality strong equilibria. It does not cover the paper’s considerate-equilibrium theorems, its results for other voting rules, or its nonconvergence propositions.
My weakest point is the existence of a sensible continuum counterpart to that integer construction. The mass model is faithful to the high-multiplicity regime, but the discrete polynomial construction does not establish a polynomial algorithm in the binary encoding of the masses—or even guarantee that every continuous instance has an equilibrium. Those are the first questions the mirror should ask.
Proposition 3 is the only credible anchor, and it is a thin one. Its stated result is existence of a strong equilibrium; the paper adds afterward that the construction is polynomial time. That makes equilibrium search an algorithmic corollary, but the paper does not set up or classify a computational problem. The other results concern existence or convergence, not worst-case complexity. So this paper offers no complexity landscape for a continuous mirror to chart.
The proposed high-multiplicity setting is sensible: many members can share a ranking, and the network is irrelevant to this particular proposition because it concerns strong equilibrium. I would not reject the mirror on the grounds that voters are individuated or that a type cannot be divided among ballots.
The stronger version is also well-posed. Given an allocation \(q_{t,a}\) of each type’s mass among veto ballots, a deviation to candidate \(y\) can be represented by variables for how much mass moves from each ballot to each other ballot, restricted to types with \(y\succ_t w\). The resulting veto totals and winner conditions are linear. Thus, for a proposed \(q\), checking whether a profitable deviation exists reduces to finitely many linear-feasibility questions, one per candidate. Searching for a stable allocation may be harder, but the model has only \(\tau m\) allocation variables and no permutation-pricing problem. Its main possible contribution is a succinct-input algorithm for an equilibrium construction the paper already gives in polynomial time for an explicit electorate.
That is a narrow potential payoff, not a decisive objection: a compact algorithm for rational type masses could still be useful, and a continuous equilibrium question is recognizable as the authors’ problem. I can make the case that this is a weak ChoCo anchor because the paper contains no substantial complexity result to mirror and the natural formulation appears low-dimensional. I cannot honestly establish the stronger claim that no worthwhile 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.