| paper | Yankee Swap: A Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations |
| authors | — |
| venue | AAMAS 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 3.5
statement extracted from the paper’s text layer
Given finite \(G\), rational per-capita seat capacities \(q_g\), finite complete student types \(T\) with matroid-rank valuation oracles \(v_t\), and rational masses \(\mu_t\), compute finite-support configuration masses \(\lambda_{t,B}\ge0\) over integral independent bundles \(B\subseteq G\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}\lambda_{t,B}\le q_g\), such that the increasing utility-quantile curve induced by \(v_t(B)\), with an optional fixed finite type-priority perturbation, Lorenz-dominates that of every feasible allocation \(\lambda'\).
A repeated-seat course market with finite student types \(T\), population masses \(\mu_t\), capacities \(q_g\), integral matroid-independent bundles \(B\), configuration variables \(\lambda_{t,B}\), and a Lorenz or type-priority-refined fairness objective.
A finite type-level priority refinement is not equivalent to Theorem 3.5's arbitrary named-agent priority permutation, so the mirror does not preserve the theorem's full identity-sensitive statement exactly.
fatal: False
The mirror covers the Lorenz-dominating allocation result of Theorem 3.5 in a repeated-seat course-allocation regime. It leaves Theorems 3.9 and 3.10's concrete-agent transfer-path and runtime claims, arbitrary one-off goods, non-MRF valuations, and randomized strategyproofness untreated.
The strongest honest positive case is a high-multiplicity course-allocation mirror of Yankee Swap. It is narrow, but it is recognisably the authors’ problem: many students, repeated course-seat supplies, and recurring matroid-rank preference types.
Take \(G=\{g_1,\ldots,g_m\}\) to be course or section classes. Each class \(g\) has supply \(q_g\) seats per unit population. Let \(T\) be a finite set of complete student types. A type \(t\) includes the entire matroid-rank valuation \(v_t\), including scheduling, prerequisite, major, and course-limit constraints. The population is \(\mu=(\mu_t)_{t\in T}\), where \(\mu_t\) is the fraction of students of type \(t\), \(\sum_t\mu_t=1\), with \(N\gg |T|\).
This is a genuine high-multiplicity regime: a large university may have tens of thousands of students but only a moderate number of recurring schedule-and-degree types. Course seats remain individually indivisible. The continuous object is only the population. An infinitesimal student receives an integral bundle of courses, not a fractional bundle.
Formally, let \(\lambda_{t,B}\) be the mass of type-\(t\) students receiving the integral bundle \(B\subseteq G\). We restrict to independent bundles, \(v_t(B)=|B|\), so allocations are non-redundant in the paper’s sense. Feasibility is
\[ \sum_B\lambda_{t,B}=\mu_t \]
for every \(t\), and
\[ \sum_{t,B:g\in B}\lambda_{t,B}\le q_g \]
for every course class \(g\). Thus \(\lambda\) is a distribution of students over integral bundles, not fractional ownership of goods.
For an allocation \(\lambda\), let \(Q_\lambda:[0,1]\to\mathbb{R}_{\ge0}\) be the increasing utility quantile function induced by the masses \(\lambda_{t,B}\). The natural continuous Lorenz objective is to find \(\lambda\) such that, for every feasible \(\lambda'\) and every \(a\in[0,1]\),
\[ \int_0^a Q_\lambda(z)\,dz \;\ge\; \int_0^a Q_{\lambda'}(z)\,dz. \]
For rational \(\mu\), \(q\), and \(\lambda\), clearing denominators produces a finite election with many identical student types and many repeated seat copies. Conversely, aggregating such a finite allocation gives \(\lambda\). This is therefore an exact high-multiplicity dictionary, not merely an analogy.
My lead anchor is Theorem 3.5, proved in this paper: “When agents have MRF valuations, Yankee Swap computes a non-redundant Lorenz dominating allocation with respect to the priority order \(\pi\).”
The corresponding problem is:
Typed Lorenz-Dominating Allocation\(_\infty\). Given \(G\), \(T\), rational masses \(\mu_t\), rational seat supplies \(q_g\), and rank-oracle access to each \(v_t\), output a finite-support table \(\lambda_{t,B}\) satisfying the feasibility constraints above and whose utility quantile curve Lorenz-dominates that of every feasible allocation. If no such allocation exists, output NO.
I expect this to be Class A. The configuration formulation has exponentially many bundle variables, but its natural pricing problems are matroid optimization problems. With item prices \(p_g\), the basic welfare pricing query is a maximum-weight independent-set problem in the type’s matroid; fixed-cardinality versions are minimum-cost basis problems. Both are solvable by greedy matroid algorithms with oracle access. Leximin or Lorenz optimization can then proceed through a polynomial number of utility levels, using column generation or a separation-oracle formulation.
The paper’s priority order requires care. A unique priority permutation over named students does not survive compression when \(N\) is much larger than \(|T|\). I would therefore mirror the core Lorenz-dominance conclusion and treat priority as an optional type-level tie-break or random refinement. This loses only the identity-level choice among allocations with the same sorted utility vector; it does not discard the central fairness or efficiency objective.
A smaller secondary anchor is Theorem 3.9, proved here: given a non-redundant allocation, a transfer path exists from agent \(i\) to agent \(j\) if and only if Algorithm 2 outputs one, and the returned path is a valid transfer path.
Its continuous counterpart is:
Typed Mass-Transfer-Path\(_\infty\). Given a feasible mass allocation \(\lambda\), a target type \(t^\star\) currently holding bundle \(B^\star\), and residual seat supplies, decide whether some positive mass \(\epsilon>0\) can be transferred along a chain so that a type-\(t^\star\) student gains one unit of utility, every intermediate student preserves utility, and the final step uses an unallocated seat. If so, output the chain and the maximum feasible \(\epsilon\).
The exchange graph has one vertex for each course class. There is an edge \(g\to h\) whenever some positive-mass type-\(t\) bundle \(B\ni g\) can replace \(g\) by \(h\) without changing \(v_t(B)\). The source connects to goods that give the target bundle marginal value \(1\); the sink consists of goods with residual supply. Breadth-first search finds a path, and the transferable mass is the minimum of the relevant bundle masses and final residual supply. This is a direct population version of the paper’s transfer-path mechanism, and I again expect Class A.
The paper’s Theorem 3.10, proved here, gives the finite-agent runtime \(O(m^2(n+\tau)(m+n))\), where its \(\tau\) is valuation-oracle time. It does not itself prove the compressed bound, but it identifies exactly what the continuous programme would need to replace: dependence on the number of named students by dependence on the number of distinct types, input bit length, and oracle time. The target bound would be \(\operatorname{poly}(m,|T|,L,\rho)\), independent of \(N\).
This mirror covers the paper’s main Lorenz-allocation theorem and its exchange-path implementation. It does not claim to cover arbitrary one-off goods, arbitrary non-MRF valuations, or the strategyproofness of the randomized prioritized egalitarian mechanism. Theorem 2.2 is cited from Babaioff et al. [2], not proved in this paper; I treat its MNW, MAX-USW, EFX, leximin, and \(1/2\)-MMS consequences as motivating guarantees rather than separate anchors.
The weakest point is that scaling course-seat supply with population changes the regime from one-off goods to repeated seat classes, and a type-compressed Lorenz algorithm is not proved by the paper. If the application truly has a fixed set of unique objects while the population grows, the limit degenerates and I would not defend that mirror. But repeated course seats are an actual, natural allocation environment, the aggregate model has an exact finite-clone interpretation, and matroid pricing gives a credible route to a Class A result.
The strongest negative case is that the only non-degenerate mirror changes the paper’s resource model. If the goods \(G\) remain fixed while the population grows, at most \(|G|\) agents can receive a positive-valued bundle. Thus the positive-utility mass is \(O(|G|/N)\), and in the limit \(Q_\lambda(z)=0\) almost everywhere. Lorenz dominance becomes vacuous, and every transfer path moves zero limiting mass. On the literal population-only reading, all three anchors therefore degenerate.
The proponent’s repair—scaling each course’s supply with population—avoids that collapse, but it replaces the paper’s set of indivisible goods by a capacitated multi-unit market. The original matroid is on named goods, and the exchange graph has one vertex per good; the proposed model instead needs parallel course-seat copies, a quotient by their symmetry, and new matroid semantics for those copies. Denominator clearing proves an exact correspondence with finite instances of this new repeated-seat model, not with high-multiplicity clones of the paper’s original instance. That is a legitimate allocation problem, but it is an extension rather than a continuous mirror of Yankee Swap.
This is especially damaging to Theorem 3.5. Its distinctive conclusion is prioritized Lorenz dominance. A priority permutation over named agents is part of the effective type: if it is retained, then clones with different priorities are different types and \(|T|\) grows with \(N\). If it is discarded, the proposed problem asks only for anonymous Lorenz dominance and loses the theorem’s priority-sensitive output. A type-level tie-break is not equivalent to the original permutation, while random priorities in an atomless population can be purified by partitioning mass, erasing the finite distinction between ex ante and ex post fairness. The remaining typed repeated-seat problem may be interesting, but it is no longer the paper’s central prioritized result.
Nor does matroid pricing by itself establish the proposed Lorenz algorithm. Greedy matroid optimization prices a single independent bundle under additive dual weights. Quantile Lorenz optimization additionally has to coordinate lower-tail utility mass, item capacities, and the decomposition of each type’s population over integral bundles. That may admit a polymatroid or configuration-LP treatment, but the required separation and finite-support representation are new results, not consequences of Theorem 3.5.
Theorem 3.9 fares worse. The finite exchange graph is defined using the current owner of each concrete good. In the mass formulation, an edge \(g\to h\) may be witnessed by one positive-mass configuration, while the next edge \(h\to k\) is witnessed by another. A graph on course classes forgets which configuration owns the transferred copy of \(h\), and can concatenate locally valid witnesses that do not form one feasible mass transfer. To repair this, one needs a typed configuration-state network with conservation constraints and a bottleneck calculation for every participating mass. That is a mass-flow problem, not the paper’s BFS theorem. Moreover, “one agent gains one unit” has no atomless analogue: a positive-\(\epsilon\) move benefits a coalition, whereas an infinitesimal move benefits zero measure. The proponent’s target problem therefore changes both the certificate and the operation being certified.
Theorem 3.10 does not rescue the construction. Its runtime counts an explicit allocation matrix, named-agent ownership lookups, and transfers along concrete goods. A type-compressed representation has no such matrix; its cost depends instead on the number of supported configurations, their rational encoding lengths, and the data structure used to separate or price them. The theorem gives no bound independent of \(N\), and replacing \(n\) by \(|T|\) is precisely the unproved part. If priority is preserved, \(T\) again contains the named agents; if it is removed, the algorithm is solving a different problem.
So the negative conclusion is defensible under the strict population-only interpretation: fixed indivisible supply makes the mirror trivial, while supply scaling, anonymous Lorenz objectives, and typed exchange flows jointly produce a new repeated-resource allocation programme. It is not, however, an airtight universal case. The repeated course-seat model is author-recognizable and has an exact rational-clone interpretation. The honest assessment is that the negative case defeats the three proposed anchors as direct mirrors, but cannot convincingly show that no worthwhile high-multiplicity extension exists.
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.