Metric-Distortion Bounds Under Limited Information (d4-conf-sagt-2021-0012)

Given candidates \(C\), ranking types \(T\subseteq S_m\), masses \(\mu\in\Delta(T)\), and adaptive access to pairwise-majority queries determined by \(p_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t\), determine the smallest worst-case metric distortion achievable by a mechanism using at most \(m-1\) queries over all unit-mass metric realizations consistent with \(\mu\).

Let \(C\) contain \(m\geq2\) labeled candidates. A society is given by its support: a list \(T\) of \(\tau\) strict ranking types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau=|T|\) is the support size, not the number of possible rankings.
A realization \(R\) consists of an arbitrary metric space, distinct candidate points \(c_a\), and finite measures \(\nu_t\) of total mass \(\mu_t\), with \(a\succ_t b\Rightarrow d(x,c_a)\leq d(x,c_b)\) for \(\nu_t\)-almost every \(x\). Individuals sharing a ranking may occupy different points. Require finite social costs \(\mathrm{SC}_R(a)=\sum_t\int d(x,c_a)\,d\nu_t(x)\).
The oracle returns only the majority winner of a queried pair, determined by \(p_\mu(a,b)=\sum_{t:a\succ_t b}\mu_t\); majority ties favor the smaller candidate label.
An admissible deterministic mechanism \(A\) is a binary decision tree of depth at most \(m-1\), with candidate-pair queries at internal nodes and a single candidate at each leaf. During execution it sees only candidate labels and oracle answers. Write \(A(\mu)\) for its output against this oracle.
Define the instance-specific optimum \(D^*(\mu)=\min_A\sup_{R\text{ consistent with }\mu}\mathrm{SC}_R(A(\mu))/\min_{a\in C}\mathrm{SC}_R(a)\), with \(0/0=1\) and positive divided by zero equal to \(+\infty\). The minimization is performed separately for each input society.

Given the society and a binary-rational threshold \(B\geq1\), is deciding whether \(D^*(\mu)\leq B\) in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it NP-hard, where \(L\) is the total input bit length?

