d4-conf-ijcai-2020-0676 (d4-conf-ijcai-2020-0676)

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\)?

Let \(M\) be a nonempty set of \(m\) alternatives in a finite metric space \((X,d)\), with binary-rational distances. Each voter type \(t\) has a location \(x_t\in X\) and a strict ranking \(\sigma_t\) of \(M\) consistent with nondecreasing distance; equal distances may be ordered arbitrarily. Voter locations may coincide with alternatives.
A society is given by its support: the list \(T\) of its \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state any running times in \(m,\tau,L,k\).
Define \(SC_\mu(a)=\sum_{t\in T}\mu_t d(x_t,a)\) and \(OPT_\mu=\min_{a\in M}SC_\mu(a)>0\).
For a positive integer \(k\), sample \(k\) types independently from \(\mu\), with replacement, and let \(S\) be the set of their top-ranked alternatives, removing duplicates. All types participate in comparisons on \(S\).
Fix a linear priority order on \(M\) before sampling. Alternative \(a\) defeats \(b\) when the mass ranking \(a\) above \(b\) exceeds \(1/2\); at exactly \(1/2\), priority determines the victor. Choose a Copeland winner \(W\) on this completed tournament, using priority to break equal Copeland scores.

For every positive integer \(k\), is \(\sup_{\mathcal I:\,OPT_\mu>0}\bigl(\mathbb E[SC_\mu(W)^k]\bigr)^{1/k}/OPT_\mu\leq 11\), where \(\mathcal I\) ranges over all societies, metrics, compatible rankings, and fixed priority orders just specified?

