On Discrete Truthful Heterogeneous Two-Facility Location

I would make a positive case, but narrowly. This paper contains no named NP-hardness, membership-in-\(\mathrm{P}\), W[1]-hardness, or FPT theorem. Its strongest anchors are instead impossibility and approximation theorems for truthful mechanism design. My lead anchor is Theorem 4; Theorem 9 gives a useful second mirror.

The natural mirror keeps the line and the facility decisions discrete. Only the population becomes continuous.

Let \(V=\{1,\ldots,m\}\) be the public line of possible facility locations. A type is a pair \((x,a)\), where \(x\in V\) is the agent’s public location and \(a=(a_1,a_2)\in\{0,1\}^2\) is her private approval vector. A society is

\[ \mu=(\mu_{x,a})_{x\in V,\;a\in\{0,1\}^2}, \]

where \(\mu_{x,a}\) is the fraction of society of type \((x,a)\). The public location mass is \(\lambda_x=\sum_a\mu_{x,a}\); it is common knowledge, just as the position profile is in the paper. There are at most \(4m\) types, while the underlying population may have \(N\gg m\) agents.

The two facilities must still occupy distinct nodes \(z=(z_1,z_2)\), and a type \((x,a)\) has cost

\[ c_{x,a}(z)=a_1|x-z_1|+a_2|x-z_2|. \]

The continuous social cost is

\[ \mathrm{SC}_\mu(z)=\sum_{x,a}\mu_{x,a}c_{x,a}(z), \]

and the continuous maximum cost is

\[ \mathrm{MC}_\mu(z)=\max_{\mu_{x,a}>0}c_{x,a}(z). \]

These are exactly the paper’s objectives divided by \(N\), so approximation ratios are unchanged when a rational society is expanded into \(N\) named agents.

There is one necessary adjustment to truthfulness. Ordinary unilateral strategyproofness becomes vacuous for a nonatomic population: one individual has zero influence on the reported distribution. The meaningful high-multiplicity version is type-level strategyproofness. A positive-mass subgroup of type \((x,a)\) may report \(b\in\{0,1\}^2\). If it has mass \(q\), the reported society is

\[ \mu'=\mu-q e_{x,a}+q e_{x,b}. \]

A mechanism \(M\) is mass-strategyproof if, for every such deviation,

\[ c_{x,a}(M(\mu)) \leq c_{x,a}(M(\mu')). \]

This says that no homogeneous constituency can improve its true cost by misreporting its approval type. It is stronger than the paper’s individual notion, but it is the natural non-vacuous strategic notion for aggregate reporting.

My lead problem is therefore:

\[ \textsf{SC-HTFL}_{\infty} \]

Given \(m\), a rational public location distribution \(\lambda\), and a threshold \(\rho\), determine whether there exists a deterministic mass-strategyproof mechanism \(M_\lambda\) that maps every compatible reported society \(\hat\mu\) to two distinct facility nodes and satisfies

\[ \mathrm{SC}_\mu(M_\lambda(\mu)) \leq \rho\cdot \mathrm{SC}^*_\mu \]

for every compatible society \(\mu\), where \(\mathrm{SC}^*_\mu\) is the minimum social cost over distinct facility locations. A solution is an explicit mechanism, together with the required truthfulness and approximation guarantees. Operationally, given \(\mu\), the mechanism must output the facility pair.

This is a direct continuization of the paper’s problem: the approval domain remains \(\{0,1\}^2\), facilities remain discrete and distinct, positions remain public, and costs remain distances to approved facilities. The only change is replacing a long list of named agents by masses of indistinguishable types.

Theorem 4 is the lead anchor. It is proved in this paper and states that every strategyproof mechanism has social-cost approximation ratio at least \(4/3\). The obstruction embeds exactly into \(\textsf{SC-HTFL}_{\infty}\). Take \(m=3\) and \(\lambda_1=\lambda_2=\lambda_3=1/3\). In the first society, all three location types approve both facilities. The mechanism must put one facility at node \(1\) or node \(3\); after relabelling, suppose facility \(2\) is at node \(3\). In the second society, the types at \(1\) and \(2\) approve both facilities, while the type at \(3\) approves only facility \(2\). If facility \(2\) moved away from node \(3\), the rightmost constituency could report approval of both facilities and return to the first society, reducing its true cost from at least \(1\) to \(0\). Thus truthfulness forces facility \(2\) to remain at \(3\). Every feasible such outcome has normalized social cost \(4/3\), while the optimum has cost \(1\). Hence the ratio is at least \(4/3\).

This is not an artefact of having only three named agents. The same society can represent \(K\) identical households at each of the three sites, with \(N=3K\). The finite lower-bound witness is therefore embedded in the high-multiplicity domain. I expect this part to be a transfer result: continuization does not dissolve the obstruction. The interesting open question is whether arbitrary masses permit a better global mechanism above this unavoidable lower bound. The paper’s Theorem 5, also proved here, gives a \(4/3\)-approximate truthful mechanism for the three-agent case and is a natural blueprint for the equal-mass three-site subdomain, although its extension to arbitrary masses requires proof.

The secondary problem is the maximum-cost counterpart:

\[ \textsf{MC-HTFL}_{\infty}. \]

It has the same instance, action, and mass-strategyproofness definitions, but asks for a mechanism minimizing

\[ \sup_\mu \frac{\mathrm{MC}_\mu(M_\lambda(\mu))} {\mathrm{MC}^*_\mu}. \]

The anchor is Theorem 9, proved in this paper: every strategyproof mechanism has maximum-cost approximation ratio at least \(2\). Its five-profile argument transfers to societies with mass \(1/3\) at each of three positions. Every intermediate deviation changes the approval vector of one positive-mass type, so the same strategyproofness chain applies, and scaling the population does not change maximum costs. Theorems 7 and 8 provide the matching upper bound \(2\) for suitable \(\alpha\)-LEFT-RIGHT mechanisms in the original discrete setting, making this a credible exact target for a weighted extension.

This second mirror is formally sound but substantively weaker: maximum cost depends only on which types have positive mass, not on their quantities. The social-cost mirror is the stronger continuization because mass genuinely changes the objective and creates a high-multiplicity optimization problem.

The regime is plausible in a city represented by \(m\) discrete neighbourhoods or candidate sites. Thousands of households may share a location node and one of four approval types concerning, say, a school and a bar. Then \(N\) is much larger than \(m\), while the number of relevant types is at most \(4m\). This is precisely the kind of population compression the programme seeks. Related work on facilities located on the real line is not a collision: that makes the outcome space continuous, whereas this mirror keeps the outcome space discrete and makes the population continuous.

The weakest point is the strategic one. The original paper assumes at most one agent per node, so I am extending its domain to allow many agents at one public location, and I am using positive-mass group truthfulness rather than unilateral truthfulness. If one insists on both one-agent-per-node and purely individual deviations, there is no useful high-multiplicity regime: either \(N\leq m\), or an individual has negligible influence and truthfulness becomes vacuous. I regard the neighbourhood or constituency interpretation as a legitimate high-multiplicity version, but it is a modelling extension rather than something already proved by the paper.

The mirror covers Theorem 4 emphatically, and Theorem 9 secondarily. It does not claim that Theorems 1–3 or 6–8 automatically survive weighted masses. Those generate the concrete next questions: whether count-medians can be replaced by mass-weighted medians, whether the \(17/4\) social-cost analysis survives, and whether the optimal truthful approximation ratio for arbitrary \(\mu\) is tractable or develops genuinely continuum-specific difficulty.