| paper | d4-conf-ecai-2023-0302 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: The \(1\)-additive guarantee always holds; choices are polynomial-time computable and independent of admissible \(N\). Writing \(u_* = \min_s U_s^T\), the deficit is \(D_N = \max\{0,T(m-1)/N-u_*\}\), hence \(D_N\to0\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given a finite support of complete Borda-ranking schedules with rational masses \(\mu_s\) summing to \(1\), revealed round by round, choose one candidate at each round by lexicographically maximizing the mass-weighted distribution of accumulated per-type utilities. For population scales \(N\) with \(N\mu_s\) integral, determine the computation required and whether the rule gives each type the paper's \(1\)-additive proportionality guarantee with benchmark \(T(m-1)/N\), including the limiting behavior as \(N\to\infty\).
Types are complete Borda-ranking schedules, each with mass \(\mu_s\). At each round the mechanism sees the types' current rankings and past choices, then selects a candidate to maximize the leximin ordering of utilities, with each type's utility repeated according to its mass at scale \(N\). The benchmark is the per-agent proportional value \(T(m-1)/N\).
Theorem 8's proportionality benchmark is \(T(m-1)/N\), which tends to zero as the population scale \(N\) grows, so its additive guarantee loses force; the proponent's offline question also does not directly mirror this online theorem.
fatal: False
The mirror covers Theorem 8's online Borda leximin guarantee. It leaves aside the paper's offline unrestricted MPP result, its other mechanisms, and its fairness trade-offs.
The strongest honest positive case is a plausible mirror of the paper’s offline leximin problem, but the paper has no qualifying numbered computational anchor under your rule. Its numbered results concern fairness guarantees and impossibility, not whether a computational problem is in P, NP-hard, or otherwise classified. For example, the printed Theorem 8, proved here, says that with Borda valuations the online leximin mechanism gives every agent a \(1\)-additive approximation of proportionality. That is a fairness guarantee, not a complexity result. Section 5 does say that computing certain offline mechanisms is intractable, but that claim is unnumbered and relies on cited hardness results. I would not present it as an eligible anchor.
A concrete candidate mirror is Continuous Prop-Leximin Sequence. Let \(C\) be the candidates and \(1,\ldots,T\) the decision rounds. The input is a finite support \(S\) of complete valuation types, where a type \(s\) specifies its value \(v_s^r(c)\) for every candidate \(c\) in every round \(r\), and has rational population mass \(\mu_s>0\), with \(\sum_s\mu_s=1\). A solution is one chosen candidate \(o^r\in C\) for each round. Its utility for type \(s\) is \(u_s(\boldsymbol{o})=\sum_r v_s^r(o^r)\). Normalize by that type’s ideal utility \(M_s=\sum_r\max_c v_s^r(c)\), and associate the ratio \(u_s(\boldsymbol{o})/M_s\) with mass \(\mu_s\). The task is to find an outcome whose resulting distribution of normalized utilities is lexicographically maximal from the lowest mass upward. This is the mass-weighted analogue of the paper’s \(LMin^{Prop}_{off}\): in a finite population, the factor \(1/n\) in \(Prop_s=M_s/n\) is common to all agents and does not change the leximin ordering.
The regime could be a large city making recurring public decisions, with many residents sharing a small set of complete valuation schedules—for example, stable stakeholder groups with the same Borda ranking in each round. Here the type is the whole schedule, not just a single-round ranking; mass is the fraction of residents with that schedule. Millions of residents and a modest support size are plausible if those schedules recur. The model keeps the paper’s decision sequence and its fairness objective, while replacing the voter list with type masses.
For this candidate I expect hardness to transfer in the unrestricted case: a finite instance embeds by assigning each distinct voter type its fraction of the population, and exact leximin computation can reveal whether proportionality is attainable. The paper itself points to that computational obstacle, relying on hardness cited from elsewhere. Whether the problem becomes tractable when support size \(\tau\) is small is a further question; so are its parameterized complexity in \((m,\tau,T,L)\) and how its online analogue behaves. This is a reason to study the mirror, not an anchor supplied by the paper.
The soft spot is that the paper’s named results do not classify this computation, and the full-schedule type assumption can make \(\tau\) grow rapidly with \(T\). Also, MPP alone depends on which types are present, not their masses; the mass-sensitive leximin objective is the closer mirror of the mechanism. So there is a credible, precise population model that the authors could recognize, but the paper does not provide a numbered computational result on which the requested anchor-based case can rest.
The strongest negative point is that this paper has no numbered theorem classifying the complexity of a computational problem. Theorem 8 gives an additive fairness guarantee for online leximin; the other numbered results concern fairness properties, impossibility, or approximation guarantees. Section 5’s claim that computing some offline mechanisms is intractable is unnumbered and relies on cited hardness results. So the proponent is right that Theorem 8 is not a qualifying computational anchor.
The best version of their proposed offline mirror is coherent: make each type a complete valuation schedule across all \(T\) rounds, give it rational mass, and maximize the mass-weighted leximin ordering of normalized utilities \(u_s/M_s\). For rational masses, this ordering can be represented by duplicating each type according to a common denominator. A large city with recurring stakeholder groups could plausibly have many residents per schedule. The identity objection therefore fails, and the mirror has a sensible high-multiplicity regime.
What weakens the case is that the paper’s \(MPP\) theorem says leximin maximizes the minimum normalized utility by definition; its continuous counterpart would not establish a computational result. A complexity study of computing the weighted leximin outcome could still be worthwhile, but it would be a new target, not a mirror of a numbered computational result in this paper. Theorem 8 is a poor substitute: its \(1\)-additive guarantee relies on the finite Borda setting, and under growing population size the benchmark \(Prop_i=T(m-1)/n\) shrinks until the additive bound becomes vacuous. A useful normalized guarantee would ask a different fairness question.
That defeats the proponent’s anchor-based case, but it does not establish the universal claim that no continuous mirror is worth the programme’s time. The offline weighted leximin problem survives as a sensible computational problem; the honest negative case is strong on the absence of a qualifying anchor and weak on excluding that problem as worthwhile.
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.