Answer: Such a mechanism exists in \(2^{O(k)}\operatorname{poly}(m,\tau,L,\log N)\) time. It is exactly strategyproof in expectation and satisfies \(D_F(\mu,x_t;x_t)=\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\) for every truthful type.
Lemma 10 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism 3 is strategyproof. It achieves approxima- tion ratios n 2 for the social cost and 2 for the maximum cost.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a bounded rational interval \(B\), \(k\) facilities, a population scale \(N\), and integer capacities \(c_1,\ldots,c_k\) summing to \(N\), represent the agents by a distribution \(\mu\) over reported ideal locations, where each mass is a multiple of \(1/N\). Can one construct a randomized mechanism running in time \(2^{O(k)}\operatorname{poly}(\tau,L,\log N)\) that outputs facility locations and a feasible integral assignment, is exactly strategyproof when one agent changes their report (moving mass \(1/N\)), and gives every agent expected distance at most \(2\,\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\)? Here \(\kappa_i=c_i/N\), and \(\mathrm{OPT}^{\max}_\infty\) is the minimum essential maximum distance when facilities lie in \(B\), assigned mass may be split among them, and facility \(i\) receives at most \(\kappa_i\) mass.
Let \(B=[b_l,b_r]\) have rational endpoints with \(b_l\le b_r\), and let \(k\ge2\) facilities have positive integer capacities \(c_i\) with \(\sum_i c_i=N\). Facilities may coincide; there are no payments.
A society is given by its support: distinct rational reported locations \(x_t\in B\) with positive binary-rational masses \(p_t\), where \(\sum_t p_t=1\) and \(Np_t\in\mathbb Z_{>0}\). The support size is \(\tau\), not the number of possible types. Write \(m=k\) and let \(L\) be the total input bit length, including the binary encodings of \(N\) and capacities.
A randomized mechanism outputs locations \(f_i\in B\) and a succinct integral assignment: binary-encoded counts \(a_{ti}\in\mathbb Z_{\ge0}\) with \(\sum_i a_{ti}=Np_t\) and \(\sum_t a_{ti}=c_i\), together with an implicit uniform allocation of agents sharing each report to these slots.
For a true location \(x\) and report \(r\) present in a society \(\nu\), let \(D_F(\nu,r;x)\) denote the agent's expected distance to its assigned facility, including the uniform allocation lottery. Exact strategyproofness in expectation means \(D_F(\mu,x;x)\le D_F(\mu',r;x)\) for every support location \(x\) and rational \(r\in B\), where \(\mu'=\mu-N^{-1}\delta_x+N^{-1}\delta_r\); other reports remain fixed.
Set \(\kappa_i=c_i/N\). Define \(\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\) as the minimum \(R\ge0\) over locations \(f_i\in B\) and real masses \(z_{ti}\ge0\) satisfying \(\sum_i z_{ti}=p_t\), \(\sum_t z_{ti}\le\kappa_i\), and \(z_{ti}>0\Rightarrow |x_t-f_i|\le R\).
Does an exactly strategyproof randomized mechanism exist that runs in \(2^{O(k)}\operatorname{poly}(m,\tau,L,\log N)\) time and guarantees \(D_F(\mu,x_t;x_t)\le2\,\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\) for every type on every input, or is this guarantee unattainable within that time bound?
For explicitly listed agents with arbitrary positive capacities summing to their number, a randomized strategyproof mechanism with maximum-cost approximation ratio \(2\) is known. [Verified result](https://journals.sagepub.com/doi/10.3233/FAIA250954)
No result settling this precise support-encoded mechanism question was located.
Such a mechanism exists. Its running time is \(2^{O(k)}\operatorname{poly}(m,\tau,L,\log N)\). In fact, it satisfies the stronger identity
\(D_F(\mu,x_t;x_t)=\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\)
for every truthful type.
The construction uses the minimum-covering-length and endpoint-lottery approach of [Mechanism 3 in the cited paper](https://journals.sagepub.com/doi/10.3233/FAIA250954). Below, the implementation on binary-encoded multiplicities and the strategyproofness argument are proved directly.
Sort the support so that \(x_1<\cdots<x_\tau\), and define the integer multiplicities \(n_t=Np_t\). Let \(X_1\le\cdots\le X_N\) denote the conceptual expanded list, containing \(n_t\) copies of \(x_t\). The algorithm will never construct this list.
For a permutation \(\pi\) of the facilities, partition this list into consecutive blocks of sizes \(c_{\pi_1},\ldots,c_{\pi_k}\). Define \(D\) as the minimum, over all such permutations, of the largest block diameter.
We first prove
\(\mathrm{OPT}^{\max}_\infty(\mu,\kappa)=D/2\).
Fractional feasibility implies integral feasibility at the same radius. Suppose locations \(f_i\) and masses \(z_{ti}\) are feasible at radius \(R\). Put \(w_{ti}=Nz_{ti}\). Their row sums are the integers \(n_t\). Their column sums are exactly \(c_i\): each is at most \(c_i\), while the total of both the row sums and the capacities is \(N\).
We can make every \(w_{ti}\) integral while preserving its margins and permitted edges. Consider the bipartite graph of nonintegral entries. Every vertex incident to an edge has degree at least two, since an integer margin cannot have exactly one nonintegral summand. Consequently, if any nonintegral entries remain, this graph contains a cycle.
Alternately increase and decrease entries around that cycle. Choose the smallest positive change that makes one entry reach its floor or ceiling, keeping every changed entry between its previous floor and ceiling. This preserves all margins, preserves nonnegativity, and decreases the number of nonintegral entries. Repetition terminates with an integral matrix supported only on permitted edges.
Thus the conceptual agents admit an integral assignment with capacities exactly \(c_i\) and distances at most \(R\).
Such an assignment can be made consecutive. Order the facilities by their locations, breaking ties arbitrarily. Suppose two adjacent agents have locations \(y\le z\), but their assigned facilities form an inversion: \(y\) is assigned to a center \(\beta\), and \(z\) to a center \(\alpha\le\beta\).
Swapping their assignments preserves feasibility. Indeed,
\(y\ge\beta-R\ge\alpha-R\) and \(y\le z\le\alpha+R\), so \(|y-\alpha|\le R\). Likewise,
\(z\ge y\ge\beta-R\) and \(z\le\alpha+R\le\beta+R\), so \(|z-\beta|\le R\).
Swapping adjacent inversions decreases the inversion count. Eventually the assigned facility labels are nondecreasing, giving consecutive blocks with the prescribed capacities. Each block has diameter at most \(2R\). Hence \(D\le2R\) for every fractionally feasible radius \(R\).
Conversely, take a consecutive partition attaining \(D\). Place each facility at its block’s midpoint and assign the block to it. These locations belong to \(B\), and all distances are at most \(D/2\). Dividing the integral assignment counts by \(N\) gives a feasible fractional solution. This proves the claimed equality.
We will also use the following consequence: every integral assignment whose group diameters are at most \(H\) satisfies \(D\le H\). Place facilities at the group midpoints and apply the preceding argument with radius \(H/2\).
Let \(q_0=0\) and \(q_t=\sum_{h=1}^t n_h\). A conceptual rank query \(X_j\) is answered by finding the smallest \(t\) with \(q_t\ge j\), using binary search.
For a subset \(S\) of facilities, write \(C(S)=\sum_{i\in S}c_i\). Let \(H(S)\) be the smallest possible largest block diameter when the facilities in \(S\), in some order, serve the first \(C(S)\) conceptual agents.
Set \(H(\varnothing)=0\). For nonempty \(S\), use the recurrence
\(H(S)=\min_{i\in S}\max\left\{H(S\setminus\{i\}),\,X_{C(S)}-X_{C(S)-c_i+1}\right\}.\)
To justify it, if \(i\) is last, its block consists exactly of ranks \(C(S)-c_i+1,\ldots,C(S)\). The remaining blocks partition the preceding prefix using \(S\setminus\{i\}\). Conversely, every partition has some last facility, so the recurrence considers every possibility.
Therefore \(D=H(\{1,\ldots,k\})\). Store a minimizing last facility at each state, with deterministic tie breaking, to recover an optimal order.
For facility \(i\), let its recovered block be ranks \(s_i+1,\ldots,s_i+c_i\). Its assignment counts are
\(a_{ti}=\max\left\{0,\,\min(q_t,s_i+c_i)-\max(q_{t-1},s_i)\right\}.\)
This is the size of the intersection between the type’s rank interval and the facility’s block. Consequently, the required row and column sums hold exactly.
Let \(\ell_i\) and \(r_i\) be the smallest and largest reports in facility \(i\)’s recovered block. Thus \(r_i-\ell_i\le D\).
Define
\(u_i=\min\{\ell_i,b_r-D\},\qquad v_i=u_i+D.\)
The interval \(I_i=[u_i,v_i]\) lies in \(B\) and contains the entire block:
Place facility \(i\) at \(u_i\) or \(v_i\), each with probability \(1/2\), using independent fair coins. Output the counts \(a_{ti}\), with the stipulated implicit uniform allocation among agents sharing a report, independently of the location coins.
For any interval \(I=[u,u+d]\) and any true location \(x\), the endpoint lottery has expected distance
\(\frac{|x-u|+|x-(u+d)|}{2}=\frac d2+\operatorname{dist}(x,I).\)
This follows by considering \(x<u\), \(u\le x\le u+d\), and \(x>u+d\).
Every truthful report assigned to facility \(i\) belongs to \(I_i\). Therefore its expected distance, conditional on that assignment, is \(D/2\). Averaging over the uniform allocation gives
\(D_F(\mu,x_t;x_t)=D/2=\mathrm{OPT}^{\max}_\infty(\mu,\kappa).\)
Moreover, every realized truthful distance is at most \(D=2\,\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\).
Fix a truthful profile \(\mu\), an agent at \(x\), and a deviation to a rational report \(r\). The case \(r=x\) is immediate, so assume \(r\ne x\).
Let \(D\) be the truthful minimum block diameter, and let \(D'\) be the corresponding value for the deviated profile \(\mu'\).
Consider any facility \(i\) that receives a positive number of slots for report \(r\) under the mechanism on \(\mu'\). Its endpoint interval \(I'_i\) has length \(D'\). Write \(\delta_i=\operatorname{dist}(x,I'_i)\).
We claim that \(D\le D'+\delta_i\).
To prove this, take the deviated integral assignment. Replace one report-\(r\) slot at facility \(i\) by an agent at \(x\), leaving every other assignment unchanged. This restores exactly the multiplicities of \(\mu\), and preserves every facility’s capacity.
Every report in every other group lies in its interval of length \(D'\). The modified group at facility \(i\) lies in the smallest interval containing \(I'_i\) and \(x\), whose length is \(D'+\delta_i\). Thus this is an integral assignment for \(\mu\) with every group diameter at most \(D'+\delta_i\). The consequence proved in Section 1 yields the claim.
Conditional on receiving facility \(i\) after the deviation, the agent’s expected true distance is \(D'/2+\delta_i\). This is at least \(D/2\):
The uniform allocation assigns the deviating agent only to facilities with positive report-\(r\) counts. Averaging these conditional inequalities therefore gives
\(D_F(\mu',r;x)\ge D/2=D_F(\mu,x;x).\)
This proves exact strategyproofness in expectation, including deviations that merge with an existing report or remove the original support point.
There are \(2^k\) dynamic-programming states and at most \(k\) transitions per state. Each transition uses two conceptual rank queries, answered in \(O(\log(\tau+1))\) comparisons on cumulative multiplicities.
All cumulative multiplicities and assignment counts have \(O(\log N)\) bits. Dynamic-programming values are support-coordinate differences, so their rational representations have bit length polynomial in \(L\). Comparisons, interval construction, and output locations likewise require polynomial bit complexity.
Sorting the support and producing the \(k\tau\) counts also take polynomial time. The location lottery uses exactly \(k\) fair bits; the allocation remains implicit as required.
The total running time is therefore \(2^{O(k)}\operatorname{poly}(m,\tau,L,\log N)\), with no expansion into \(N\) explicitly listed agents.
⟨structured verdict parsed — rendered above⟩
The claimed mechanism is proved. The argument establishes exact strategyproofness in expectation, the stated running time, and the stronger identity \(D_F(\mu,x_t;x_t)=\mathrm{OPT}^{\max}_\infty(\mu,\kappa)\). I found no major or minor gaps.
The complexity result is a parameterized running-time guarantee. Since \(k\) is part of the input, the factor \(2^{O(k)}\) does not establish polynomial time in the unrestricted total input size.
Fractional margins. Multiplying the feasible masses by \(N\) gives integer row margins \(n_t\). The column margins must equal \(c_i\): their sum is \(N\), each is bounded above by \(c_i\), and \(\sum_i c_i=N\). This deduction is valid.
Integral rounding. In the graph of nonintegral entries, a vertex cannot have exactly one incident edge, because its margin and all remaining summands are integers. A nonempty finite graph with every nonisolated vertex of degree at least two contains a cycle. Bipartiteness makes that cycle even, so the alternating adjustments preserve every margin.
The specified adjustment keeps each changed entry within its previous floor and ceiling, makes at least one entry integral, and introduces no new nonintegral entries. It also preserves nonnegativity and permitted edges. Thus termination with an integral assignment is justified.
Consecutive assignments. Both displayed bounds for swapping an adjacent inversion are correct. They establish that the exchanged assignments retain distance at most \(R\). Facility labels are understood in the total order specified by sorting centers and breaking ties. Adjacent inversion swaps therefore terminate in nondecreasing label order. Exact capacities then give consecutive blocks of the required sizes, including when facilities or agent locations coincide.
Each resulting block has diameter at most \(2R\), proving \(D\le 2R\). Conversely, midpoint placement for a partition attaining \(D\) gives feasible radius \(D/2\), with centers in \(B\). There are finitely many facility permutations, so the minimizing partition exists. The equality \(\mathrm{OPT}^{\max}_\infty(\mu,\kappa)=D/2\) follows.
Group-diameter consequence. The stated consequence for any integral assignment with group diameters at most \(H\) follows from its midpoint placement and the preceding characterization. Positive capacities ensure that every group is nonempty. This consequence is available for the later strategyproofness argument.
The recurrence correctly conditions on the last facility. Its block occupies exactly ranks \(C(S)-c_i+1,\ldots,C(S)\), and the preceding blocks use precisely \(S\setminus\{i\}\). Conversely, every permissible order has a last facility, so no partition is omitted.
All queried ranks are valid: capacities are positive, and for nonempty \(S\), \(1\le C(S)-c_i+1\le C(S)\le N\). The empty-state value \(0\) is appropriate because block diameters are nonnegative.
The assignment-count formula correctly computes the intersection of the integer rank intervals \(q_{t-1}+1,\ldots,q_t\) and \(s_i+1,\ldots,s_i+c_i\). Since recovered blocks partition all ranks, the formula yields nonnegative integer counts with the required row and column sums.
The interval construction is valid. Every block diameter is at most the total span of \(B\), so \(0\le D\le b_r-b_l\). Consequently \(u_i\ge b_l\), \(v_i\le b_r\), and the stated case distinction proves that \(I_i\) contains the entire assigned block.
The endpoint-lottery identity is correct for locations inside, to the left of, and to the right of the interval. It also holds when the interval length is zero.
Every truthful type lies in every interval corresponding to one of its assigned slots. Its conditional expected distance is therefore \(D/2\) for every possible assigned facility. Uniform allocation preserves this value after averaging. The stronger expected-distance identity and the bound on every realized truthful distance both follow.
This is the central argument, and it is valid.
For each facility with a positive report-\(r\) count in the deviated profile, replacing one such slot by a report at \(x\) restores exactly the truthful multiplicities. It preserves capacities, including when \(r\) already existed or the deviation removed the original support point.
All unchanged groups have diameter at most \(D'\). The modified group is contained in the interval spanning \(I'_i\) and \(x\), whose length is \(D'+\delta_i\). Applying the already established group-diameter consequence therefore yields \(D\le D'+\delta_i\).
The conditional expected true distance is \(D'/2+\delta_i\). Both cases in the comparison with \(D/2\) are correct. In particular, when \(D'<D\), the established bound gives \(\delta_i\ge D-D'\), hence \(D'/2+\delta_i\ge D-D'/2\ge D/2\).
Under uniform allocation, the deviating agent can receive only facilities with positive report-\(r\) counts. Each such conditional expectation satisfies the required inequality, so averaging proves exact strategyproofness in expectation. The argument covers every rational deviation in \(B\), without requiring stable tie breaking between the two profiles.
The dynamic program has \(2^k\) states and at most \(k\) transitions per state. Rank queries use the compressed cumulative multiplicities, so no operation requires expanding the \(N\) agents.
Cumulative counts, subset capacities, and assignment counts have \(O(\log N)\) bits. Coordinate differences and constructed endpoints have polynomial bit length in \(L\). The described arithmetic, comparisons, reconstruction, sorting, and \(k\tau\)-entry output therefore fit the claimed bound. Exactly \(k\) fair bits suffice for the location lotteries; allocation remains implicit as required.
The proof also handles \(D=0\), singleton blocks, support points split between blocks, coincident facilities, and a degenerate domain \(b_l=b_r\).
The paper attribution is not needed as a theorem invocation: the output supplies its own optimum characterization and strategyproofness proof.
No mathematical repair or additional clarification is required. The output resolves the assigned existence question. Its running-time statement should be understood as the requested parameterized bound, rather than a claim of unrestricted polynomial-time solvability.
⟨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.