For finite societies, a polynomial-time deterministic balanced knockout mechanism uses \(m-1\) majority queries and guarantees distortion at most \(2\lceil\log_2m\rceil+1\); fewer queries cannot guarantee bounded distortion uniformly over societies. [Source](https://jair.org/index.php/jair/article/download/13338/26830/31347)
Later elicitation results concern individual-voter comparisons rather than aggregate-majority queries. [Source](https://www.ijcai.org/proceedings/2024/0309.pdf) No verified classification was located for the exact rational-mass decision problem stated above.

Polynomial-time solvability

The decision problem as stated belongs to \(\mathrm{P}\). The proof uses at most \(\,m(m-1)\,\) rational linear feasibility tests, each of polynomial size in \(\,m,\tau,L\,\).

The instance-specific minimization permits constant decision trees. This removes the query restriction from the optimization, but leaves a substantive problem: checking a candidate’s worst-case distortion over all consistent metric realizations. We solve that problem exactly.

1. Reduction to choosing a candidate

For each candidate \(\,a\in C\,\), define

\(\displaystyle W_a(\mu)=\sup_{R\text{ consistent with }\mu}\frac{\mathrm{SC}_R(a)}{\min_{b\in C}\mathrm{SC}_R(b)}.\)

For a fixed society, every admissible mechanism outputs a fixed candidate: its oracle answers depend only on the society, not on the realization. Conversely, the depth-zero tree whose sole leaf is labeled \(\,a\,\) is admissible and outputs \(\,a\,\). Consequently,

\(\displaystyle D^*(\mu)=\min_{a\in C}W_a(\mu).\)

The constant tree has its output label hardcoded; it does not inspect the society during execution.

For any realization and threshold \(\,B\geq1\,\),

\(\displaystyle \frac{\mathrm{SC}_R(a)}{\min_{c\in C}\mathrm{SC}_R(c)}\leq B \quad\Longleftrightarrow\quad \mathrm{SC}_R(a)\leq B\,\mathrm{SC}_R(b)\text{ for every }b\in C.\)

To verify this equivalence, if the minimum cost is positive, multiply by that minimum. If the minimum is zero, both conditions hold exactly when \(\,\mathrm{SC}_R(a)=0\,\): the ratio is then defined to be one. Otherwise, comparison with a zero-cost candidate violates the right-hand condition.

Thus candidate \(\,a\,\) fails the threshold precisely when some candidate \(\,b\,\) and consistent realization satisfy

\(\displaystyle \mathrm{SC}_R(a)-B\,\mathrm{SC}_R(b)>0.\)

2. A polynomial-size cone of distance data

Introduce variables

\(\displaystyle D_{ab}=D_{ba}\quad(a\neq b),\qquad r_{ta}\quad(t\in T,\ a\in C),\)

and set \(\,D_{aa}=0\,\). Interpret \(\,D_{ab}\,\) as a candidate distance and \(\,r_{ta}\,\) as type \(\,t\,\)’s mean distance to candidate \(\,a\,\).

Let \(\,\mathcal K\,\) be the cone defined by the following linear constraints:

• Nonnegativity: \(\,D_{ab}\geq0\,\) and \(\,r_{ta}\geq0\,\).
• Candidate triangle inequalities: \(\,D_{ab}\leq D_{ac}+D_{cb}\,\) for distinct candidates \(\,a,b,c\,\).
• Distance-difference inequalities: \(\,-D_{ab}\leq r_{ta}-r_{tb}\leq D_{ab}\,\).
• Distance-sum inequalities: \(\,D_{ab}\leq r_{ta}+r_{tb}\,\).
• Ranking consistency: \(\,r_{ta}\leq r_{tb}\,\) whenever \(\,a\succ_t b\,\).

The third and fourth constraints apply to every type and pair of distinct candidates. Define the linear cost functional

\(\displaystyle \Phi_a(r)=\sum_{t\in T}\mu_t r_{ta}.\)

Every realization supplies feasible cone data

Given a consistent realization, set

\(\displaystyle D_{ab}=d(c_a,c_b),\qquad r_{ta}=\frac{1}{\mu_t}\int d(x,c_a)\,d\nu_t(x).\)

These values are finite. Indeed, finite social costs and nonnegative integrands imply that every type’s integral is finite, and \(\,\mu_t>0\,\).

Candidate triangle inequalities hold in the metric. Integrating

\(\displaystyle d(x,c_a)\leq d(x,c_b)+D_{ab}\)

and its reverse gives the distance-difference inequalities. Integrating

\(\displaystyle D_{ab}\leq d(x,c_a)+d(x,c_b)\)

gives the distance-sum inequalities. Ranking consistency follows by integrating the required almost-everywhere comparisons.

Therefore \(\,(D,r)\in\mathcal K\,\), and

\(\displaystyle \Phi_a(r)=\mathrm{SC}_R(a).\)

This argument allows individuals of the same type to occupy arbitrary different points.

3. Positive feasible data have finite metric realizations

We next prove the converse needed for detecting strict violations.

Lemma. Suppose \(\,(D,r)\in\mathcal K\,\), all off-diagonal candidate distances are positive, and all \(\,r_{ta}\,\) are positive. Then there is a finite consistent realization with social costs \(\,\Phi_a(r)\,\).

Proof. Construct an undirected weighted graph with a vertex \(\,c_a\,\) for every candidate and a vertex \(\,v_t\,\) for every type. Include:

• an edge \(\,c_ac_b\,\) of length \(\,D_{ab}\,\) for every distinct candidate pair;
• an edge \(\,v_tc_a\,\) of length \(\,r_{ta}\,\) for every type and candidate.

Use the shortest-path distance on this graph. The graph is finite and connected, and every edge length is positive, so this distance is a genuine metric on its vertices.

We verify that shortest paths preserve the prescribed distances.

For a path between two candidates, every internal type vertex occurs between candidate vertices. Replace each segment

\(\displaystyle c_i,\ v_t,\ c_j\)

by the candidate edge of length \(\,D_{ij}\,\), or delete the segment when \(\,i=j\,\). This does not increase length because

\(\displaystyle D_{ij}\leq r_{ti}+r_{tj}.\)

The remaining candidate-only walk has length at least the direct candidate distance, by repeated application of the candidate triangle inequalities. Since the direct edge exists,

\(\displaystyle d(c_a,c_b)=D_{ab}.\)

Now consider a shortest path from \(\,v_t\,\) to \(\,c_a\,\). Positive edge lengths permit choosing it without repeated vertices. Its first edge goes to some candidate \(\,c_b\,\). Eliminate all subsequent type vertices as above. The remaining portion has length at least \(\,D_{ba}\,\). Hence the original path has length at least

\(\displaystyle r_{tb}+D_{ba}\geq r_{ta},\)

where the last inequality is a distance-difference constraint. The direct edge gives the reverse inequality, so

\(\displaystyle d(v_t,c_a)=r_{ta}.\)

Finally, place measure \(\,\nu_t=\mu_t\delta_{v_t}\,\) at each type vertex. The ranking inequalities hold at that vertex, and

\(\displaystyle \mathrm{SC}_R(a)=\sum_t\mu_t d(v_t,c_a)=\Phi_a(r).\)

All costs are finite, and all candidate points are distinct. This proves the lemma. \(\square\)

4. Exact detection of strict violations

For distinct candidates \(\,a,b\,\), form the rational linear feasibility system

\(\displaystyle (D,r)\in\mathcal K,\qquad \Phi_a(r)-B\Phi_b(r)\geq1.\)

Proposition. This system is feasible if and only if some consistent realization satisfies

\(\displaystyle \mathrm{SC}_R(a)>B\,\mathrm{SC}_R(b).\)

Proof, realization to feasibility. A violating realization gives cone data with

\(\displaystyle \delta=\Phi_a(r)-B\Phi_b(r)>0.\)

All defining constraints of \(\,\mathcal K\,\) are homogeneous. Dividing every variable by \(\,\delta\,\) therefore preserves cone feasibility and makes the cost difference equal to one.

Proof, feasibility to realization. Take feasible data and set

\(\displaystyle \varepsilon=\frac{1}{2B},\qquad D^\varepsilon_{ab}=D_{ab}+\varepsilon\ (a\neq b),\qquad r^\varepsilon_{ta}=r_{ta}+\varepsilon.\)

Keep \(\,D^\varepsilon_{aa}=0\,\). These perturbed data remain in \(\,\mathcal K\,\):

• candidate triangle inequalities gain \(\,\varepsilon\,\) on the left and \(\,2\varepsilon\,\) on the right;
• distance differences are unchanged, while their permitted bounds increase;
• distance-sum inequalities gain \(\,\varepsilon\,\) on the left and \(\,2\varepsilon\,\) on the right;
• ranking comparisons receive the same addition on both sides.

Every required edge length is now positive. Moreover, because \(\,\sum_t\mu_t=1\,\),

\(\displaystyle \Phi_c(r^\varepsilon)=\Phi_c(r)+\varepsilon\)

for every candidate \(\,c\,\). Consequently,

\(\displaystyle \Phi_a(r^\varepsilon)-B\Phi_b(r^\varepsilon) \geq 1+(1-B)\varepsilon =\frac{B+1}{2B}>0. \)

The lemma supplies a finite consistent metric realization with exactly these perturbed social costs. It strictly violates the threshold comparison. \(\square\)

The rescaling and perturbation are essential: they allow ordinary non-strict rational linear feasibility tests while respecting distinct candidate points. They also avoid any special treatment of zero-cost denominators.

5. Algorithm and bit complexity

For each candidate \(\,a\,\), test the feasibility systems in Section 4 for every \(\,b\neq a\,\). Accept exactly when some candidate has all its systems infeasible.

By the proposition, such a candidate satisfies

\(\displaystyle \mathrm{SC}_R(a)\leq B\,\mathrm{SC}_R(b)\)

for every candidate and every consistent realization. Section 1 then proves that the algorithm accepts exactly when \(\,D^*(\mu)\leq B\,\).

Each system has

\(\displaystyle N=\binom{m}{2}+\tau m\)

variables and \(\,O(m^3+\tau m^2)\,\) constraints. Its coefficients are rational: the cone uses only small integer coefficients, while the added cost constraint uses \(\,\mu_t\,\) and \(\,B\mu_t\,\). Multiplying the input rationals increases their encoding lengths by at most the sum of their encoding lengths. Thus every system has total encoding length polynomial in \(\,m,\tau,L\,\).

Rational linear feasibility is decidable exactly in time polynomial in its encoding length, by the polynomial-time linear programming theorem. Its hypotheses apply here because every system is finite and explicitly represented with rational coefficients. See [Khachiyan, *A polynomial algorithm in linear programming*](https://www.mathnet.ru/eng/dan42319).

There are at most \(\,m(m-1)\,\) systems. Hence the entire algorithm runs in time polynomial in \(\,m,\tau,L\,\).

6. Scope of the conclusion

This resolves the stated instance-specific decision problem. The algorithm uses the explicitly supplied ranking support and masses to select a candidate, then that candidate can be implemented by a constant admissible tree.

This does not contradict the supplied uniform query lower bound: choosing a tree separately for each society and requiring one fixed tree to guarantee bounded distortion over all societies have different quantifiers.

⟨structured verdict parsed — rendered above⟩

The claimed polynomial-time classification is correct. The argument resolves the instance-specific decision problem as stated. I found no major or minor mathematical issues.

• The reduction to choosing a candidate is valid. For a fixed society, the majority oracle is fixed independently of the realization, so each deterministic mechanism outputs one fixed candidate. Every candidate is attainable by an admissible depth-zero tree. Thus the equality \(D^*(\mu)=\min_a W_a(\mu)\) respects the task’s quantifiers. Hardcoding a candidate does not violate the execution restrictions.

• The threshold comparison handles zero denominators correctly. When the minimum social cost is positive, the stated equivalence follows by multiplication. When it is zero, the convention \(0/0=1\), together with \(B\geq1\), gives precisely the condition described in the output. The omitted comparison with \(b=a\) is automatic because costs are nonnegative and \(B\geq1\). Consequently, a candidate fails exactly when some realization and some distinct candidate give a strict cost violation. Taking a supremum introduces no additional attainment requirement.

• Every realization produces feasible cone data. Positive type masses and finite social costs ensure that all type means are finite. Each distance constraint follows from the stated pointwise metric inequality after integration and division by the type mass. Almost-everywhere ranking consistency suffices for the integrated ranking inequalities. No assumption that voters of a type share a point is used.

• The finite metric realization lemma is correct. Positive graph edge lengths ensure a genuine shortest-path metric. Eliminating internal type vertices cannot increase a candidate-to-candidate path’s length, by the distance-sum constraints. Candidate triangle inequalities then prevent any shortening of a prescribed candidate distance. For a type-to-candidate shortest path, the distance-difference constraint supplies the required lower bound after the same elimination. The argument also covers the case where the first candidate is the destination, using \(D_{aa}=0\). The atomic measures have the required masses, satisfy the rankings, and reproduce the prescribed costs.

• The feasibility test detects strict violations exactly. Homogeneity justifies rescaling a positive violation to one. Conversely, the prescribed perturbation preserves every cone constraint and makes every graph edge positive. The critical calculation is correct:

\[ 1+(1-B)\frac{1}{2B}=\frac{B+1}{2B}>0. \]
It applies throughout the required range, including \(B=1\). Thus allowing zero distances in the feasibility system creates no false positives.

• The algorithm and bit complexity are valid. The variable and constraint counts are correct. Products \(B\mu_t\) have polynomial encoding length, and no strict inequalities remain in the systems submitted to linear feasibility. The invoked theorem—exact feasibility of explicitly represented rational linear systems in polynomial time—has the required hypotheses here; boundedness and full dimensionality are unnecessary. The cited [Khachiyan publication](https://www.mathnet.ru/eng/dan42319) is correctly identified. Testing at most \(m(m-1)\) such systems therefore gives the claimed polynomial running time.

• The scope statement is consistent. Selecting a mechanism separately for each society differs from requiring one mechanism to guarantee bounded distortion uniformly over societies. The supplied query lower bound therefore does not contradict the conclusion.

No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