| paper | Proportional Fairness in Obnoxious Facility Location |
| authors | — |
| venue | AAMAS 2024 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Lemma 5.10
statement extracted from the paper’s text layer
Given rational locations \(x_t\in[0,1]\) and masses \(\mu_t\ge0\) with \(\sum_{t=1}^{\tau}\mu_t=1\), compute an exact endpoint lottery \(\pi^\star=p^\star\delta_0+(1-p^\star)\delta_1\) maximizing \(\sum_t\mu_t\bigl(p x_t+(1-p)(1-x_t)\bigr)\) subject to \(p x_t+(1-p)(1-x_t)\ge\mu_t/2\) for every \(t\) and \(0\le p\le1\).
A finite-support high-multiplicity OFLP with types \(t\) of location \(x_t\) and mass \(\mu_t\), endpoint-lottery decision variable \(p\), utilitarian objective \(\sum_t\mu_t\bigl(p x_t+(1-p)(1-x_t)\bigr)\), and type-level \(2\)-UFS constraints.
The mirror is atom-sensitive: \(2\)-UFS is vacuous for atomless populations, while finite support represents a high-multiplicity town or district model rather than smooth geography.
fatal: False
The mirror covers randomized and deterministic welfare optimization and price-of-fairness results for \(2\)-UFS, but leaves individual strategic behavior, \(\epsilon\)-equilibria, atomless \(2\)-PF, and the hybrid extension largely untreated.
The strongest positive case is a high-multiplicity version of the obnoxious facility-location problem in which population mass, rather than the identities of residents, is the input. The paper contains no named NP-hardness or membership-in-\(\mathrm{P}\) theorem in the strict complexity-theoretic sense. It does, however, contain named algorithmic and approximation results, which are sufficient anchors for a continuous mirror.
Let a type be \(t=(x_t,O)\), where \(x_t\in[0,1]\) is the residential location and \(O\) records the common obnoxious preference. A society is a finite-support distribution \(\mu=(\mu_1,\ldots,\mu_\tau)\), where \(\mu_t\) is the fraction of residents of type \(t\). The intended regime is a city, corridor, or collection of towns with very many residents but only \(\tau\) distinct effective locations, with \(\tau\ll N\). This is exactly the paper’s own motivating situation of co-located residents, apartment buildings, or towns.
For a facility location \(y\), type \(t\) has utility \(|y-x_t|\). For a randomized mechanism \(\pi\) over facility locations,
\[ u_t(\pi)=\int_{[0,1]} |y-x_t|\,d\pi(y), \qquad \mathrm{UW}_\mu(\pi)=\sum_t\mu_t u_t(\pi). \]
The continuous form of \(2\)-UFS is
\[ u_t(\pi)\ge \frac{\mu_t}{2} \]
for every type \(t\); deterministically, this becomes \(|y-x_t|\ge \mu_t/2\). This is not an arbitrary rescaling: it is precisely the paper’s guarantee \(|S|/(2n)\) with the high-multiplicity substitution \(|S|/n=\mu_t\).
My lead anchor is Lemma 5.10, proved in this paper: the \(2\)-UFS randomized mechanism is optimal for utilitarian welfare among all randomized mechanisms satisfying \(2\)-UFS. The quantitative companions are Theorem 5.11 and Corollary 5.12, also proved here, which give the tight price of fairness
\[ \frac{2}{7}(1+2\sqrt{2}) \]
for utilitarian welfare.
The corresponding continuous problem is:
Given rational locations \(x_1,\ldots,x_\tau\in[0,1]\) and rational masses \(\mu_1,\ldots,\mu_\tau\) summing to \(1\), compute a lottery \(\pi^\star\) over facility locations that maximizes \(\mathrm{UW}_\mu(\pi)\) subject to \(u_t(\pi)\ge\mu_t/2\) for every type \(t\).
A solution is an exact optimal lottery, together with its welfare value. Lemma 5.3 shows that an optimum may be taken to have support only at \(0\) and \(1\), so it suffices to output \(p\in[0,1]\), where
\[ \pi_p=p\delta_0+(1-p)\delta_1. \]
Then
\[ u_t(\pi_p)=p\,x_t+(1-p)(1-x_t), \]
and the problem is the one-variable linear program
\[ \max_{0\le p\le1} \sum_t\mu_t\bigl(p\,x_t+(1-p)(1-x_t)\bigr) \]
subject to
\[ p\,x_t+(1-p)(1-x_t)\ge \frac{\mu_t}{2} \qquad \text{for every }t. \]
This is a Class A candidate: the feasible values of \(p\) form an interval obtained by intersecting \(\tau\) linear constraints, and the objective is linear. It is solvable in time polynomial in \(\tau\) and the input bit length, without expanding a denominator representing the total number of residents.
The transfer to the paper is exact on rational finite-support societies. If \(\mu_t=a_t/D\), create \(a_t\) agents of type \(t\). The resulting \(D\)-agent profile is literally an instance of the paper, while the continuous algorithm works on the \(\tau\) type masses rather than on \(D\) individuals. Thus Theorem 5.11 and Corollary 5.12 transfer directly to this high-multiplicity problem. Randomization is not being smuggled in as the source of continuity: randomized mechanisms are already central to the paper; the continuous object is the population distribution.
A second, independent anchor is Theorem 4.3, proved here: the price of \(2\)-UFS for deterministic utilitarian welfare is \(2\), and the bound is tight. Its continuous counterpart is:
Given \(\mu\), compute a deterministic facility location
\[ > y^\star\in\arg\max_{y\in F_\mu}\sum_t\mu_t|y-x_t|, > \]
where
\[ > F_\mu=\left\{y\in[0,1]: |y-x_t|\ge\frac{\mu_t}{2} > \text{ for every }t\right\}. > \]
The unrestricted optimum is at \(0\) or \(1\). The fair set is the complement of a union of at most \(\tau\) forbidden intervals, and the welfare function is piecewise linear, so the optimum can be found by checking polynomially many interval endpoints. For rational finite-support inputs, the paper’s tight factor \(2\) carries over by clearing denominators. This is another Class A problem, and it removes any concern that the positive case depends on outcome randomization.
The authors should recognize both mirrors immediately: the location domain, utility, fairness axiom, welfare objective, and facility action are unchanged. Only the representation of the electorate changes from a list of agents to a distribution over co-located types. The scenario is plausible for municipal planning: millions of residents are grouped into a moderate number of towns, districts, or apartment clusters, and a landfill, prison, refinery, or power plant must be placed along a geographic corridor.
I would not claim that this mirrors every result in the paper. The individual \(2\)-IFS guarantee is not a good continuum object on its own, since \(1/(2n)\) vanishes for infinitesimal agents; its meaningful high-multiplicity form is essentially the type-level \(2\)-UFS guarantee. Likewise, individual strategyproofness and the paper’s \(\epsilon\)-Nash results become delicate because a single infinitesimal agent cannot change the outcome. I therefore leave Propositions 4.7–4.8 and Theorems 4.10–4.16 outside the core mirror.
The weakest point is that exact \(2\)-UFS protects atoms. A genuinely smooth population with no co-located mass makes the constraint vacuous. The paper itself anticipates this issue through \(2\)-PF. A natural further problem is to let every subpopulation \(\nu\le\mu\) impose
\[ |y-x| \ge \frac{\nu([0,1])}{2} - \operatorname{diam}(\operatorname{supp}\nu) \]
for \(\nu\)-almost every \(x\), and ask for a feasible or welfare-optimal facility. That would be the genuinely local continuous mirror of Theorem 6.3. The hybrid extension likewise yields a clean mass model with types \((x,C)\) and \((x,O)\), anchored by Theorem 7.4. Those questions may require new separation algorithms, but the lead \(2\)-UFS mirrors are already precise, faithful, and efficiently solvable.
The strongest negative case is that the paper’s substantive results are not complexity results. Lemma 5.10 and Theorem 5.11 characterize a welfare-optimal randomized mechanism and its price of fairness; Theorem 4.3 gives another price bound. They do not identify a hard computational problem, a complexity boundary, or an algorithmic bottleneck of the kind ChoCo is designed to chart.
There is also a real modelling fault line. Exact \(2\)-UFS only protects atoms: for a type of mass \(\mu_t\), the guarantee is \(\lvert y-x_t\rvert\ge \mu_t/2\). For an atomless population, every individual type has mass zero, so \(2\)-UFS becomes vacuous. Retaining atoms gives a finite collection of towns or buildings with population weights—a high-multiplicity encoding of the original finite profile, rather than a genuinely continuous population. Replacing it by the proposed \(2\)-PF condition avoids vacuity only by introducing a new grouping axiom whose result depends on the chosen spatial scale and representation. Theorem 6.3 is an existence theorem, not a computational result that naturally demands a ChoCo mirror. The hybrid extension has the same problem: adding masses for \((x,C)\) and \((x,O)\) is formally easy, but it inherits the atom/continuum dichotomy.
That objection does defeat the proposed mirrors if “continuous” is required to mean an atomless geographic population. It does not defeat them under ChoCo’s stated rules. The programme explicitly accepts finite-support high-multiplicity societies, and a city consisting of many residents in a moderate number of towns is a sensible regime. Under that regime, the proponent’s translation of \(2\)-UFS is exact, and the one-variable LP for the randomized mechanism is a legitimate Class A computational question. The deterministic \(2\)-UFS mirror is equally faithful: rational masses can be expanded into a finite profile, so the factor \(2\) transfers exactly.
The strategic results would indeed degenerate under infinitesimal agents, but the proponent did not rely on them. Consequently, the honest conclusion is that the negative case is weak. One can argue that the atomless and strategic mirrors are poor, and that the paper is primarily normative rather than complexity-theoretic. One cannot honestly claim that no worthwhile mirror exists: the finite-support high-multiplicity versions of Lemma 5.10, Theorem 5.11, and Theorem 4.3 survive the strongest objections.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.