Strategyproof Mechanisms for Group-Fair Obnoxious Facility Location Problems (aaai24-28843)

Given a finite rational type support of group-location types and rational masses, compute the PBPM endpoint distribution using each group's left/right mass and determine whether the resulting single rule is mass-group-strategyproof and achieves expected maximum total group cost at most twice the optimum location cost.

A society is given by its support: the list of the \(\tau\) types \((g_k,x_k)\) with positive binary-rational masses \(w_k\), where \(g_k\in\{1,\ldots,m\}\), \(x_k\in\mathbb Q\cap[0,1]\), and \(\sum_k w_k=1\). Every group has positive mass; \(\tau\) counts supported types, not possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Group membership is public and immutable. Per-capita cost at facility location \(y\in[0,1]\) is \(c(y,x)=1-|y-x|\). Define \(C(y)=\max_{1\le j\le m}\sum_{k:g_k=j}w_kc(y,x_k)\) and \(\mathrm{OPT}=\min_{y\in[0,1]}C(y)\).
For each group define \(a_j=\sum_{k:g_k=j,\,x_k\le1/2}w_k\) and \(b_j=\sum_{k:g_k=j,\,x_k>1/2}w_k\).
Mass-PBPM outputs \(0\) with probability \(\alpha\) and \(1\) otherwise. If \(\max_j a_j=0\), set \(\alpha=1\); if \(\max_j b_j=0\), set \(\alpha=0\); otherwise choose \(\alpha\in[0,1]\) satisfying \(\alpha+(1-\alpha)\frac{\max_j(a_j/2+b_j)}{\max_j(a_j/2)}=(1-\alpha)+\alpha\frac{\max_j(b_j/2+a_j)}{\max_j(b_j/2)}\).
A coalition may select rational submasses from any supported types and split each selected submass among finitely many rational reported locations, retaining its group; unselected mass keeps its report. Coalitions must have positive total mass and may span groups.
Mass-group-strategyproofness means that every such deviation leaves a positive amount of coalition mass whose expected per-capita cost, evaluated at its true location, does not strictly decrease. Costs under either output distribution use that same true location.

Does mass-PBPM admit exact computation in time polynomial in \(m,\tau,L\), remain mass-group-strategyproof, and satisfy \(\alpha C(0)+(1-\alpha)C(1)\le2\,\mathrm{OPT}\) for every society, or does any of these guarantees fail?

