| paper | d4-conf-ijcai-2020-0676 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
other→other discrete result → its continuous mirror
Answer: Yes. For every positive integer \(k\), the stated supremum is at most \(11\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 2
statement extracted from the paper’s text layer
Given a finite metric alternative set \(M\), a finite support \(T\) of voter locations with rational masses \(\mu_t\), and a positive integer \(k\), draw \(k\) types independently from \(\mu\), shortlist their favorite alternatives, and choose a Copeland winner using the whole society’s mass-weighted pairwise comparisons, with exact half-mass ties resolved by a fixed rule. Is the supremum, over such metric societies with \(OPT_\mu>0\), of \(\bigl(\mathbb{E}[SC_\mu(W)^k]\bigr)^{1/k}/OPT_\mu\) at most \(11\)?
Types are metric locations whose distances induce their rankings and costs; the society is a rational distribution \(\mu\) over finite support \(T\). Its per-capita cost is \(SC_\mu(a)=\sum_{t\in T}\mu_t d(x_t,a)\), with \(OPT_\mu=\min_{a\in M}SC_\mu(a)>0\). The \(PRC_k\) rule samples \(k\) types from \(\mu\), takes their favorite alternatives, and returns a Copeland winner under mass-weighted comparisons; the objective is its worst-case normalized \(k\)th-moment distortion.
The mirror covers Theorem 2’s full-participation PRC guarantee and Theorem 1’s full-participation sample lower bound; it leaves Theorems 3–4’s limited-participation model and the empirical simulations untouched.
The strongest mirror is the paper’s full participation model: a few sampled residents propose alternatives, then the whole society compares them. The paper has no named NP-hardness, \(P\), or parameterized-complexity result. Its numbered theorems instead give sample-complexity and distortion bounds. Those are still computational social choice results, but their continuous counterparts should be judged on sample efficiency, not runtime hardness.
Consider a finite set \(M\) of alternatives and a finite support \(T\) of voter types. A type \(t\) is a point \(x_t\) in the paper’s metric space, so it determines both the voter’s ranking and their cost \(d(x_t,a)\) for every \(a\in M\). The society is a rational distribution \(\mu\) over \(T\), with \(\sum_t\mu_t=1\). Its per-capita social cost is \(SC_\mu(a)=\sum_t\mu_t d(x_t,a)\), and \(OPT_\mu=\min_{a\in M}SC_\mu(a)>0\). The type masses are the fractions of society at each location.
This fits a citywide participatory budgeting election with millions of residents but, say, hundreds of recurring ideal-point types. The alternatives remain discrete budget plans, and the mechanism still selects one plan; the continuous object is the population. For a type distribution, full participation means each type’s ranking counts with weight \(\mu_t\).
My lead is the following continuous problem, anchored by Theorem 2 (proved in the paper): for every \(n\ge3\), the PRC rule with \(k\) samples has normalized \(k\)th moment of Distortion at most \(11+8/(n-2)\), approaching \(11\) as \(n\to\infty\). Its continuous mirror is: given \((M,T,d,\mu,k)\), draw \(k\) types independently from \(\mu\), shortlist their favorite alternatives, and return a Copeland winner under the mass-weighted comparisons of the whole society. Resolve exact half-mass pairwise ties by a fixed rule. The question is whether this rule’s worst-case value of \(\bigl(\mathbb{E}[SC_\mu(W)^k]\bigr)^{1/k}/OPT_\mu\) is at most \(11\). A solution is the stated mechanism and a proof of that bound. The expected answer is yes: the paper’s metric argument adapts by taking a ball around an optimal alternative with radius \(2(1+\delta)OPT_\mu\). It contains strictly more than half the mass; letting \(\delta\) decrease to zero gives the bound \(11\). This is the most persuasive anchor because it gives a concrete, sample-efficient rule for a population distribution. In ChoCo’s terms, it is closest to a tractable result, though the theorem itself does not analyze runtime.
The companion question is the continuous full-participation \(k\)-moment sample threshold. Fix \(k\), and consider rules that first see \(s\) independent favorite alternatives from \(\mu\), then may use the whole society’s rankings among those alternatives to choose a winner. The objective is the worst-case normalized \(k\)th moment across metric societies. Theorem 1 (also proved in the paper) says that with fewer than \(k\) samples, any such mechanism has Distortion at least \(\Omega(n^{1/k})\). The continuous mirror asks whether that moment can be bounded uniformly over societies when \(s<k\). A two-point metric gives the obstruction directly: put mass \(1-\epsilon\) at alternative \(A\) and mass \(\epsilon\) at \(B\), with distance \(1\). If all \(s\) samples come from \(B\), an \(A\)-free shortlist forces every mechanism to return \(B\). That event has probability \(\epsilon^s\), and the normalized moment is at least \((1-\epsilon)\epsilon^{s/k-1}\), which diverges as \(\epsilon\) tends to zero for \(s<k\). So the expected answer is that fewer than \(k\) samples cannot give a uniform moment guarantee. This is a sharp obstruction in sample complexity, not a runtime-hardness result or a Class C claim.
Together, these questions give the mirror a clear boundary: \(k\) samples suffice for a constant moment guarantee, while fewer do not. Theorem 2 is the lead; Theorem 1 shows why its sample count matters. Both cover the full participation results only, not Theorems 3 and 4’s limited participation model.
The weak point is that the paper’s results already make this mirror close to an extension by change of notation: rational \(\mu\) can be represented by a finite electorate using a common denominator, and Theorem 2’s bound tends to \(11\) with population size. The paper does not itself formulate the population as a distribution or state these mass-based questions, so this is not a collision with a continuous-population model. But it may be a modest continuization result rather than a new complexity landscape. Its strongest value is to make the high-multiplicity population object explicit and show that the sample threshold survives when mass, rather than headcount, is the primitive.
The strongest case against is about ChoCo’s research priorities, not whether this paper has a valid continuous mirror. Its results concern sample complexity and distortion guarantees, not runtime or hardness classifications. In a finite-support continuous society, the proposed PRC rule is easy to execute: draw \(k\) types from \(\mu\), then compute weighted pairwise comparisons among at most \(k\) alternatives. So this mirror is unlikely to expose the kind of algorithmic boundary the programme most wants.
But that does not defeat either anchor. For Theorem 2, a citywide population with recurring metric preference types gives a sensible model: sample types from \(\mu\), and let each type’s mass count in the final vote. The proof carries over. A ball of radius \(2\alpha\,OPT_\mu\) around an optimum contains mass greater than one half, and the same metric and Copeland arguments yield the bound as \(\alpha\) decreases to \(1\). There is no identity or measure-zero objection.
Theorem 1’s lower bound also survives directly. Put mass \(1-\epsilon\) at \(A\) and \(\epsilon\) at \(B\), distance \(1\) apart. With \(s<k\) samples, all samples are at \(B\) with probability \(\epsilon^s\); then the shortlist contains only \(B\). The normalized \(k\)th moment is at least \((1-\epsilon)\epsilon^{s/k-1}\), which diverges as \(\epsilon\) tends to zero. This is a valid continuous-population obstruction, not a failure of the model.
There is a real limitation in the mirror’s novelty: every rational \(\mu\) can be represented by duplicating voters, and the paper’s finite-\(n\) upper bound already tends to \(11\). The continuous statements therefore add little new mathematics or computational analysis. That is a case for modest expected payoff, though, not for saying the questions are ill-posed or already continuous under the programme’s criteria.
I can’t honestly defeat the anchors. The paper has a plausible high-multiplicity regime, and its sample-complexity results translate cleanly to mass. The negative case is weak: it rests only on the view that this would be a low-yield continuization for a programme focused on algorithmic complexity.
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.