Facility Location Games with Fractional Preferences and Limited Resources (aamas24-00067)

\(\mathrm{FL}^{\mathrm{KP}}_\infty\): Given a rational finite-support society \(\mu=\sum_{\ell=1}^{\tau}\mu_\ell\delta_{(x_\ell,p_\ell)}\) over \([0,1]\times\Delta_2\), with \(p\) public and \(x\) privately reportable, compute a deterministic rule selecting \((F_j,y)\in\{F_1,F_2\}\times[0,1]\) that is group-strategy-proof against measurable positive-mass coalitions changing positions and satisfies \(U_\mu(f(\mu))\ge\frac{1}{2}\max_{j,y}U_\mu(F_j,y)\), where \(U_\mu(F_j,y)=\int p_j(1-|x-y|)\,d\mu\); determine whether selecting \(j\in\arg\max_j\int p_j\,d\mu\) and placing it at a corresponding weighted median always achieves this guarantee.

A society is given by its support: \(\mu=\sum_{\ell=1}^{\tau}\mu_\ell\delta_{(x_\ell,p_\ell)}\), where all coordinates and positive masses are binary rationals, \(\sum_\ell\mu_\ell=1\), \(x_\ell\in[0,1]\), and \(p_\ell\in\Delta_2=\{(a,b)\in\mathbb R_{\ge0}^2:a+b=1\}\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length and \(m=2\).
Represent each type's mass by a divisible population on an atomless probability space. Preferences and masses are public; only positions may be reported differently. A deterministic rule maps reported distributions to \((F_j,y)\in\{F_1,F_2\}\times[0,1]\), with true individual utility \(u_{x,p}(F_j,y)=p_j(1-|x-y|)\) and welfare \(U_\mu(F_j,y)=\int u_{x,p}(F_j,y)\,d\mu\).
Coalitions are measurable subsets of positive population mass, may split any type's mass, and may make arbitrary measurable position reports while outsiders' reports remain fixed. Group strategy-proofness means no such deviation strictly improves utility for almost every coalition member, for any fixed reports of outsiders. The rule must therefore be defined also on distributions produced by reports with infinite support.
Define the candidate rule by \(W_j=\int p_j\,d\mu\): choose \(j=1\) if \(W_1\ge W_2\), otherwise \(j=2\), and set \(y=\inf\{t\in[0,1]:\int_{x\le t}p_j\,d\mu\ge W_j/2\}\).

Does a deterministic group-strategy-proof rule exist, evaluable in time polynomial in \(m,\tau,L\) on rational finite-support inputs, that always satisfies \(U_\mu(f(\mu))\ge\tfrac12\max_{j\in\{1,2\},\,y\in[0,1]}U_\mu(F_j,y)\), or is this guarantee impossible? In particular, does the specified candidate rule meet these requirements?

For finite agents with public preferences, maximum total preference followed by the leftmost weighted median is deterministic group-strategy-proof and achieves approximation ratio \(2\); no deterministic strategy-proof rule achieves a smaller ratio. [Fang–Liu, 2024](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p553.pdf).
The [2025 journal version](https://link.springer.com/article/10.1007/s10458-025-09722-8) also states these discrete bounds. No result settling the exact divisible-population problem above was located.

Resolution

Yes. The specified candidate rule meets all the requirements. It is deterministic, is defined on reports with infinite support, is group strategy-proof under the stated almost-everywhere strict-improvement definition, and achieves the welfare guarantee in polynomial time on rational finite-support inputs.

The finite-agent analogue is [Mechanism 3.1 and Theorem 3.1 of Fang–Liu](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2024/pdfs/p553.pdf). The following proof establishes the divisible-population result directly.

1. Definition on arbitrary reported distributions

Let \((\Omega,\mathcal A,P)\) be the atomless probability space representing the population. Write \(x(\omega)\) for true positions and \(p(\omega)\) for public preferences. A position report is any measurable map \(r:\Omega\to[0,1]\).

The public totals are
\[ W_j=\int_\Omega p_j(\omega)\,dP(\omega). \]
They are unaffected by position reports. Because \(W_1+W_2=1\), the selected facility \(j\) has \(W_j\ge\tfrac12>0\).

For this selected facility, define the finite Borel measure
\[ \nu_r(B)=\int_\Omega p_j(\omega)\mathbf 1_{\{r(\omega)\in B\}}\,dP(\omega) \]
on \([0,1]\). Its total mass is \(W_j\). The rule chooses
\[ y_r=\inf\{t\in[0,1]:\nu_r([0,t])\ge W_j/2\}. \]

This depends only on the reported distribution of positions and public preferences. Thus it defines a deterministic distribution-based rule, including when reports have infinite support.

2. Weighted-quantile facts

Let \(\nu\) be any finite Borel measure on \([0,1]\), with total mass \(W>0\). Put \(H=W/2\), \(G(t)=\nu([0,t])\), and
\[ q=\inf\{t\in[0,1]:G(t)\ge H\}. \]

Then
\[ G(q)\ge H,\qquad G(t)<H\ \text{for every }t<q, \]
and consequently
\[ \nu([0,q))\le H,\qquad \nu((q,1])\le H. \]

Proof. The defining set is nonempty because \(G(1)=W\). Every \(t<q\) lies outside that set, giving \(G(t)<H\).

For every \(t>q\) in \([0,1]\), the definition of the infimum supplies an element of the defining set below \(t\); monotonicity therefore gives \(G(t)\ge H\). If \(q<1\), take \(t_n\downarrow q\) with \(t_n>q\). Continuity from above of the finite measure gives \(G(q)=\lim_nG(t_n)\ge H\). If \(q=1\), this follows directly from \(G(1)=W\).

For \(q>0\), continuity from below along \(t_n\uparrow q\), with \(t_n<q\), gives \(\nu([0,q))\le H\); for \(q=0\), that interval is empty. Finally, \(\nu((q,1])=W-G(q)\le H\). This proves all the assertions.

3. Group strategy-proofness

Fix any measurable coalition \(C\subseteq\Omega\) with \(P(C)>0\), and fix arbitrary measurable reports of outsiders.

Let \(r\) be the report profile where coalition members report their true positions and outsiders use those fixed reports. Let \(r'\) be any measurable deviation by the coalition, agreeing with \(r\) outside \(C\). Denote the respective outputs by \((F_j,y)\) and \((F_j,z)\). The facility is unchanged because its selection uses only public preferences.

Define the report-independent weighted population measure
\[ \lambda(A)=\int_A p_j(\omega)\,dP(\omega), \]
and the two cumulative functions
\[ G(t)=\lambda(\{\omega:r(\omega)\le t\}),\qquad G'(t)=\lambda(\{\omega:r'(\omega)\le t\}). \]
Their common total mass is \(W=W_j\), and let \(H=W/2\).

Suppose, for contradiction, that almost every coalition member strictly benefits. If \(z=y\), utilities are unchanged, so \(z\ne y\). Strict improvement also requires \(p_j(\omega)>0\) and
\[ |x(\omega)-z|<|x(\omega)-y| \]
for almost every \(\omega\in C\).

Every \(P\)-null exceptional set is also \(\lambda\)-null because \(0\le p_j\le1\). Squaring the distance inequality shows that the beneficiaries lie strictly on the side of the midpoint closer to \(z\).

Case \(z>y\)

Almost every coalition member has
\[ x(\omega)>(y+z)/2>y. \]
Since coalition members report truthfully under \(r\), their weighted contribution to \(G(y)\) is zero. Outsiders’ reports are unchanged, so
\[ G'(y)\ge G(y)\ge H. \]
Thus \(y\) belongs to the defining set for the deviated quantile, implying \(z\le y\), a contradiction.

Case \(z<y\)

Put \(c=(y+z)/2\), so \(z<c<y\). Almost every coalition member has \(x(\omega)<c\). Consequently,
\[ G(c)=\lambda(\{\omega\notin C:r(\omega)\le c\})+\lambda(C). \]
After deviation, the coalition can contribute at most its entire weighted mass below \(z\). Therefore,
\[ \begin{aligned} G'(z) &\le \lambda(\{\omega\notin C:r(\omega)\le z\})+\lambda(C)\\ &\le \lambda(\{\omega\notin C:r(\omega)\le c\})+\lambda(C)\\ &=G(c)<H. \end{aligned} \]
The final inequality follows from \(c<y\) and the quantile facts. But those same facts applied to the deviated distribution give \(G'(z)\ge H\), a contradiction.

Both cases are impossible. Hence the rule is group strategy-proof for arbitrary fixed outsider reports, arbitrary measurable coalition deviations, and coalitions that split types.

4. Welfare guarantee

Now consider truthful reports. Let \(j\) be the selected facility, \(W=W_j\), and \(\nu\) its weighted position measure. Its selected location \(y\) satisfies
\[ \nu([0,y))\le W/2,\qquad \nu((y,1])\le W/2. \]

For positions left of \(y\), distance is at most \(y\); for positions right of \(y\), distance is at most \(1-y\). Mass at \(y\) contributes zero distance. Thus
\[ \begin{aligned} \int_{[0,1]}|x-y|\,d\nu(x) &\le y\,\nu([0,y))+(1-y)\,\nu((y,1])\\ &\le yW/2+(1-y)W/2=W/2. \end{aligned} \]
It follows that
\[ U_\mu(F_j,y)=W-\int|x-y|\,d\nu(x)\ge W/2. \]

For every facility \(k\) and location \(t\),
\[ U_\mu(F_k,t)\le\int p_k\,d\mu=W_k\le W, \]
where the last inequality is the facility-selection rule. Combining these bounds gives
\[ U_\mu(f(\mu))\ge \tfrac12\max_{k,t}U_\mu(F_k,t). \]
The maximum exists: each facility’s welfare is continuous in its location, and the location interval is compact.

5. Polynomial-time evaluation

On rational finite-support input:

• Compute each \(W_j=\sum_{\ell=1}^{\tau}\mu_\ell p_{\ell,j}\) exactly and select the facility, using the prescribed tie-breaking.
• Sort the support entries by \(x_\ell\).
• Accumulate the selected weights \(\mu_\ell p_{\ell,j}\), and output the first support position where the cumulative sum reaches \(W_j/2\).

Grouping equal positions gives exactly the defining weighted quantile. Processing tied entries individually produces the same output position.

This uses \(O(m\tau+\tau\log\tau)\) rational arithmetic operations and comparisons. All intermediate rational numbers have polynomial bit length: a common denominator for the products can be formed from the input denominators, whose total bit length is bounded by \(L\); summing at most \(\tau\) numerators adds at most \(O(\log\tau)\) bits. Exact arithmetic and sorting therefore take time polynomial in \(m,\tau,L\). No expansion into individual agents is needed.

6. Tightness for this candidate

The candidate’s guarantee is attained by the rational society
\[ \mu=\tfrac14\delta_{(0,(1,0))} +\tfrac14\delta_{(1,(1,0))} +\tfrac12\delta_{(1/2,(0,1))}. \]

Here \(W_1=W_2=\tfrac12\), so the rule selects \(F_1\). Its leftmost weighted median is \(0\), giving welfare \(\tfrac14\). Placing \(F_2\) at \(\tfrac12\) gives welfare \(\tfrac12\), which is optimal because no facility can yield more than its total preference weight.

Thus the welfare fraction is exactly \(\tfrac12\). This establishes tightness for the specified candidate.

⟨structured verdict parsed — rendered above⟩

Assessment

The prover resolves the task correctly. The specified candidate is deterministic, extends to arbitrary measurable position reports, satisfies the stated group strategy-proofness condition, and guarantees at least half of optimal welfare. Its finite-support implementation runs in polynomial bit complexity.

No major or minor mathematical issues were found. The proof is self-contained; the finite-agent result cited in the introduction is not used to justify the divisible-population argument.

Step-by-step verification

1. Definition on arbitrary reported distributions

The public totals \(W_j\) are invariant under position reports. Since \(W_1+W_2=1\), the selected facility has \(W_j\ge \tfrac12\), so the quantile threshold is strictly positive.

For measurable reports \(r\), the expression defining \(\nu_r\) gives a finite Borel measure of total mass \(W_j\). The quantile’s defining set is nonempty because it contains \(1\). Both facility selection and location selection depend only on the reported joint distribution of positions and public preferences.

Thus the rule is well-defined and deterministic even for reports with infinite support. Atomlessness and the possibility of splitting types introduce no additional restriction into this definition.

2. Quantile facts

All stated quantile properties are established correctly.

• For every \(t<q\), the definition of the infimum implies \(G(t)<H\).
• For every \(t>q\), an element of the defining set lies below \(t\), so monotonicity gives \(G(t)\ge H\).
• Continuity from above for a finite measure establishes \(G(q)\ge H\) when \(q<1\). The endpoint \(q=1\) is handled separately.
• Continuity from below establishes \(\nu([0,q))\le H\), with the endpoint \(q=0\) handled explicitly.
• Subtracting \(G(q)\) from \(W\) establishes \(\nu((q,1])\le H\).

The measure-continuity statements have their required hypotheses, and the proof covers atoms, gaps in the support, and both endpoints.

3. Group strategy-proofness

The comparison uses truthful coalition reports against arbitrary coalition deviations while fixing arbitrary outsider reports, exactly as required.

Facility selection cannot change. Strict utility improvement therefore requires positive preference for the selected facility and strictly smaller distance to its new location. The passage from population-almost-everywhere statements to weighted-almost-everywhere statements is justified by \(\lambda\ll P\).

Movement to the right. If \(z>y\), every beneficiary lies strictly above \((y+z)/2\), hence above \(y\). The truthful coalition contributes zero weighted mass to \(G(y)\). Unchanged outsiders already supply \(G(y)\ge H\), and deviating coalition reports can only add mass there. Consequently \(G'(y)\ge H\), forcing the deviated quantile to satisfy \(z\le y\). This is a valid contradiction.

Movement to the left. If \(z<y\), every beneficiary lies strictly below \(c=(y+z)/2\). Thus all coalition weighted mass is included in \(G(c)\). Under deviation, its contribution to \(G'(z)\) is at most \(\lambda(C)\), while outsiders’ contribution below \(z\) is at most their contribution below \(c\). Therefore \(G'(z)\le G(c)<H\). Quantile attainment requires \(G'(z)\ge H\), giving the stated contradiction.

Exceptional null sets do not affect either argument. Coalition members with zero selected-facility preference cannot strictly benefit; this is correctly accounted for. No finiteness assumption on reports or indivisibility assumption on coalition membership is used.

4. Welfare guarantee

The distance bound is correct: positions below \(y\) have distance at most \(y\), positions above \(y\) have distance at most \(1-y\), and mass at \(y\) contributes zero.

The two quantile bounds therefore imply total weighted distance at most \(W/2\), giving welfare at least \(W/2\).

Every competing outcome has welfare at most its facility’s total preference weight, which is at most \(W\). Combining these inequalities proves the requested factor. Continuity on the compact location interval justifies writing a maximum rather than a supremum.

5. Polynomial-time evaluation

The algorithm computes exactly the specified quantile. Zero selected weights and repeated positions cause no problem; processing tied entries individually returns the same position.

The arithmetic-operation count is valid. Products and cumulative sums admit common denominators of polynomial bit length formed from input denominators. Numerators likewise have polynomial bit length, so exact arithmetic and rational comparisons have polynomial cost. The argument establishes bit complexity, not merely a unit-cost arithmetic bound.

6. Tightness example and scope

The example has positive rational masses summing to one. Both facility totals equal \(\tfrac12\), the prescribed tie-break selects \(F_1\), and its leftmost weighted median is \(0\). Candidate welfare is \(\tfrac14\), while optimal welfare is \(\tfrac12\).

This establishes tightness for the candidate, exactly as claimed. It does not establish a lower bound for all divisible-population mechanisms, and the output does not claim that it does.

No additional clarification is needed.

⟨structured verdict parsed — rendered above⟩