| paper | Truthful Facility Assignment with Resource Augmentation: An Exact Analysis of Serial Dictatorship |
| authors | I. Caragiannis, Aris Filos-Ratsikas, S. Frederiksen, Kristoffer Arnsfelt Hansen, Zihan Tan |
| venue | WINE 2016 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: \(W_g(\tau)=\sum_{i=0}^{\tau-1}(2/g)^i\). · discrete side: other · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite metric facility set \(F_1,\ldots,F_m\), rational per-capita capacities \(q_j\), rational type masses \(\mu_t\), preferred points \(a_t\), a fixed priority order, and augmentation factor \(g\), compute the block-Serial-Dictatorship mass assignment \(x\), compute \(\operatorname{OPT}_q(\mu)=\min\{\sum_{t,j}d(a_t,F_j)z_{tj}:\sum_jz_{tj}=\mu_t,\ \sum_tz_{tj}\le q_j,\ z_{tj}\ge0\}\), and characterize the worst-case ratio \(R_g(\mu)=\sum_{t,j}d(a_t,F_j)x_{tj}/\operatorname{OPT}_q(\mu)\) as a function of \(g\) and the number of types \(\tau\).
Types \(t\) carry mass \(\mu_t\), preferred point \(a_t\), and finite priority \(\rho_t\). Mass is processed in priority order and assigned greedily to nearest facilities with residual augmented capacity \(gq_j\); \(x_{tj}\) is the assigned mass, while \(z_{tj}\) is the benchmark transportation allocation under capacities \(q_j\).
The mirror covers Theorem 1 and the first three statements of Theorem 3. It leaves the Random Serial Dictatorship results, Corollary 1, Corollary 2, and Appendix Theorem 4 aside.
The strongest positive case is a genuine high-multiplicity mirror of the paper’s deterministic Serial Dictatorship results. It is not a hardness-driven case—the paper contains no named NP-hardness, \(P\), FPT, or W[1]-hardness theorem—but its approximation theorems provide a solid algorithmic anchor.
My lead anchor is Theorem 1, proved in this paper. It states that for facility assignment with \(n\) agents, Serial Dictatorship has approximation ratio at most \(2^n-1\) without augmentation, at most \(\log(n+1)\) with augmentation factor \(g=2\), and at most \(g/(g-2)\) for every \(g\ge3\). The first bound was known from earlier online-transportation work, but the authors reprove it; the other bounds are established through their directed-tree and primal-dual LP analysis.
The continuous mirror is Continuous Resource-Augmented Serial Dictatorship. An instance consists of:
The type order can represent batches of patients, pupils, commuters, or parking users processed in the same priority wave. Thus a type is a genuine complete type: agents in it have the same preferred point and the same mechanism-relevant priority class.
Serial Dictatorship processes the type masses in order. Type \(t\)'s mass is assigned greedily to the nearest facilities with remaining augmented capacity \(gq_j\), with a fixed tie-breaking rule. Let \(x_{tj}\) be the resulting assignment mass. Every individual still receives one integral facility; \(x_{tj}\) is only the aggregate mass assigned from type \(t\) to facility \(j\).
The benchmark is the minimum-cost mass assignment under the original capacities:
\[ \operatorname{OPT}_q(\mu)= \min_z\sum_{t,j}d(a_t,F_j)z_{tj} \]
subject to
\[ \sum_jz_{tj}=\mu_t,\qquad \sum_tz_{tj}\le q_j,\qquad z_{tj}\ge0. \]
The continuous question is: given such an instance and \(g\), compute the greedy mass assignment, compute \(\operatorname{OPT}_q(\mu)\), and determine the ratio
\[ R_g(\mu)= \frac{\sum_{t,j}d(a_t,F_j)x_{tj}} {\operatorname{OPT}_q(\mu)}. \]
The global version asks for the supremum of this ratio over all finite-support societies, and for its dependence on \(g\) and the number of types.
This is a natural high-multiplicity regime. Think of a large regional health system assigning thousands of patients from a small number of recurring postcode or workplace cohorts to GP sites, with capacities scaled proportionally to population. There may be \(N\) agents but only \(\tau\) location-and-priority types, with \(N\gg\tau\). For rational masses, choose \(N\) clearing all denominators, create \(N\mu_t\) agents of type \(t\), and give facility \(j\) capacity \(Nq_j\). Running the paper’s original Serial Dictatorship and dividing all costs by \(N\) gives exactly the mass formulation above. This is not continuity of the outcome space: facilities remain indivisible and each agent receives one facility.
The expected continuous answer is particularly clean. For every \(g\ge3\),
\[ \sup_\mu R_g(\mu)=\frac{g}{g-2}. \]
The upper bound follows directly from Theorem 1 because it is independent of \(n\), and the paper’s LP/path-covering proof can be read after normalizing multiplicities into masses. The greedy assignment and the benchmark transportation LP are both polynomial-time computable in \(m\), \(\tau\), and the input bit length. This is a Class A mirror.
For \(g=1\) and \(g=2\), the unrestricted continuous worst-case ratio is unbounded as the number of types grows. The finite \(n\)-dependent bounds do not become constant merely because the population has been normalized. This is itself an informative continuization: population size disappears, while the number and geometry of distinct cohorts become the relevant parameters.
A second anchor is Theorem 3, also proved in this paper. Its first three statements give matching lower bounds: without augmentation, Serial Dictatorship has ratio at least \(2^n-1\); with \(g=2\), at least \(\log(n+1)\); and for every \(g\ge3\), at least \(g/(g-2)-\delta\) for every \(\delta>0\).
Its continuous problem is Continuous Serial-Dictatorship Worst-Case Witness: given \(g\), \(\delta>0\), and an allowed type bound \(K\), construct a finite-support mass society with at most \(K\) types whose ratio is at least the relevant target.
The paper’s line-metric construction transfers directly. For levels \(i=0,\ldots,k-1\), put a type mass proportional to
\[ \ell_i=g^{k-i-1} \]
at location \(2^i\). Put facilities at \(-\varepsilon,1,2,\ldots,2^k\), with capacities proportional to \(c_i=\ell_i\) for \(i<k\) and \(c_k=1\). Process the levels in increasing order. Serial Dictatorship sends level \(i\) to facility \(i+1\), while the optimum sends it to facility \(i\). After normalizing all masses and capacities by their total, the ratio is unchanged. Letting \(k\) grow and \(\varepsilon\) shrink yields the stated lower bounds. Repeating every cohort many times makes the population arbitrarily large without increasing the number of distinct types.
This second problem is also Class A: the witness is explicit. It establishes that the \(g\ge3\) constant is tight and that no population-size-independent guarantee exists for \(g=1\) or \(g=2\) when the type support is unrestricted.
The mirror covers Theorem 1 and the first three clauses of Theorem 3. I would not stretch it to cover the paper’s Random Serial Dictatorship bounds or Theorem 4’s impossibility result for all truthful mechanisms. A literal atomless truthfulness notion is problematic: one individual has zero mass and cannot change the aggregate distribution, so individual incentive constraints become vacuous. The honest interpretation is therefore the finite-replication semantics above: every rational mass instance corresponds to a large finite truthful Serial Dictatorship instance, and the continuous question concerns its normalized performance.
That is the weakest point. A sceptic can say that the mirror is compressed finite replication rather than a fundamentally new mechanism. But that is precisely the high-multiplicity bridge the programme is meant to study. The paper’s problem survives intact—metric assignment, capacities, greedy Serial Dictatorship, resource augmentation, and social cost—while population size is replaced by type masses. The resulting question exposes a meaningful boundary: augmentation \(g\ge3\) yields a sharp constant guarantee, whereas \(g=1,2\) retain arbitrarily bad behaviour through increasingly rich type structure.
The strongest negative case is that Serial Dictatorship is intrinsically sequential. Its operative input is a total order of named agents, so the proponent’s “position in the fixed order” is not innocuous: it is a mechanism-relevant type coordinate. If exact position is included in the type, no type has high multiplicity. If it is discarded and equal types are processed as a mass block, the object becomes a new batched mechanism, and literal atomless truthfulness becomes vacuous.
That objection applies to both anchors. Theorem 1 concerns the performance of the sequential truthful mechanism, while Theorem 3’s lower-bound construction relies on carefully ordered level blocks. Repeating each level does not preserve the original model unless one explicitly adds a block-priority convention. Thus the proposed mirror should not be advertised as literal atomless Serial Dictatorship or as preserving the paper’s incentive theorem.
However, this does not defeat the better mirror. One can make priority a genuine population attribute and define types by \((a_t,\rho_t)\), or restrict to natural cohorts processed in contiguous priority blocks. For rational masses, clearing denominators produces a finite replicated instance whose normalized greedy cost and optimal cost are exactly the mass quantities. The lower-bound construction already consists of such cohorts. Hence this is a legitimate high-multiplicity regime, not merely a formal trick.
Nor can the anchors be dismissed as noncomputational: Theorem 1 is a named approximation analysis, and Theorem 3 gives constructive worst-case witnesses. The mass greedy assignment and capacity-constrained transportation benchmark are well-defined computational problems. Their answers being inherited from finite replication is not an admissible objection under the programme’s bridge.
So the honest negative case is weak. It supplies an important modelling warning—do not claim a literal atomless truthful mechanism, and state the priority/batching semantics explicitly—but it does not defeat either Theorem 1 or Theorem 3. A worthwhile continuous mirror survives.
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.