Answer: A deterministic strategy-proof \(2\)-approximation exists, has strictly positive social utility on every society, and is computable in time polynomial in \(m,\tau,L\).
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateMechanism 2 is a deterministic strategy-proof mechanism with an approximation ratio of 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite-support society of types \(t=(x_t,p_t)\), where \(x_t\in[0,L]\), \(p_t\in\{(p_1,p_2)\in[0,1]^2:p_1+p_2=1\}\), and positive rational masses \(\mu_t\) summing to \(1\), with locations public and preferences reported, construct a deterministic mechanism returning \(y_1,y_2\in[0,L]\). For each type, allow its whole mass to replace its reported preference by \(q_t\), while evaluating its utility using its true \(p_t\); require that no such deviation improves utility and that \(\mathrm{OPT}(\mu)/\mathrm{SU}_{\mu}(y)\le 2\), with computation polynomial in \(\tau\) and the input bit length.
A society is given by its support: the list of the \(\tau\) distinct types with positive binary-rational masses \(\mu_t\), summing to \(1\); \(\tau\) is the support size, not the number of possible types.
There are \(m=2\) labeled facilities on an interval of positive rational length \(\ell\). Each type has a public rational location \(x_t\in[0,\ell]\) and a private rational preference \(p_t\in\Delta_2=\{(a,b)\in\mathbb Q_{\ge0}^2:a+b=1\}\). Let \(L\) be the total input bit length.
A deterministic mechanism without payments maps every reported society to \(f(\mu)=(y_1,y_2)\in[0,\ell]^2\); facilities may coincide, and zero preference for a facility is allowed throughout the society.
Define \(u_t(y)=\ell-p_{t,1}|x_t-y_1|-p_{t,2}|x_t-y_2|\), \(\mathrm{SU}_\mu(y)=\sum_t\mu_tu_t(y)\), and \(\mathrm{OPT}(\mu)=\max_{y\in[0,\ell]^2}\mathrm{SU}_\mu(y)\).
For \(q\in\Delta_2\), let \(\mu^{t\to q}\) move the entire mass \(\mu_t\) from \((x_t,p_t)\) to \((x_t,q)\), merging identical reported types. Masses and locations cannot be misreported. Require \(u_t(f(\mu))\ge u_t(f(\mu^{t\to q}))\) for every society, type, and report.
Does there exist such a deterministic strategy-proof mechanism, computable in time polynomial in \(m,\tau,L\), with \(\mathrm{SU}_\mu(f(\mu))>0\) and \(\mathrm{OPT}(\mu)/\mathrm{SU}_\mu(f(\mu))\le2\) for every society, or is this approximation guarantee unattainable under these requirements?
For finite agents with public locations and private fractional preferences, a deterministic strategy-proof \(2\)-approximation is known, and ratios below \(1.06\) are impossible. [Source](https://cdn.aaai.org/ojs/11458/11458-13-14986-1-2-20201228.pdf)
No result settling exactly the support-encoded mass problem above was located.
Such a mechanism exists. It is deterministic, strategy-proof under the specified whole-mass deviations, and computable in time polynomial in \(m,\tau,L\). It guarantees \(\mathrm{SU}_\mu(f(\mu))\ge \ell/2>0\), and hence approximation ratio at most \(2\).
Indeed, the constant mechanism \(f(\mu)=(\ell/2,\ell/2)\) already satisfies these requirements: reports cannot affect its output, and every type has utility at least \(\ell/2\). To address the preference-dependent case as well, we prove that the extreme-support midpoint mechanism works directly on the encoded support.
For each labeled facility \(j\in\{1,2\}\), define its set of supporting locations by
\(S_j(\mu)=\{x_t:p_{t,j}>0\}\).
If this set is nonempty, let \(a_j=\min S_j(\mu)\), \(b_j=\max S_j(\mu)\), and choose \(y_j=(a_j+b_j)/2\). If it is empty, choose \(y_j=\ell/2\). Set \(f(\mu)=(y_1,y_2)\).
The nonempty-support rule is Mechanism 2 in the [cited paper](https://cdn.aaai.org/ojs/11458/11458-13-14986-1-2-20201228.pdf). The following proof explicitly handles whole-mass deviations, merging, and empty facility support.
Fix an arbitrary society \(\mu\), a supported type \(t\), and a report \(q\in\Delta_2\). Write \(x=x_t\), \(\mu'=\mu^{t\to q}\), \(y=f(\mu)\), and \(y'=f(\mu')\).
We prove that, for every facility \(j\) with \(p_{t,j}>0\),
\(|x-y_j|\le |x-y'_j|\).
Fix such a facility. Its original supporting set \(S=S_j(\mu)\) contains \(x\).
If \(q_j>0\), moving the mass retains a positive supporter at \(x\). Every other supporting location also remains. Therefore \(S_j(\mu')=S\), even if reported types merge, and \(y'_j=y_j\).
Suppose instead that \(q_j=0\). Every type other than \(t\) retains its location and preference. Consequently, the supporting set either remains unchanged, because another type at \(x\) supports facility \(j\), or becomes \(S\setminus\{x\}\). The unchanged case is immediate. In the deletion case, consider the following possibilities.
These cases exhaust all possibilities. Facilities with \(p_{t,j}=0\) contribute zero to the type’s true cost. Multiplying the proved inequalities by the nonnegative true preferences and summing gives
\(\sum_{j=1}^2 p_{t,j}|x-y_j|\le \sum_{j=1}^2 p_{t,j}|x-y'_j|\).
Subtracting from \(\ell\) proves
\(u_t(f(\mu))\ge u_t(f(\mu^{t\to q}))\).
Thus the mechanism satisfies exactly the required strategy-proofness condition.
Fix any supported type \(t\). Whenever \(p_{t,j}>0\), its location belongs to \(S_j(\mu)\), so \(a_j\le x_t\le b_j\). The chosen midpoint therefore satisfies
\(|x_t-y_j|\le (b_j-a_j)/2\le \ell/2\).
Terms with \(p_{t,j}=0\) vanish. Since \(p_{t,1}+p_{t,2}=1\), it follows that
\(u_t(f(\mu))=\ell-\sum_{j=1}^2p_{t,j}|x_t-y_j|\ge \ell/2\).
Using \(\sum_t\mu_t=1\), we obtain
\(\mathrm{SU}_\mu(f(\mu))\ge \sum_t\mu_t\,\ell/2=\ell/2>0\).
For every feasible placement \(z\), each distance cost is nonnegative, so \(u_t(z)\le\ell\). Consequently \(\mathrm{OPT}(\mu)\le\ell\), and
\(\mathrm{OPT}(\mu)/\mathrm{SU}_\mu(f(\mu))\le \ell/(\ell/2)=2\).
Scan the \(\tau\) supported types, testing whether each preference coordinate is positive and maintaining the minimum and maximum supporting locations for each facility. This uses \(O(m\tau)\) rational tests and comparisons, followed by at most \(m\) midpoint computations.
Comparisons can be performed exactly by cross-multiplication. Their operands and intermediate products have bit lengths polynomial in \(L\); each output midpoint also has polynomial bit length. Standard integer arithmetic therefore gives total running time polynomial in \(m,\tau,L\).
The mechanism never expands a mass into individual agents. It uses only supporting locations, so neither mass magnitude nor merging identical reports creates a computational or incentive obstruction.
⟨structured verdict parsed — rendered above⟩
The claimed existence result is proved. Both the constant mechanism and the extreme-support midpoint mechanism meet the requirements. No major or minor mathematical issues were found.
The output addresses the support-encoded society and the specified whole-mass deviations directly.
For each facility, the supporting-location set is finite. When nonempty, its minimum and maximum exist and belong to \([0,\ell]\), so their midpoint is a feasible rational position. When empty, the specified position \(\ell/2\) is also feasible and rational.
The rule is deterministic and applies to every valid reported society, including societies with coincident locations or an unsupported facility. It does not require facilities to be distinct.
The opening observation is correct and already resolves the existence question.
For \(f(\mu)=(\ell/2,\ell/2)\), reports cannot change the output, so every required incentive inequality holds with equality. Because every location lies in \([0,\ell]\), its distance from either facility is at most \(\ell/2\). Normalization of the preferences therefore gives utility at least \(\ell/2\).
The subsequent welfare argument applies to this mechanism as well. Computing its two rational coordinates requires polynomial time and polynomial output length. This observation uses precisely the placements permitted by the task; facility coincidence is explicitly allowed.
The coordinatewise argument is valid.
These cases exhaust every possible deletion from a finite nonempty set containing \(x_t\).
Coordinates with zero true preference contribute zero regardless of their new positions. Multiplying the remaining distance inequalities by true preferences and summing therefore proves the required utility inequality. No assumption about mass size, absence of merging, or independent coordinate reports is needed.
Every positively weighted facility has \(x_t\) between its supporting extremes. The midpoint distance bound
\[ |x_t-y_j|\le (b_j-a_j)/2\le \ell/2 \]
is correct. Zero-preference terms vanish, and the preferences sum to one, giving
\[ u_t(f(\mu))\ge \ell/2. \]
Positive masses summing to one then give
\[ \mathrm{SU}_\mu(f(\mu))\ge \ell/2>0. \]
For every feasible placement, nonnegative distance costs imply utility at most \(\ell\), hence \(\mathrm{OPT}(\mu)\le\ell\). Division is justified by the strictly positive welfare bound, and the claimed approximation ratio follows.
The proof correctly uses an upper bound on optimal welfare; it does not assume that this upper bound is attained.
The computation claim is valid. Scanning the encoded support requires \(O(m\tau)\) positivity tests and location comparisons. Stored extremes are input rationals, so repeated comparisons do not accumulate denominator growth. Exact cross-products have bit length polynomial in \(L\), as do the finitely many midpoint computations and output coordinates.
The algorithm never expands encoded masses into agents. Thus potentially large populations represented by short mass encodings create no computational gap.
The nonempty-support rule agrees with Mechanism 2 in the [cited paper](https://cdn.aaai.org/ojs/11458/11458-13-14986-1-2-20201228.pdf). The submitted argument independently proves the required properties and explicitly supplies the empty-support convention, so it does not depend on transferring a finite-agent theorem without checking its hypotheses.
Required repairs: none. The constant-mechanism argument alone settles the target; the additional midpoint argument is also rigorous.
⟨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.