Answer: Yes. A deterministic polynomial-time mechanism achieves \(\alpha=39\) using exactly \(m\tau\) value queries, independently of any population obtained by clearing mass denominators.
Theorem 3.10 — class: algorithmic
Given a finite candidate set \(A\), committee size \(k\), rational \(\lambda\in(0,1]\), finite type set \(T\), rational masses \(\mu\), rankings \(\succ_t\), and oracle access to a hidden common metric \(d(t,a)\) consistent with the rankings and triangle inequalities, determine whether a randomized mechanism can output \(S\subseteq A\), \(|S|\le k\), using polynomially many type queries, such that with probability at least \(1-\delta\), \(\Phi_\lambda(\mu,d,S)\le\alpha\min_{|S'|\le k}\Phi_\lambda(\mu,d,S')\) for a universal constant \(\alpha\), with complexity independent of the represented population size.
A society is given by its support: a nonempty list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_t\mu_t=1\). Here \(\tau=|T|\) is the support size, not the number of possible rankings; each type represents colocated agents sharing its ranking and distances.
Let \(A\) contain \(m\) candidates, let \(2\le k\le m\), and let \(\lambda\in(0,1]\) and \(\delta\in(0,1)\) be binary rationals. Each supplied ranking \(\succ_t\) is a strict total order; equal distances may be ordered arbitrarily.
The hidden distances \(d:T\times A\to\mathbb{Q}_{\ge0}\) satisfy \(d(t,a)\le d(t,b)+d(u,b)+d(u,a)\) for all \(t,u,a,b\), and \(a\succ_t b\) implies \(d(t,a)\le d(t,b)\). An adaptive value query \((t,a)\) returns exactly \(d(t,a)\); the mechanism accesses distances only through these queries.
For nonempty \(S\subseteq A\), put \(c_t(S)=\min_{a\in S}d(t,a)\) and define the cost of the worst \(\lambda\) mass by \(\Phi_\lambda(\mu,d,S)=\max\{\sum_t x_t c_t(S):0\le x_t\le\mu_t,\ \sum_t x_t=\lambda\}\); mass at the cutoff may be split.
Let \(\mathrm{OPT}=\min_{S\subseteq A,\,1\le|S|\le k}\Phi_\lambda(\mu,d,S)\). Let \(L\) bound the public input's total bit length and the bit length of each oracle answer.
Does there exist a universal constant \(\alpha\ge1\) and a randomized mechanism that, for every such instance, uses time and total value queries polynomial in \(m,\tau,k,L,\log(1/\delta)\), independently of any population obtained by clearing mass denominators, and returns \(1\le|S|\le k\) with \(\Pr[\Phi_\lambda(\mu,d,S)\le\alpha\mathrm{OPT}]\ge1-\delta\); or is this guarantee impossible?
For finite unweighted societies with candidates equal to agents, a randomized mechanism achieves constant distortion for the sum of the \(\ell\) largest costs, with probability \(1-\delta\), using \(\widetilde O(k\log(1/\delta)\log(\min\{\ell,n/\ell\}))\) queries per agent (endpoint logarithms understood as at least one). [Source](https://ojs.aaai.org/index.php/AAAI/article/download/33539/35694).
The full version also establishes constant distortion for separate agent and candidate sets with \(O(k\log\ell\log(1/\delta))\) queries per agent, and treats integer multiplicities in a weighted reduction. No result for exactly the normalized rational-mass problem above was located. [Source](https://arxiv.org/html/2501.19148v2).
The guarantee exists. In fact, a deterministic mechanism suffices: it makes exactly \(m\tau\) value queries, runs in polynomial time in \(m,\tau,k,L\), and achieves approximation factor \(\alpha=39\).
The proof uses a known LP-relative approximation theorem for weighted metric \(k\)-median. All reductions below operate directly on binary-encoded rational masses.
Query every pair in \(T\times A\). Regard \(T\) and \(A\) as disjoint labeled vertex sets, and form the complete bipartite graph whose edge \(\{t,a\}\) has length \(d(t,a)\). Let \(D\) be its shortest-path pseudometric.
We claim that \(D(t,a)=d(t,a)\) for every supplied pair. The direct edge proves \(D(t,a)\le d(t,a)\). Conversely, any path from a type to a candidate has odd length. A three-edge segment \(t,b,u,a\) can be replaced by the edge \(\{t,a\}\) without increasing length, because the assumed inequality gives
\(d(t,a)\le d(t,b)+d(u,b)+d(u,a).\)
Repeated replacement shows that every path from \(t\) to \(a\) has length at least \(d(t,a)\). This proves the claim.
Consequently, we may use the triangle inequality for \(D\) while preserving every supplied type-to-candidate distance exactly. Distinct vertices may have distance zero; this will cause no difficulty.
We use the following standard consequence of Swamy’s LP-rounding theorem for matroid median, specialized to the uniform matroid and zero opening costs.
Weighted metric \(k\)-median theorem. Given a finite metric space \(R\), positive rational demands \(w_j\), and a positive integer \(k\), a deterministic polynomial-time algorithm returns a nonempty \(Q\subseteq R\), with \(|Q|\le k\), satisfying
\(\displaystyle \sum_{j\in R}w_jD(j,Q)\le 8\,\mathrm{LP}_{\mathrm{med}},\)
where
\(\displaystyle \mathrm{LP}_{\mathrm{med}} =\min\left\{\sum_{j,i\in R}w_jD(j,i)X_{ji}: \sum_iX_{ji}=1,\quad 0\le X_{ji}\le Y_i\le1,\quad \sum_iY_i\le k\right\}.\)
The factor is relative to the LP optimum, not merely the integral optimum. The source models clients with demands directly; its algorithm uses LPs and matroid optimization, without expanding demands into unit clients. Thus rational demands are handled in polynomial encoding length. See [Swamy, Sections 2–3 and Theorem 3.8](https://arxiv.org/html/1310.7834v4).
We will apply this theorem only to a genuine metric: the representatives constructed below have strictly positive pairwise distances. If \(k\ge |R|\), simply take \(Q=R\).
For every nonnegative cost vector \(c\), positivity of all masses and of \(\lambda\) implies
\(\Phi_\lambda(\mu,c)=0\quad\Longleftrightarrow\quad c_t=0\text{ for every }t.\)
Indeed, if \(c_t>0\), one can select mass \(\min\{\mu_t,\lambda\}>0\) from type \(t\), and fill the remaining selected mass from other types when necessary.
Consider the connected components of the graph consisting only of zero-length bipartite edges. Two vertices belong to the same component exactly when their \(D\)-distance is zero. Since \(D\) preserves the supplied distances, a candidate serves a type at zero cost exactly when they belong to the same such component.
Therefore, \(\mathrm{OPT}=0\) exactly when every component containing a type contains a candidate, and the number of components containing types is at most \(k\). This condition is computable in polynomial time. When it holds, return one candidate from each component containing types.
Henceforth suppose \(\mathrm{OPT}>0\). The encoding bound implies that every positive input mass, \(\lambda\), and every positive distance is at least \(2^{-L}\), while every distance is at most \(2^L\). Every feasible committee then has a type with positive cost, so
\(\displaystyle 2^{-2L}\le\mathrm{OPT}\le2^L.\)
For the lower bound, select mass \(\min\{\mu_t,\lambda\}\) from a positive-cost type; its cost is at least \(2^{-L}\).
Enumerate
\(\displaystyle B\in\{2^i:-2L\le i\le L\}.\)
There are \(3L+1\) guesses, and some guess satisfies
\(\mathrm{OPT}\le B<2\,\mathrm{OPT}.\)
The following construction is performed for every guess. Its approximation analysis uses a guess satisfying this inequality.
Fix \(B>0\), put \(r=B/\lambda\), and define
\(\displaystyle f_r(z)= \begin{cases} 0,&z\le r,\\ z,&z>r. \end{cases}\)
Solve the polynomial-size rational LP
\(\displaystyle V= \min\sum_{t\in T}\mu_t\sum_{a\in A}f_r(d(t,a))x_{ta},\)
subject to
\(\displaystyle \sum_{a\in A}x_{ta}=1,\qquad 0\le x_{ta}\le y_a\le1,\qquad \sum_{a\in A}y_a\le k.\)
Claim. If \(B\ge\mathrm{OPT}\), then \(V\le\mathrm{OPT}\).
Proof. Let \(S^*\) be an optimal committee and write \(c_t=c_t(S^*)\). Let \(H=\{t:c_t>r\}\).
If \(\sum_{t\in H}\mu_t\ge\lambda\), selecting \(\lambda\) mass entirely from \(H\) gives cost strictly greater than \(\lambda r=B\), contradicting optimality and \(B\ge\mathrm{OPT}\). Hence the mass of \(H\) is less than \(\lambda\).
We can therefore select all mass in \(H\) and fill the remainder elsewhere. Nonnegativity yields
\(\displaystyle \sum_{t\in H}\mu_tc_t\le\Phi_\lambda(\mu,d,S^*)=\mathrm{OPT}.\)
The integral LP solution corresponding to \(S^*\) has exactly the left-hand objective value. Thus \(V\le\mathrm{OPT}\). \(\square\)
For an optimal fractional solution, define the unweighted per-type LP contributions
\(\displaystyle C_t=\sum_{a\in A}f_r(d(t,a))x_{ta}.\)
Thus \(V=\sum_t\mu_tC_t\).
Process types in nondecreasing order of \(C_t\). When processing \(t\), assign it to an existing representative \(j\) with \(D(t,j)\le2r\), if one exists; otherwise make \(t\) a new representative.
Let \(R\) be the representatives, let \(\sigma(t)\) denote the representative assigned to \(t\), and put
\(\displaystyle w_j=\sum_{\sigma(t)=j}\mu_t.\)
The construction gives
\(\displaystyle D(t,\sigma(t))\le2r,\qquad C_{\sigma(t)}\le C_t,\qquad D(i,j)>2r\quad(i,j\in R,\ i\ne j).\)
In particular, \(D\) restricted to \(R\) is a genuine metric, and
\(\displaystyle V'=\sum_{j\in R}w_jC_j =\sum_{t\in T}\mu_tC_{\sigma(t)} \le V.\)
This consolidation is the rational-demand version of a threshold-clustering idea used for the unweighted objective; compare [Chakrabarty–Swamy, Appendix A](https://arxiv.org/pdf/1711.08715). The separate-candidate projection and lifting are established next.
For each candidate \(a\), choose a representative \(p(a)\in R\) minimizing \(d(j,a)\). Define
\(\displaystyle Y_i=\min\left\{1,\sum_{a:p(a)=i}y_a\right\},\qquad X_{ji}=\sum_{a:p(a)=i}x_{ja}.\)
These variables are feasible for the weighted metric \(k\)-median LP on \(R\):
Suppose \(p(a)=i\ne j\). By the choice of \(p(a)\) and the triangle inequality,
\(\displaystyle D(j,i)\le d(j,a)+d(i,a)\le2d(j,a).\)
Since distinct representatives have distance greater than \(2r\), this implies \(d(j,a)>r\). Therefore,
\(\displaystyle D(j,p(a))\le2f_r(d(j,a)).\)
The same inequality holds when \(p(a)=j\), because its left side is zero. Consequently,
\(\displaystyle \mathrm{LP}_{\mathrm{med}} \le\sum_{j,a}w_jD(j,p(a))x_{ja} \le2\sum_jw_jC_j =2V'.\)
Applying the weighted metric \(k\)-median theorem produces a nonempty \(Q\subseteq R\), with \(|Q|\le k\), such that
\(\displaystyle M:=\sum_{j\in R}w_jD(j,Q)\le16V'.\)
All theorem hypotheses have now been verified: \(R\) is a finite metric space, the demands are positive rationals, and the facility constraint is the uniform matroid of rank \(\min\{k,|R|\}\).
For every \(q\in Q\), choose a closest candidate \(a(q)\in A\). Return
\(\displaystyle S_B=\{a(q):q\in Q\}.\)
This is nonempty and has cardinality at most \(k\).
Write \(\delta_j=\min_{a\in A}d(j,a)\). Since \(z\le r+f_r(z)\) and \(\sum_ax_{ja}=1\),
\(\displaystyle \delta_j \le\sum_ax_{ja}d(j,a) \le r+C_j.\)
For any representative \(j\), choose a closest \(q\in Q\). Distance to the candidate set satisfies
\(\displaystyle \delta_q\le D(q,j)+\delta_j.\)
It follows that
\(\displaystyle d(j,a(q)) \le D(j,q)+\delta_q \le2D(j,Q)+\delta_j.\)
Now take any original type \(t\), and set \(j=\sigma(t)\). Another triangle inequality gives
\(\displaystyle c_t(S_B) \le D(t,j)+d(j,a(q)) \le3r+2D(j,Q)+C_j.\)
For any feasible selected masses \(z_t\), satisfying \(0\le z_t\le\mu_t\) and \(\sum_tz_t=\lambda\), we obtain
\(\displaystyle \sum_tz_tc_t(S_B) \le3r\lambda +2\sum_{j\in R}w_jD(j,Q) +\sum_{j\in R}w_jC_j.\)
Here each nonnegative representative term was bounded using
\(\sum_{\sigma(t)=j}z_t\le w_j\). Maximizing over the selected masses proves
\(\displaystyle \Phi_\lambda(\mu,d,S_B) \le3B+2M+V' \le3B+33V'.\)
For the guess satisfying \(\mathrm{OPT}\le B<2\mathrm{OPT}\), Sections 4–5 give \(V'\le V\le\mathrm{OPT}\). Hence
\(\displaystyle \Phi_\lambda(\mu,d,S_B) \le3B+33\,\mathrm{OPT} \le39\,\mathrm{OPT}.\)
After handling the zero-optimum case, construct \(S_B\) for every enumerated guess and return the committee with smallest exact \(\Phi_\lambda\).
Evaluation is polynomial: compute each type’s nearest selected candidate, sort the resulting costs in decreasing order, and accumulate mass until \(\lambda\) is reached, splitting the final type’s mass as necessary.
There are \(O(L)\) guesses. Shortest paths, both LPs, demand consolidation, candidate projection, and candidate lifting all use polynomially many operations on numbers of polynomial encoding length. Shortest-path lengths have polynomial bit length because a shortest path can be chosen simple. Rational LP optimal solutions likewise admit polynomial encoding length. The weighted \(k\)-median subroutine operates on at most \(\tau\) representatives with explicitly encoded rational demands.
The mechanism uses exactly \(m\tau\) value queries, all at the beginning. It never constructs a population by clearing denominators.
Its approximation guarantee holds deterministically, and therefore with probability at least \(1-\delta\) for every permitted \(\delta\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The argument establishes a deterministic polynomial-time mechanism with approximation factor \(\alpha=39\) and exactly \(m\tau\) value queries. I found no major or minor mathematical gaps.
The complete bipartite graph is connected because both vertex sets are nonempty, and all edge lengths are nonnegative. Its shortest-path distances therefore define a finite pseudometric.
Every path from a type to a candidate alternates between the two vertex sets and has an odd number of edges. The stated four-point inequality permits replacing any initial three-edge segment by its direct type-to-candidate edge without increasing length. Repeated replacement reduces the path to the direct edge. Thus every such path has length at least \(d(t,a)\), while the direct edge gives the reverse bound.
Consequently, \(D(t,a)=d(t,a)\) for every supplied pair. Subsequent uses of the triangle inequality are valid, including when distinct vertices have zero distance.
The cited source supports the required theorem. Section 2 gives the demand-weighted LP; Section 3 defines its \(\mathrm{OPT}\) as the fractional optimum; Theorem 3.8 bounds the returned integral cost by eight times that value. Its procedure uses deterministic clustering and optimization over integral or half-integral polytopes. Demands enter directly as numerical coefficients, so binary rational demands do not require expansion into unit clients. [Swamy, Sections 2–3 and Theorem 3.8](https://arxiv.org/html/1310.7834v4).
The specialization is appropriate: clients and facilities occupy the same finite metric space \(R\), opening costs are zero, and the facility matroid is uniform. Its rank constraints reduce to the displayed bounds \(0\le Y_i\le1\) and \(\sum_iY_i\le k\). Assignment sums may be made equal to one without increasing a nonnegative objective.
A feasible integral assignment requires a nonempty facility set. The explicit branch \(k\ge|R|\) also returns a nonempty set and has zero representative connection cost.
The equivalence between zero tail cost and all individual costs being zero is correct. If any type has positive cost, a positive amount \(\min\{\mu_t,\lambda\}\) of its mass can be selected. When additional mass is needed, the remaining available mass suffices because total mass is one and \(\lambda\le1\).
In a finite graph with nonnegative edge lengths, zero shortest-path distance is equivalent to connectivity through zero-length edges. Thus a candidate serves precisely the types in its zero-distance component at zero cost.
The component criterion is both necessary and sufficient. Each component containing types needs a candidate, and candidates from distinct components are required separately. Selecting one candidate from every such component gives a nonempty committee of size at most \(k\). Isolated types and components containing only candidates are handled correctly.
Under the stated binary encoding bound, positive masses, positive distances, and \(\lambda\) are at least \(2^{-L}\), and distances are at most \(2^L\).
Once zero optimum has been excluded, every feasible committee has a positive-cost type. Selecting the stated positive mass from that type establishes \(\mathrm{OPT}\ge2^{-2L}\). The upper bound \(\mathrm{OPT}\le2^L\) follows because selected mass is at most one and all costs are bounded by \(2^L\).
The enumerated powers of two therefore contain a guess satisfying \(\mathrm{OPT}\le B<2\mathrm{OPT}\), including when the optimum equals either endpoint or an enumerated power. There are \(3L+1\) guesses, each with polynomial encoding length.
The LP is feasible: any nonempty committee of size at most \(k\) supplies an integral feasible solution.
For a good guess, every type in \(H\) has cost strictly greater than \(r=B/\lambda\). If \(H\) had mass at least \(\lambda\), selecting \(\lambda\) mass from it would yield cost strictly greater than \(B\), contradicting \(\mathrm{OPT}\le B\).
Because \(H\) has mass less than \(\lambda\), all its mass can be included in a feasible selection. Nonnegative remaining costs imply \(\sum_{t\in H}\mu_tc_t\le\mathrm{OPT}\). This is exactly the threshold objective of the integral solution associated with \(S^*\), establishing \(V\le\mathrm{OPT}\).
Equality at the threshold is treated consistently: costs equal to \(r\) contribute zero to \(f_r\).
Processing in nondecreasing order of \(C_t\) gives \(C_{\sigma(t)}\le C_t\), including ties. The assignment rule gives \(D(t,\sigma(t))\le2r\), and creating a new representative only when no existing representative qualifies ensures distinct representatives have distance strictly greater than \(2r\).
Since \(r>0\), the restricted pseudometric is a genuine metric on \(R\). The set \(R\) is nonempty, every representative has positive rational weight, and consolidation preserves total mass.
The calculation \(V'=\sum_t\mu_tC_{\sigma(t)}\le V\) is valid.
A closest representative exists for every candidate because \(R\) is finite and nonempty. The projected assignments sum to one. Each \(X_{ji}\) is at most both its grouped opening mass and one, so \(X_{ji}\le Y_i\). Capping grouped opening mass at one cannot increase its total, establishing \(\sum_iY_i\le k\).
For \(p(a)=i\ne j\), the nearest-representative property and triangle inequality give \(D(j,i)\le2d(j,a)\). Separation gives \(D(j,i)>2r\), hence \(d(j,a)>r\). Therefore the claimed bound by \(2f_r(d(j,a))\) holds. When \(p(a)=j\), its left side is zero.
Summing with nonnegative assignment values and weights proves \(\mathrm{LP}_{\mathrm{med}}\le2V'\). The verified external theorem consequently yields \(M\le16V'\).
The inequality \(z\le r+f_r(z)\) holds in both branches of \(f_r\). Averaging against the representative’s assignment row gives \(\delta_j\le r+C_j\).
Distance to the candidate set satisfies the stated triangle bound \(\delta_q\le D(q,j)+\delta_j\). Combining it with the nearest selected representative and then the consolidation distance gives exactly \(c_t(S_B)\le3r+2D(\sigma(t),Q)+C_{\sigma(t)}\).
For any feasible selected masses, the mass assigned to representative \(j\) is at most \(w_j\). All representative terms being bounded are nonnegative. The resulting bound is therefore valid even when selected mass splits a type:
\(\Phi_\lambda(\mu,d,S_B)\le3B+2M+V'\le3B+33V'\).
For a good guess, \(V'\le\mathrm{OPT}\) and \(B<2\mathrm{OPT}\), yielding the claimed factor \(39\). The returned candidate set remains nonempty, and merging duplicate lifted candidates only decreases its cardinality.
Sorting costs and filling mass in decreasing cost order evaluates the specified fractional tail objective exactly. Choosing the least-cost committee over all guesses preserves the guarantee of the good guess.
The graph, LPs, representative instances, and guess list have polynomial size. Shortest paths, rational sums, threshold comparisons, and exact LP solutions have polynomial encoding length. The cited subroutine operates directly on the encoded demands. No step enumerates a population obtained by clearing denominators.
All oracle access consists of the initial \(m\tau\) queries. Ignoring rankings is permitted, and deterministic success implies the required probability bound for every allowed \(\delta\).
No repair or additional clarification is needed. This establishes polynomial-time constant approximation for the requested guarantee; it does not claim polynomial-time exact optimization.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.