For finite agents, PBPM is group-strategyproof and achieves approximation ratio \(2\); no randomized strategyproof mechanism supported on two fixed facility locations can achieve a smaller worst-case ratio. [Verified discrete results](https://ojs.aaai.org/index.php/AAAI/article/view/28843/29604).
No result addressing exactly the rational-mass coalition formulation above was located in the literature search.

Result

All three guarantees hold. Mass-PBPM’s exact output distribution can be computed in \(O((m+\tau)L^2)\) bit operations, it is mass-group-strategyproof under the stated coalition definition, and it satisfies the approximation bound \(2\). The approximation bound is attained by a rational-mass society.

1. The probability is uniquely defined and efficiently computable

Define
\(A=\max_j a_j\), \(B=\max_j b_j\), \(U=\max_j(a_j+2b_j)\), and \(V=\max_j(2a_j+b_j)\).

Since the total mass is positive, \(A\) and \(B\) cannot both vanish. When either vanishes, the prescribed boundary rule determines the probability.

Suppose \(A,B>0\). Write \(r=U/A\) and \(s=V/B\). The balancing equation becomes
\(\alpha+(1-\alpha)r=(1-\alpha)+\alpha s\), so its unique solution is

\(\displaystyle \alpha=\frac{r-1}{r+s-2} =\frac{B(U-A)}{B(U-A)+A(V-B)}.\)

To justify uniqueness and feasibility, observe that \(U\ge A\), \(V\ge B\), \(U\ge2B\), and \(V\ge2A\). Thus \(r,s\ge1\) and \(rs\ge4\). In particular, \(r+s-2>0\), and the displayed probability belongs to \([0,1]\).

For an explicit bit-complexity bound, express each mass as \(w_k=p_k/q_k\), with positive integers \(p_k,q_k\), and set \(D=\prod_k q_k\). The bit length of \(D\) is \(O(L)\). Compute the integer masses \(h_k=p_k(D/q_k)\), whose sum is \(D\), and accumulate

\(\displaystyle P_j=\sum_{k:g_k=j,\ x_k\le1/2}h_k,\qquad Q_j=\sum_{k:g_k=j,\ x_k>1/2}h_k.\)

Let \(P=\max_jP_j\), \(Q=\max_jQ_j\), \(H=\max_j(P_j+2Q_j)\), and \(K=\max_j(2P_j+Q_j)\). In the interior case, output the exact fraction

\(\displaystyle \alpha=\frac{Q(H-P)}{Q(H-P)+P(K-Q)}.\)

All these integers, including the numerator and denominator, have \(O(L)\) bits. Classifying each rational location relative to \(1/2\) uses an integer comparison. Using schoolbook integer arithmetic, the entire computation takes \(O((m+\tau)L^2)\) bit operations. In particular, it never enumerates an expanded population.

2. Monotonicity under transfers of mass

Consider transferring mass from the left half to the right half within each group. For numbers \(0\le\delta_j\le a_j\), the resulting totals are
\(a'_j=a_j-\delta_j\) and \(b'_j=b_j+\delta_j\).

Consequently,

\(A'\le A,\qquad B'\ge B,\qquad U'\ge U,\qquad V'\le V.\)

If both profiles have positive \(A,B\), these inequalities imply \(r'\ge r\) and \(s'\le s\). The function
\(f(r,s)=(r-1)/(r+s-2)\), on its domain \(r,s\ge1\), \(r+s>2\), satisfies

\(\displaystyle \frac{\partial f}{\partial r}=\frac{s-1}{(r+s-2)^2}\ge0,\qquad \frac{\partial f}{\partial s}=-\frac{r-1}{(r+s-2)^2}\le0. \)

Increasing \(r\) first and then decreasing \(s\) stays in this domain. Hence \(\alpha'\ge\alpha\).

The boundary cases also satisfy this conclusion. If initially \(B=0\), then initially \(\alpha=0\); if finally \(A'=0\), then finally \(\alpha'=1\). If initially \(A=0\), no left-to-right transfer is possible. If finally \(B'=0\), no such transfer occurred.

Thus arbitrary left-to-right transfers weakly increase \(\alpha\). Reversing the two profiles shows that arbitrary right-to-left transfers weakly decrease \(\alpha\).

3. Mass-group-strategyproofness, including split reports

At true location \(x\), the expected per-capita cost under probability \(\alpha\) is

\(\displaystyle e_\alpha(x)=\alpha(1-x)+(1-\alpha)x=x+\alpha(1-2x).\)

Consider any allowed coalition deviation, and let its resulting probability be \(\alpha'\). Every selected portion of a supported type has the same true location and hence the same cost change, regardless of how its reports are split:

\(\displaystyle e_{\alpha'}(x)-e_\alpha(x)=(\alpha'-\alpha)(1-2x).\)

There are three cases.

• If \(\alpha'=\alpha\), all coalition mass has unchanged expected cost.

• If \(\alpha'>\alpha\), all coalition mass with true location \(x\le1/2\) has cost that does not strictly decrease. If any positive amount of such mass was selected, the required conclusion follows. Otherwise, all selected mass is truly in the right half. Its reports can only transfer some of that mass from right to left; reports remaining in the right half leave the half-group totals unchanged. Therefore \(a'_j\ge a_j\) and \(b'_j\le b_j\) for every group. Section 2 then gives \(\alpha'\le\alpha\), a contradiction.

• If \(\alpha'<\alpha\), all coalition mass with true location \(x\ge1/2\) has cost that does not strictly decrease. If none of this mass was selected, all selected mass is truly in the left half. Its reports produce only left-to-right transfers, so Section 2 gives \(\alpha'\ge\alpha\), again a contradiction.

Because the coalition selects mass from finitely many supported types, a selected type with nondecreasing cost contributes a positive amount of coalition mass. This proves exactly the requested mass-group-strategyproofness, including coalitions spanning groups and splitting their selected masses among reports.

4. Exact transfer of the finite-agent approximation theorem

We use the finite-agent result supplied in the question: PBPM with publicly fixed groups and the stated half-group counting rule satisfies
\(\beta F(0)+(1-\beta)F(1)\le2\min_{y\in[0,1]}F(y)\), where \(F(y)\) is the maximum total group cost and \(\beta\) is PBPM’s probability of outputting \(0\). This is [Theorem 4 of Li, Li, and Chan](https://ojs.aaai.org/index.php/AAAI/article/view/28843/29604).

Here is an exact replication argument verifying its applicability.

Choose a positive integer \(N\) for which every \(Nw_k\) is an integer; for example, take the denominator product \(D\) from Section 1. Replace supported type \(k\) by \(Nw_k\) finite agents, each having location \(x_k\) and group \(g_k\).

Every group remains nonempty because its original mass was positive. Locations lie in \([0,1]\), and group membership remains public and fixed. Thus the replicated instance satisfies the finite theorem’s hypotheses.

For every group and every facility location \(y\), its replicated total cost is exactly \(N\) times its original mass-weighted cost. Taking the maximum over groups gives

\(\displaystyle F(y)=N C(y).\)

Also, the replicated left and right counts in group \(j\) are \(Na_j\) and \(Nb_j\), including the same convention at \(1/2\). Multiplying every half-group total by \(N\) preserves every ratio in the balancing equation and preserves the zero cases. By the uniqueness established in Section 1, the replicated probability is \(\beta=\alpha\).

The function \(C\) is continuous, being the maximum of finitely many continuous functions, so its minimum on \([0,1]\) exists. Therefore
\(\min_y F(y)=N\,\mathrm{OPT}\). Applying the finite theorem and dividing by \(N>0\) yields

\(\displaystyle \alpha C(0)+(1-\alpha)C(1)\le2\,\mathrm{OPT}. \)

This replication is a proof device only: \(N\) may be exponentially large, while the direct computation in Section 1 remains polynomial.

5. The approximation bound is sharp

Take two groups, each consisting of one supported type of mass \(1/2\), with true locations \(0\) and \(1\), respectively. Then
\(A=B=1/2\), \(U=V=1\), and \(\alpha=1/2\).

For this society,

\(\displaystyle C(y)=\frac12\max\{1-y,y\},\qquad \mathrm{OPT}=C(1/2)=\frac14.\)

Both endpoint objectives equal \(1/2\), so the expected objective is \(1/2=2\,\mathrm{OPT}\).

⟨structured verdict parsed — rendered above⟩

The output resolves all three requested guarantees. The argument is correct and rigorous; I found no major or minor mathematical issues.

• Probability definition and algebra

The substitutions are correct: the two ratios in the balancing equation become \(r=U/A\) and \(s=V/B\). Rearranging gives
\[ \alpha(r+s-2)=r-1, \]
and hence both displayed expressions for \(\alpha\).

The inequalities \(U\ge A\), \(V\ge B\), \(U\ge2B\), and \(V\ge2A\) follow directly from the definitions and nonnegative group masses. When \(A,B>0\), they imply \(r,s\ge1\) and \(rs\ge4\). Thus the denominator is strictly positive. Moreover, \(0\le r-1\le r+s-2\), verifying \(\alpha\in[0,1]\), including possible endpoint probabilities.

Since total mass is positive, \(A=B=0\) is impossible. The prescribed zero cases therefore define the probability without ambiguity.

• Exact computation and bit complexity

The denominator product \(D\) has \(O(L)\) bits because the sum of the input denominators’ bit lengths is bounded by the total input length. Each \(h_k=p_k(D/q_k)\) is an integer, and normalization gives \(\sum_k h_k=D\).

Consequently, the accumulated group masses and their maxima have \(O(L)\) bits. The products forming the output numerator and denominator also have \(O(L)\) bits. Substitution of the integer totals correctly cancels all factors of \(D\).

Comparing a rational location with \(1/2\), accumulating masses, computing maxima, and performing the stated integer arithmetic fit within \(O((m+\tau)L^2)\) bit operations using schoolbook arithmetic. This bound is conservative but valid. An exact rational output does not require expansion into individual agents.

• Monotonicity under mass transfers

Under the stated left-to-right transfer, each group’s contribution to \(U\) increases by \(\delta_j\), while its contribution to \(V\) decreases by \(\delta_j\). Together with the changes in \(a_j,b_j\), this verifies all four inequalities for \(A',B',U',V'\).

For interior profiles, these inequalities correctly yield \(r'\ge r\) and \(s'\le s\). Both partial derivatives are computed correctly.

The proposed coordinatewise comparison stays within the function’s domain: increasing \(r\) preserves \(r+s>2\), and subsequently decreasing \(s\) leaves the sum at least its valid final value \(r'+s'>2\). Thus the monotonicity conclusion follows.

The boundary discussion covers every possibility. Reversing a right-to-left transfer produces an admissible left-to-right transfer, so the reverse monotonicity conclusion is also justified.

• Mass-group-strategyproofness

The expected cost formula and its difference are correct:
\[ e_{\alpha'}(x)-e_\alpha(x)=(\alpha'-\alpha)(1-2x). \]

The three cases exhaust all possible probability changes.

If the probability increases, any selected positive mass at a true location \(x\le1/2\) supplies the required nonimproving mass. Otherwise, every selected portion originates in the right half, so its reports can only produce right-to-left transfers or leave the half-group totals unchanged. The resulting contradiction with monotonicity is valid.

The decreasing-probability case is symmetric, with the midpoint correctly included among locations whose costs do not strictly decrease. If the probability is unchanged, the entire positive coalition mass has unchanged cost.

Splitting reports does not affect this reasoning: every selected portion retains its true location and group, and expected cost depends only on that true location and the resulting probability. Finiteness of the supported types ensures that the identified nonimproving selected mass has positive amount. This establishes exactly the coalition property requested.

• Application of the finite-agent approximation theorem

I verified the cited source. Its Mechanism 3 uses the same half-interval convention, balancing equation, zero cases, endpoint distribution, public groups, and cost definition. Theorem 4 concerns expected maximum total group cost and comparison with the optimum over the full interval. Thus the theorem invoked in Section 4 matches the required finite statement. [Li, Li, and Chan, Mechanism 3 and Theorem 4](https://ojs.aaai.org/index.php/AAAI/article/view/28843/29604).

The replication produces positive integer multiplicities and nonempty groups. For every \(y\), the equality \(F(y)=NC(y)\) is exact. The half-group counts scale by the same factor, preserving both the balancing equation and boundary rules; uniqueness therefore gives \(\beta=\alpha\).

Continuity justifies existence of the minimum. Scaling the objective scales its minimum, so dividing the finite theorem’s inequality by \(N>0\) proves the requested bound. The potentially large replication is used only in the proof and does not compromise the computation bound.

• Sharpness and repair feedback

The example satisfies all input requirements. Its stated maxima, probability, objective, optimum, and endpoint costs are correct, giving ratio exactly \(2\).

No repairs or additional lemmas are needed. The polynomial classification below concerns exact computation of Mass-PBPM’s distribution, which is the computational question asked; the output does not separately claim an algorithm for computing \(\mathrm{OPT}\).

⟨structured verdict parsed — rendered above⟩