| paper | d4-conf-ijcai-2017-0082 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a fixed linear tie-break, and finitely many delegated voter blocs \(t\) with rational masses \(\mu_t>0\), \(\sum_t\mu_t=1\), shared truthful rankings \(r_t\), and current ballots \(b_t\), set \(P_\mu(a,b)=\sum_{t:\,a\succ_{b_t} b}\mu_t\) and \(\mathrm{mm}_\mu(c)=\min_{d\ne c}P_\mu(c,d)\). Start from \(b_t=r_t\). At each step, one bloc changes its whole ballot to a best response: the new winner is strictly preferred under \(r_t\) to the current winner, and no alternative ballot gives that bloc a more-preferred winner. Decide whether an infinite legal sequence is reachable from the truthful state, equivalently whether a directed cycle is reachable among the finitely many ballot profiles.
A weighted Maximin voting game whose strategic agents are delegated blocs: each bloc has a shared ranking and control arrangement, carries mass \(\mu_t\), and changes its whole reported ballot in a sequential best-response move. The society is the distribution of these blocs; pairwise support and the Maximin winner are calculated from their masses.
A delegate’s move changes an entire constituency, adding coordination absent from the paper’s one-voter dynamics; the proposed mirror therefore does not cover independently acting atomless voters.
fatal: False
The mirror covers only Theorem 1’s Maximin best-response clause. It leaves the other dynamics and voting rules, and the empirical winner-quality results, aside.
The strongest honest mirror I see is iterative voting by organized voter blocs. A continuum of independent, atomless voters would not preserve the paper’s strategic step: one person changing a ballot has zero effect on the population distribution, and therefore cannot change the winner. In a plausible high-multiplicity regime, though, large associations or caucuses can coordinate their members’ ballots and act through a delegate. Their members share a strict ranking, while the delegate controls the bloc’s share of the electorate. That gives the bloc a consequential move and makes mass the natural unit.
The type is a bloc’s complete shared ranking and ballot-control arrangement; its mass is the fraction of the electorate it represents. Its current submitted ranking is part of the state. A realistic regime could have thousands or millions of members in a handful of associations, so the population is large while the number of distinct strategic blocs \(\tau\) remains small. The winner remains a candidate, and updates remain sequential. The social object being continuized is the electorate’s size and composition.
My anchor is Theorem 1, stated in this paper. It says that Maximin with linear-order tie-breaking does not converge under any of five dynamics: best response (BR), TOP, TB, Kendall–tau-minimal best response (KT), or one-adjacent-swap better response (SWAP). Here “does not converge” means that some valid sequence of moves is infinite. The paper prints a cycling example for BR and points to Koolyk, Lev, and Rosenschein (2016a) for omitted proof details. I would lead with the BR clause; the other four clauses strengthen the theorem, but are not needed to make this case.
The corresponding question is Weighted-Maximin BR-Cycle. An instance consists of candidates \(C\), the fixed linear tie-breaking order, and finitely many blocs \(t\), each with a positive rational mass \(\mu_t\), a shared true ranking \(r_t\), and a current reported ranking \(b_t\); the masses sum to \(1\). Initially \(b_t=r_t\). For reported ballots, define
\[
P_\mu(a,b)=\sum_{t:\,a\succ_{b_t} b}\mu_t,\qquad
\operatorname{mm}_\mu(c)=\min_{d\ne c}P_\mu(c,d).
\]
The winner maximizes \(\operatorname{mm}_\mu\), with the specified tie-break.
A BR move changes one bloc’s whole reported ranking, holding all other blocs fixed. It is legal if the resulting winner is strictly better according to \(r_t\) than the current winner, and no other ballot that bloc could submit would give it a more-preferred winner. The question is: starting from the truthful state, does there exist an infinite legal sequence? A yes-instance has a finite lasso as a witness: a path from the truthful state to a cycle of ballot profiles. There are at most \((m!)^\tau\) profiles, so this is a precise finite-state decision problem on rational-mass inputs. The bloc’s objective is ordinal—get the most-preferred attainable winner—not a social-welfare objective.
The intended correspondence is narrow but concrete. A finite Maximin cycle can be written as rational bloc shares; normalizing voter counts to proportions preserves every pairwise comparison, and scaling the membership behind each coordinated bloc preserves those comparisons too. I therefore expect the theorem’s non-convergence phenomenon to transfer to this regime—Class B-style persistence of the negative result. That is not an NP-hardness claim about deciding cycle reachability: Theorem 1 supplies cycle witnesses, not a complexity lower bound for this new decision problem. The complexity of Weighted-Maximin BR-Cycle in \(m,\tau,L\) is a further question.
This mirror covers the Maximin convergence result only. It does not claim a continuous analogue of the paper’s empirical winner-quality findings, or of its results for the other voting rules. The main follow-up questions are whether cycles persist for arbitrary rational bloc weights, how hard it is to decide cycle reachability, and which restrictions on bloc updates restore convergence.
The weakest point is also the model’s defining choice: these are coordinated blocs, not independent voters. The paper’s examples move one voter at a time; it does not establish that the same cycles survive when each bloc is split into smaller, independently acting voters. If the authors or a referee require an atomless population with unilateral individual moves, this mirror fails. If they accept strategic caucuses as the relevant high-multiplicity actors, it is a direct, testable extension of their Maximin iterative-voting question.
Theorem 1 is the paper’s strongest anchor: it gives a named result about convergence of iterative voting. The difficulty is that its cycles depend on one voter changing one ballot at a time. In an atomless society, a single voter has mass zero. Changing their ballot leaves every pairwise share \(P_\mu(a,b)\) unchanged, so it cannot strictly improve the winner. Under the paper’s better-response definition, there are no legal moves and convergence is immediate. The continuous version degenerates at the step where the dynamics begin.
Normalizing voter counts to shares preserves winners for a fixed profile, but it does not preserve transitions between profiles. If an electorate is replicated \(k\) times, the margins in the cycle scale by \(k\), while one voter’s change still shifts a pairwise share by only \(1/(kn)\). Reproducing the original consequential move requires \(k\) voters to coordinate. That changes the move unit, even when the static election is identical.
The proponent’s caucus model is the strongest repair. Give each association a positive share, a common ranking, and a delegate who changes all its members’ ballots together. This defines a coherent weighted-player voting game, and it could be worth studying. But the strategic players are now the associations or delegates. High multiplicity of their constituencies does not make their joint action follow from the paper’s model of individual voters; coordination and delegation are additional assumptions. The model’s finite strategic core is \(\tau\) blocs, with rational weights. Its cycles would establish something about bloc-level dynamics, not a nondegenerate limit of the paper’s unilateral dynamics.
Allowing arbitrary fractions of a type to move does not remove that issue. A positive-mass fraction can change the outcome only if those voters move together; specifying who chooses that fraction, and why they coordinate, is part of the new game. Leaving changes at infinitesimal scale returns to the zero-impact problem. So the plausible variants either erase the paper’s strategic step or add a collective actor that the paper does not study.
The negative case is weakest against a paper whose authors explicitly want to study organized caucuses: they might recognize that as a worthwhile extension. But the proponent has not shown that the Maximin cycle survives a continuous-population version of the paper’s own one-voter-at-a-time process. They have shown that a related model with mass-bearing collective players can be formulated. That is a more substantial modeling change than replacing discrete voter counts with population shares.
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.