| paper | Welfare-Optimal Serial Dictatorships Have Polynomial Query Complexity |
| authors | Ioannis Caragiannis, Kurt Mehlhorn, Nidhi Rathi |
| venue | AAAI 2025 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4.2
statement extracted from the paper’s text layer
Given publicly known household types T, apartment types J, rational household masses μ and apartment capacities ν, but hidden common values and tie-breaking orders for each type, with an oracle that returns the apartment type and value chosen by type t after any finite rational prefix mass schedule, compute a welfare-maximizing finite block serial-dictatorship schedule using a number of queries polynomial in |T|, |J|, and encoding length, independent of the cleared-denominator population size.
A publicly typed, high-multiplicity housing market with household mass, apartment-type capacities, hidden common type valuations, type-level favorite-available queries, and welfare-maximizing mass schedules.
The proposed type-level oracle exposes common type classes and replaces named-agent prefixes with residual-capacity mass states, so Theorem 4.2 does not transfer automatically or preserve query transcripts.
fatal: False
The mirror targets Theorem 4.2 and uses Theorems 4.3 and Lemma 4.6 as structural ingredients; it leaves the cited structural Theorem 4.1, VCG implementation, lower bounds, and generalizations untreated.
The strongest positive case is a high-multiplicity housing-allocation mirror, anchored on Theorem 4.2, which is proved in this paper:
“For \(n\)-agent OSM instances with query access, Algorithm 1 uses \(O(n^5)\) queries to compute a welfare-optimal action sequence.”
I would not add Theorem 4.1 as a second anchor: it is cited from Caragiannis and Rathi (2024), and is structural rather than a new computational result. Theorem 4.3, Lemma 4.6, and Lemma 4.8 are valuable ingredients in the proof of Theorem 4.2, but not separate anchors.
Consider a large municipality assigning a standardized housing supply. There are \(\tau\) household types and \(q\) apartment types. A household type \(t\) is its complete value vector \(v_t=(v_{t1},\ldots,v_{tq})\), together with its tie-breaking order over apartment types. Apartment type \(j\) has capacity \(\nu_j\), and household type \(t\) has mass \(\mu_t\), with
\[ \sum_t\mu_t=\sum_j\nu_j=1. \]
The masses are rational. A typical instance might have hundreds of thousands of households but only a few dozen household types and apartment types. The types could encode standardized household profiles and the apartment features relevant to them. Nothing query-relevant is being suppressed: if two households differ in value, price, budget, or tie-breaking, they are different types.
The natural continuous problem is:
Mass-OSM Query. The input consists of \((\mu,\nu)\) and oracle access to the unknown values and rankings. A mass action sequence is an ordering of the unit mass of households, represented by a measurable type-labelled sequence \(S:[0,1]\to[\tau]\) whose type-\(t\) set has measure \(\mu_t\). At each point in the sequence, that infinitesimal household receives its highest-ranked apartment type with remaining capacity. Let \(y_{tj}(S)\) be the resulting mass assigned from household type \(t\) to apartment type \(j\). Its welfare is
\[ W(S)=\sum_{t,j} y_{tj}(S)v_{tj}. \]
A query \(Q(t,\rho)\) supplies a finite rational prefix \(\rho\) of a mass action sequence and asks for the next household of type \(t\). The oracle returns the apartment type \(j\) chosen and its value \(v_{tj}\), exactly mirroring the paper’s \(Query(i,S)\). The task is to output a mass action sequence \(S^\star\) maximizing \(W(S)\), using as few oracle queries as possible. An optimal schedule can be represented as a finite rational block sequence; only finitely many apartment capacities can become exhausted, so intervals with no change in available choices can be coalesced.
This is recognisably the authors’ problem. It preserves the complete bipartite assignment setting, greedy serial dictatorship, welfare maximization, and the restrictive favorite-available query model. It merely replaces repeated, interchangeable rows and columns by masses. It is also directly connected to their housing example: the paper already describes citizens choosing among apartment types such as balcony, sunlight, or view.
The high-multiplicity bridge is exact. For every \(N\) clearing the denominators, create \(N\mu_t\) named households of type \(t\) and \(N\nu_j\) copies of apartment type \(j\). A rational mass schedule expands to a named action sequence, and its per-capita welfare is exactly the continuous welfare. Conversely, projecting any such discrete action sequence onto types gives a mass schedule. Thus the question is not “can we fractionalize the allocation?” It is whether the hidden \(N\times N\) valuation structure can be compressed to the \(\tau q\) distinct type–item values.
I expect Mass-OSM Query to be Class A. The proof of Theorem 4.2 already maintains an overestimating proxy graph, learns only information needed for optimality, and progresses through three finite events: discovering an unknown edge, tightening a proxy value, or resolving a ranking tie. In the mass version, the unknown edge set becomes the \(\tau q\) type–item pairs rather than the \(n^2\) named pairs. The matching subroutine becomes a capacitated or transportation version, and the output is a serializable mass schedule. The natural conjecture is therefore an exact query algorithm polynomial in \(\tau,q\), and the value encoding length, independent of the population size \(N\). A bound such as \(O((\tau q)^5)\) is plausible, though it is not claimed by this paper.
The main new questions would be whether the proxy/potential argument survives arbitrary fractional interleaving of types; what the optimal dependence on \(\tau\) and \(q\) is; whether there is an \(\Omega(\tau q)\) query lower bound; and how the continuous schedule rounds to an exact sequence for a finite \(N\)-copy market. One could also study a parameterized regime with a small number of exceptional households whose values are not type-shared.
The weakest point is that Theorem 4.2 itself does not imply this result. Its oracle names an individual agent and its proof counts progress over individual agent–item edges. The mass problem needs a genuinely new type-level oracle and a proof that fractional type schedules do not introduce extra complexity. A referee could therefore say that this is a high-multiplicity reformulation rather than an immediate continuous corollary.
That weakness is real, but it is also exactly the research opportunity. The reformulation does not trivialize serial dictatorship or replace the authors’ question by an easier welfare LP: the action sequence remains the decision variable, values remain hidden behind the same restrictive query interface, and the goal remains to find a welfare-optimal greedy sequence. The proposed mirror covers one concrete result emphatically—Theorem 4.2—and asks whether its central query-compression phenomenon becomes stronger, rather than disappearing, when the population itself is treated as a distribution over types.
The only serious anchor is Theorem 4.2, and the strongest objection is that it is not fundamentally a population theorem. It is a theorem about information acquisition from a black-box oracle over named agents and named items. The algorithm’s potential function tracks individual agent–item edges and individual rankings; the population size \(n\) is simply the number of hidden rows and columns.
That matters for the proposed Mass-OSM. In the paper, the algorithm is not told which agents are identical. Since values and rankings are hidden, the type partition is an ex-post property of the instance. A genuine high-multiplicity compression therefore needs extra information: public type labels, an equality oracle, or a type-level query oracle. If the labels are absent, discovering the repeated types may itself require population-scale querying. If they are supplied, the proposed \(Q(t,\rho)\) is no longer a reformulation of \(Query(i,S)\); it is a new information model that grants the algorithm access to equivalence classes the paper never provides.
The continuous sequence also changes the mechanism at its core. An infinitesimal household has zero effect on residual capacity, so a literal pointwise sequence \(S:[0,1]\to[\tau]\) does not behave like the paper’s sequential process. The natural repair is a block or fluid process whose oracle is queried after a residual-capacity vector. That is coherent, but it is a new capacitated elicitation problem, not a limit theorem for Theorem 4.2. Denominator clearing preserves welfare and allocations, but it does not by itself preserve the query transcripts or the information available to the algorithm.
The proponent’s strongest rescue is therefore to declare household types and apartment types publicly, retain hidden common values within each type, and define a type-level residual-capacity oracle. That is a sensible high-multiplicity problem, but its central theorem would have to be proved from scratch. The paper’s \(O(n^5)\) argument gives no \(O((\tau q)^5)\) replacement: fractional interleaving, capacity exhaustion, ties, and the reachability of type–item values all change the state space. Once values are known, the problem is simply a finite capacitated matching problem whose optimum can be serialized; the genuinely difficult part is the newly designed oracle, not continuization.
This is a real objection to calling Mass-OSM a direct mirror of the paper. It is not, however, a successful universal negative. Standardized household types with publicly known categories and hidden common valuations are plausible, and the resulting type-level query problem is computationally meaningful even if it is a new theorem. Thus the honest negative verdict is weak: Theorem 4.2 does not transfer automatically, but the proposed high-multiplicity housing mirror survives as a worthwhile research question.
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.