For discrete societies with \(n\geq3\) voters, independent uniform sampling with replacement followed by full-participation Copeland has normalized \(k\)th-moment distortion at most \(11+8/(n-2)\). [Fain, Fan, and Munagala (2020)](https://arxiv.org/pdf/2004.13153)
No published result explicitly treating the precise mass formulation and tie convention above was located.

Result

Yes. For every positive integer \(k\), the stated mechanism satisfies
\[ \mathbb E[SC_\mu(W)^k]\le 11^k OPT_\mu^k. \]
Consequently, the requested supremum is at most \(11\).

We adapt the geometric strategy of [Fain, Fan, and Munagala, Theorem 2](https://arxiv.org/pdf/2004.13153), proving the needed facts directly for masses and the specified tie convention.

1. A ball containing a strict majority of the mass

Fix an instance. Choose \(a^\star\in M\) minimizing social cost, and write \(C=SC_\mu(a^\star)=OPT_\mu>0\). For a set of types \(A\subseteq T\), write \(\mu(A)=\sum_{t\in A}\mu_t\).

Define
\[ B=\{t\in T:d(x_t,a^\star)\le 2C\}. \]
We claim that \(\mu(B)>1/2\).

Indeed, put \(q=\mu(T\setminus B)\). If \(q=0\), the claim is immediate. Otherwise, every type outside \(B\) has distance strictly greater than \(2C\), and its mass is positive. Hence
\[ C=\sum_{t\in T}\mu_t d(x_t,a^\star) \ge \sum_{t\notin B}\mu_t d(x_t,a^\star) >2Cq. \]
Dividing by \(2C>0\) gives \(q<1/2\), as required.

For distinct alternatives, write \(u\to v\) when \(u\) defeats \(v\) in the completed tournament. Its supporting types
\[ A_{uv}=\{t\in T:u\text{ is ranked above }v\text{ in }\sigma_t\} \]
have mass at least \(1/2\), including when priority decides a tied comparison. Therefore
\[ \mu(B\cap A_{uv})\ge \mu(B)+\mu(A_{uv})-1>0. \]
Choose a type \(t\) in this intersection. Ranking compatibility gives \(d(x_t,u)\le d(x_t,v)\). The triangle inequality then yields
\[ d(a^\star,u) \le d(a^\star,x_t)+d(x_t,u) \le 2d(a^\star,x_t)+d(a^\star,v) \le 4C+d(a^\star,v). \tag{1} \]
Thus every tournament edge satisfies this inequality, regardless of how distance ties or majority ties were resolved.

2. Copeland winners reach every vertex within two edges

In any finite tournament, let \(w\) have maximum outdegree. We prove that every other vertex \(v\) is reached by either \(w\to v\) or \(w\to z\to v\).

Suppose neither possibility holds. Then \(v\to w\). Moreover, for every outneighbor \(z\) of \(w\), the absence of \(w\to z\to v\) forces \(v\to z\). Thus \(v\) defeats \(w\) and every vertex defeated by \(w\), so its outdegree is at least the outdegree of \(w\) plus one. This contradicts maximality.

The selected Copeland winner \(W\) has maximum outdegree in the tournament on \(S\). Hence this property applies to \(W\); priority among equal Copeland scores does not affect it.

3. A pointwise bound for each sample

Let \(t_1,\ldots,t_k\) be the independently sampled types, and define
\[ R_i=d(x_{t_i},a^\star), \qquad Y=\min_{1\le i\le k}R_i. \]
Choose an index \(j\) attaining this minimum, and let \(a\) be the top-ranked alternative of \(t_j\). Since \(a^\star\) is available and \(a\) is top-ranked,
\[ d(x_{t_j},a)\le d(x_{t_j},a^\star)=Y. \]
Consequently,
\[ d(a^\star,a)\le d(a^\star,x_{t_j})+d(x_{t_j},a)\le 2Y. \]
The alternative \(a\) belongs to \(S\), even after duplicates are removed.

By Section 2, there is a directed path from \(W\) to \(a\) of length at most two, allowing length zero when \(W=a\). Applying (1) along that path gives
\[ d(a^\star,W)\le 8C+d(a^\star,a)\le 8C+2Y. \]
Finally, averaging \(d(x_t,W)\le d(x_t,a^\star)+d(a^\star,W)\) over all types gives the pointwise bound
\[ SC_\mu(W)\le 9C+2Y. \tag{2} \]

4. The moment bound

The random variables \(R_1,\ldots,R_k\) are independent, nonnegative, and satisfy
\[ \mathbb E[R_i]=\sum_{t\in T}\mu_t d(x_t,a^\star)=C. \]
For every sample, each factor \(9C+2R_i\) is at least \(9C+2Y\). Using (2), we obtain
\[ SC_\mu(W)^k \le (9C+2Y)^k \le \prod_{i=1}^k(9C+2R_i). \]
Independence therefore implies
\[ \mathbb E[SC_\mu(W)^k] \le \prod_{i=1}^k\mathbb E[9C+2R_i] =(9C+2C)^k =(11C)^k. \]
Taking the \(k\)th root and dividing by \(C=OPT_\mu>0\) proves the claim for every admissible instance, and hence for their supremum.

⟨structured verdict parsed — rendered above⟩

Verdict

The proof is correct and resolves the stated question. Every nontrivial step is justified. No major or minor mathematical issues were found.

The argument applies directly to positive masses, compatible strict rankings, and the specified priority rules. It does not depend on transferring a discrete-society theorem to the mass setting.

Step-by-step verification

1. The ball contains strictly more than half the mass

An optimal alternative \(a^\star\) exists because \(M\) is finite and nonempty. The assumption \(C=OPT_\mu>0\) justifies the subsequent divisions.

The assertion \(\mu(B)>1/2\) is correct. If the complement has positive mass \(q\), every type in it has distance strictly greater than \(2C\). Since the support is finite and its masses are positive, the weighted sum over the complement is strictly greater than \(2Cq\). Thus
\[ C>2Cq, \]
which implies \(q<1/2\). If the complement is empty, the conclusion is immediate.

The strict inequality is essential: it ensures that the ball intersects the supporting types even for a comparison decided by an exact majority tie.

2. The edge inequality handles both kinds of ties correctly

For each directed edge \(u\to v\), its supporting set has mass at least \(1/2\). In a priority-decided comparison, the supporting mass is exactly \(1/2\); otherwise it exceeds \(1/2\).

Consequently,
\[ \mu(B\cap A_{uv})\geq \mu(B)+\mu(A_{uv})-1>0. \]
The selected type therefore exists.

Ranking compatibility gives the weak inequality
\[ d(x_t,u)\leq d(x_t,v), \]
including when distances are equal. The two triangle-inequality applications then establish precisely
\[ d(a^\star,u)\leq 4C+d(a^\star,v). \]
The constant and direction of this inequality are correct.

3. The tournament property is proved correctly

Suppose a maximum-outdegree vertex \(w\) cannot reach another vertex \(v\) within two directed edges. Tournament completeness implies \(v\to w\). For every outneighbor \(z\) of \(w\), it also implies \(v\to z\), since \(z\to v\) would provide the prohibited path.

The vertices counted here are distinct: \(v\) is not an outneighbor of \(w\), and \(w\) is not its own outneighbor. Hence \(v\) has at least one more outgoing edge than \(w\), contradicting maximality.

The selected Copeland winner has maximum outdegree in the completed tournament. Breaking equal scores by priority preserves this property. No external tournament theorem is being invoked without proof.

4. The sample-dependent bound is valid

Because \(k\geq1\), the minimum defining \(Y\) is attained. The sampled type’s top-ranked alternative \(a\) satisfies
\[ d(x_{t_j},a)\leq d(x_{t_j},a^\star)=Y, \]
so the triangle inequality yields
\[ d(a^\star,a)\leq2Y. \]

Removing duplicate nominated alternatives does not remove \(a\) from \(S\).

Applying the edge inequality along a path from \(W\) to \(a\) of length at most two gives
\[ d(a^\star,W)\leq8C+2Y. \]
The same bound remains valid for paths of length zero or one, since \(C>0\).

Averaging the triangle inequality over the normalized masses correctly gives
\[ SC_\mu(W)\leq C+d(a^\star,W)\leq9C+2Y. \]

5. The moment calculation is correct

The variables \(R_i\) are independent because the types are sampled independently with replacement. Each has mean \(C\).

Since \(R_i\geq Y\) and all factors are nonnegative,
\[ SC_\mu(W)^k\leq(9C+2Y)^k \leq\prod_{i=1}^k(9C+2R_i). \]
Independence applies to the factors on the right; no independence involving \(W\) or \(Y\) is assumed or needed.

All expectations are finite because the metric space and support are finite. Thus the factorization and calculation
\[ \mathbb E[SC_\mu(W)^k]\leq \prod_{i=1}^k(9C+2\mathbb E[R_i])=(11C)^k \]
are justified.

Taking roots and dividing by \(C>0\) gives the claimed bound. Since the instance and positive integer \(k\) were arbitrary, the supremum statement follows.

6. Scope and edge cases

The argument covers \(k=1\), a singleton nomination set, \(m=1\), repeated samples, coincident voter and alternative locations, arbitrary distance-tie rankings, and exact majority ties.

Binary-rational encoding creates no additional hypothesis needed by this proof. No running time is asserted, so the instruction concerning how to express running times is not violated.

Repair feedback: None required.

⟨structured verdict parsed — rendered above⟩