Answer: Both the unperturbed and fixed-priority versions are solvable in time polynomial in \(m,\tau,L,c\).
Theorem 3.5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateWhen agents have MRF valuations, Yankee Swap computes a non-redundant Lorenz dominating allocation with respect to the priority order 𝜋.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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'\).
Let \(G\) be a finite set of \(m\) goods. A society is given by its support: a list \(T\) of \(\tau\ge1\) complete types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) counts listed types, not all possible types. Each type specifies a matroid-rank valuation oracle \(v_t\) on \(G\). Capacities \(q_g\ge0\) are binary rationals; \(L\) is the total explicit input bit length, and each oracle query costs at most \(c\).
Use either unperturbed utilities, with \(\delta_t=0\), or a supplied priority permutation \(\pi:T\to\{1,\ldots,\tau\}\), with lower numbers indicating higher priority and \(\delta_t=\pi(t)/\tau^2\).
A feasible allocation consists of finitely many nonzero rational configuration masses \(\lambda_{t,B}\ge0\), where \(B\subseteq G\) is independent for type \(t\), satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and \(\sum_{t,B:g\in B}\lambda_{t,B}\le q_g\). Empty bundles and unused capacity are allowed; each student receives at most one seat of each good.
Let \(Q_\lambda\) be the increasing quantile function of the utility distribution assigning mass \(\lambda_{t,B}\) to \(v_t(B)+\delta_t\), and set \(C_\lambda(a)=\int_0^a Q_\lambda(s)\,ds\). An allocation is Lorenz dominating if \(C_\lambda(a)\ge C_{\lambda'}(a)\) for every \(a\in[0,1]\) and every feasible \(\lambda'\).
Is computing a Lorenz-dominating allocation polynomial-time in \(m,\tau,L,c\), or is it NP-hard, for the unperturbed and fixed-priority versions?
For finitely many individual agents, Yankee Swap computes a non-redundant prioritized Lorenz-dominating allocation in \(O(m^2(n+c)(m+n))\) time, where \(n\) is the number of agents ([Viswanathan–Zick](https://arxiv.org/pdf/2206.08495)).
No result settling this exact configuration-mass problem was identified in the literature search.
Both the unperturbed and fixed-priority versions are polynomial-time solvable in \(m,\tau,L,c\). A Lorenz-dominating allocation always exists, and one can compute a rational allocation having at most \(m+\tau\) positive configuration masses.
The proof has two separate parts: existence follows from a finite-population matroid argument; computation uses a configuration linear program with polynomial-time dual separation. The algorithm does not expand the rational masses into individual agents.
Let \(\mathcal I_t\) denote the independent sets of type \(t\)'s matroid. Because configurations are independent, \(v_t(B)=|B|\) for \(B\in\mathcal I_t\).
For an allocation \(\lambda\), let \(U_\lambda\) be its utility random variable. For a real threshold \(z\), define
\(F_z(\lambda)=\mathbb E[\min\{U_\lambda,z\}]=\sum_{t,B\in\mathcal I_t}\lambda_{t,B}\min\{|B|+\delta_t,z\}.\)
These are linear functions of the configuration masses.
The following identities connect them to the Lorenz curve:
\(C_\lambda(a)=\sup_{z\in\mathbb R}\bigl(F_z(\lambda)-(1-a)z\bigr),\)
\(F_z(\lambda)=\inf_{a\in[0,1]}\bigl(C_\lambda(a)+(1-a)z\bigr).\)
To verify them, write \(Q=Q_\lambda\). For every \(a,z\),
\(az-C_\lambda(a)=\int_0^a(z-Q(s))\,ds\le\int_0^1(z-Q(s))_+\,ds=z-F_z(\lambda).\)
Equality holds when \(z\) is an \(a\)-quantile. At the endpoints, choose \(z\) below every utility when \(a=0\), and above every utility when \(a=1\). Conversely, for fixed \(z\), equality holds upon choosing \(a=\Pr(U_\lambda<z)\). This proves both identities.
Consequently, Lorenz dominance is equivalent to simultaneous maximization of every \(F_z\).
Only polynomially many thresholds are needed. Define
\(H=\{k+\delta_t:t\in T,\ k\in\{0,\ldots,m\}\}.\)
Every attainable utility belongs to \(H\), and \(|H|\le\tau(m+1)\). As a function of \(z\), each \(F_z(\lambda)\) is linear between consecutive elements of \(H\). Below its smallest element it equals \(z\); above its largest element it equals \(\mathbb E[U_\lambda]\). Therefore,
\(F_h(\lambda)\ge F_h(\lambda')\text{ for every }h\in H\quad\Longrightarrow\quad C_\lambda(a)\ge C_{\lambda'}(a)\text{ for every }a\in[0,1].\)
We next prove that the capped objectives have a common maximizer.
Lemma. Suppose finitely many agents have matroids on a common finite set \(E\). Agent \(i\)'s utility from an independent bundle \(B_i\) is \(|B_i|+b_i\), where the offsets \(b_i\) are fixed real numbers. Bundles must be pairwise disjoint; empty bundles and unassigned goods are allowed.
There is an allocation simultaneously maximizing
\(\sum_i\min\{|B_i|+b_i,z\}\)
for every real \(z\).
In particular, offsets may coincide. This will allow all copies of a type to retain exactly the supplied type offset.
Let \(N\) be the finite agent set, and let \(r_i\) be agent \(i\)'s matroid rank function. For \(S\subseteq N\), define
\(f(S)=\min_{A\subseteq E}\left(|E\setminus A|+\sum_{i\in S}r_i(A)\right).\)
We claim that a nonnegative integer vector \(x=(x_i)_{i\in N}\) is realizable as the sizes of pairwise disjoint independent bundles precisely when
\(x(S):=\sum_{i\in S}x_i\le f(S)\qquad\text{for every }S\subseteq N.\)
Necessity. Given such bundles, for every \(S,A\),
\(\sum_{i\in S}|B_i|\le |E\setminus A|+\sum_{i\in S}r_i(A).\)
Indeed, at most \(|E\setminus A|\) assigned goods lie outside \(A\), while \(|B_i\cap A|\le r_i(A)\). Taking the minimum over \(A\) proves necessity.
Sufficiency. Truncate agent \(i\)'s matroid at cardinality \(x_i\); its rank on \(A\) becomes \(\min\{r_i(A),x_i\}\). The matroid-union theorem states that the largest union of independent sets of these truncated matroids has cardinality
\(\min_{A\subseteq E}\left(|E\setminus A|+\sum_i\min\{r_i(A),x_i\}\right).\)
The theorem applies because all truncations are matroids on the same finite ground set. See [Oxley, *Matroid Theory*, Theorem 11.3.1 and formula 11.3.3](https://www.math.ens.psl.eu/~benoist/refs/Oxley.pdf#page=440).
For a fixed \(A\), put \(S_A=\{i:x_i>r_i(A)\}\). The assumed inequalities give
\(\sum_{i\in S_A}x_i\le f(S_A)\le |E\setminus A|+\sum_{i\in S_A}r_i(A).\)
Equivalently,
\(|E\setminus A|+\sum_i\min\{r_i(A),x_i\}\ge\sum_i x_i.\)
Thus the union has cardinality \(\sum_i x_i\). Its constituent independent sets can be made disjoint by deleting overlaps. Since each constituent has size at most \(x_i\), a union of cardinality \(\sum_i x_i\) forces their sizes to be exactly \(x_i\). This establishes sufficiency.
The function \(f\) is nonnegative, integer-valued, monotone, and satisfies \(f(\varnothing)=0\). These facts follow directly from its definition.
It is also submodular. Write
\(\Phi(S,A)=|E\setminus A|+\sum_{i\in S}r_i(A).\)
For \(S_1,S_2\subseteq N\), choose minimizing sets \(A_1,A_2\). Rank submodularity and monotonicity imply
\(\Phi(S_1,A_1)+\Phi(S_2,A_2)\ge \Phi(S_1\cup S_2,A_1\cap A_2)+ \Phi(S_1\cap S_2,A_1\cup A_2).\)
Here agents in \(S_1\cap S_2\) contribute the rank-submodularity inequality. An agent belonging only to \(S_1\) contributes \(r_i(A_1)\ge r_i(A_1\cap A_2)\), and similarly for \(S_2\). The two complement-cardinality terms satisfy equality.
Taking the respective minima on the right yields
\(f(S_1)+f(S_2)\ge f(S_1\cup S_2)+f(S_1\cap S_2).\)
Introduce slots
\(V=\{(i,k):i\in N,\ 1\le k\le r_i(E)\}.\)
For \(I\subseteq V\), let \(x_i(I)\) be the number of slots of agent \(i\) contained in \(I\). Declare \(I\) independent when
\(x(I)(S)\le f(S)\qquad\text{for every }S\subseteq N.\)
We verify that this defines a matroid. The empty set is independent, and independence is hereditary. It remains to prove augmentation.
Let \(I,J\) be independent with \(|I|<|J|\). Suppose no slot in \(J\setminus I\) can be added to \(I\). For each such slot belonging to agent \(i\), some set \(S_i\) containing \(i\) must be tight:
\(x(I)(S_i)=f(S_i).\)
This follows because both sides are integers, and adding that slot increases the left side by one.
Tight sets are closed under union. Indeed, if \(A,B\) are tight, then feasibility and submodularity give
\(f(A)+f(B)=x(I)(A\cup B)+x(I)(A\cap B)\le f(A\cup B)+f(A\cap B)\le f(A)+f(B).\)
Thus both \(A\cup B\) and \(A\cap B\) are tight.
Let \(S\) be the union of the selected tight sets. Every slot of \(J\setminus I\) belongs to an agent in \(S\). Therefore, outside \(S\), the slots of \(J\) are a subset of those of \(I\). Inside \(S\),
\(x(J)(S)\le f(S)=x(I)(S).\)
Adding these inequalities gives \(|J|\le|I|\), a contradiction. Hence augmentation holds.
By Section 2.1, an independent slot set corresponds exactly to a feasible bundle-size vector.
Order the slots by increasing
\(b_i+k-1,\)
breaking ties arbitrarily, and run the ordinary matroid greedy algorithm in this order: accept a slot whenever independence is preserved. Let \(I^\star\) be its output.
For a threshold \(z\), assign slot \((i,k)\) the weight
\(w_z(i,k)=\min\{b_i+k,z\}-\min\{b_i+k-1,z\} =\min\{1,\max\{0,z-(b_i+k-1)\}\}.\)
These weights are nonnegative and nonincreasing in the chosen slot order, for every \(z\).
For completeness, greedy maximizes any such weight sequence. Let the ordered slots be \(e_1,\ldots,e_s\), and let \(R_j=\{e_1,\ldots,e_j\}\). Greedy's accepted slots in \(R_j\) form a maximal independent subset of \(R_j\), hence have maximum possible cardinality by augmentation. Thus, for any independent \(J\),
\(|I^\star\cap R_j|\ge |J\cap R_j|.\)
For nonincreasing nonnegative weights \(w_1,\ldots,w_s\), with \(w_{s+1}=0\),
\(\sum_{e_j\in I^\star}w_j =\sum_{j=1}^s(w_j-w_{j+1})|I^\star\cap R_j| \ge\sum_{j=1}^s(w_j-w_{j+1})|J\cap R_j| =\sum_{e_j\in J}w_j.\)
Moreover, greedy accepts a prefix of each agent's slots. If one slot of an agent is rejected, its corresponding count increment is infeasible. Subsequent accepted slots only increase counts, so downward closure prevents any later slot of that agent from becoming feasible.
Let \(x_i^\star\) be the resulting prefix lengths. They are realizable by disjoint independent bundles. For any feasible size vector \(x\), its prefix slot set is independent, and telescoping gives
\(\sum_i\min\{b_i+x_i,z\} =\sum_i\min\{b_i,z\}+\sum_i\sum_{k=1}^{x_i}w_z(i,k).\)
Greedy's optimality therefore proves that \(x^\star\) maximizes this expression for every \(z\). This proves the lemma.
Let \(\mathcal P\) be the configuration polytope, temporarily allowing real masses. It has finitely many variables and rational constraints. It is nonempty because every type can receive the empty bundle, and bounded because \(\lambda_{t,B}\le\mu_t\).
For each \(h\in H\), choose a rational maximizer \(\lambda^h\) of \(F_h\) over \(\mathcal P\). Such a maximizer exists because this is a bounded rational linear program with a rational objective.
Choose an integer \(D\) clearing the denominators of:
Construct a finite instance with \(D\mu_t\) agents of type \(t\), each retaining offset \(\delta_t\), and \(Dq_g\) copies of good \(g\). There are exactly \(D\) agents.
Each agent's matroid on copied goods is the parallel extension of its original matroid: a set of copies is independent precisely when it contains at most one copy of each original good and its projection is originally independent. This is a matroid, including when some goods have no copies.
Every \(\lambda^h\) is realizable in this instance. Assign \(D\lambda^h_{t,B}\) agents bundle \(B\), and give its occurrences distinct good copies. The capacity inequalities ensure that enough copies exist.
Apply the finite-population lemma. Its allocation maximizes every capped-utility sum and hence performs at least as well as every \(\lambda^h\). Aggregate its bundles by type and divide their counts by \(D\), obtaining a feasible rational configuration allocation \(\lambda^\star\). For every \(h\in H\),
\(F_h(\lambda^\star)\ge F_h(\lambda^h)=\max_{\lambda\in\mathcal P}F_h(\lambda).\)
Thus \(\lambda^\star\) simultaneously maximizes all the capped objectives. Section 1 implies that it Lorenz dominates every feasible allocation.
This replication establishes existence; it is not part of the algorithm.
Define the rational coefficients
\(A_t(k)=\sum_{h\in H}\min\{k+\delta_t,h\},\qquad 0\le k\le m.\)
Consider the configuration linear program with objective
\(\max_{\lambda\in\mathcal P}\sum_{t,B\in\mathcal I_t}A_t(|B|)\lambda_{t,B} =\max_{\lambda\in\mathcal P}\sum_{h\in H}F_h(\lambda).\)
Every optimum is Lorenz dominating. To see this, let \(M_h=\max_{\lambda\in\mathcal P}F_h(\lambda)\). Section 3 supplies a feasible allocation attaining every \(M_h\), so the optimum of the summed objective is \(\sum_hM_h\). At any optimum \(\widehat\lambda\), all deficits \(M_h-F_h(\widehat\lambda)\) are nonnegative and sum to zero. Each deficit is therefore zero. Section 1 then gives Lorenz dominance.
It remains to compute an optimum efficiently.
The dual has variables \(\alpha_t\in\mathbb R\) and \(p_g\ge0\), objective
\(\min\sum_t\mu_t\alpha_t+\sum_gq_gp_g,\)
and constraints
\(\alpha_t+\sum_{g\in B}p_g\ge A_t(|B|)\qquad(t\in T,\ B\in\mathcal I_t).\)
Given a candidate dual vector, first check \(p_g\ge0\). For each type, separation requires computing
\(\max_{B\in\mathcal I_t}\left(A_t(|B|)-\sum_{g\in B}p_g\right).\)
Sort the goods by increasing \(p_g\), and greedily accept a good whenever it preserves independence in type \(t\)'s matroid. Let the accepted sequence have prefixes \(B_{t,0},\ldots,B_{t,r_t}\), where \(r_t=v_t(G)\).
For every \(k\le r_t\), \(B_{t,k}\) is a minimum-weight independent set of cardinality \(k\). This is weighted matroid greedy applied to the rank-\(k\) truncation. More explicitly, use nonnegative weights \(K-p_g\), where \(K=\max_g p_g\): maximizing their sum over cardinality-\(k\) independent sets is equivalent to minimizing \(\sum_gp_g\).
Consequently, the required maximum equals
\(\max_{0\le k\le r_t}\left(A_t(k)-\sum_{g\in B_{t,k}}p_g\right).\)
If this exceeds \(\alpha_t\), the maximizing prefix supplies an actual violated dual constraint. Otherwise, every configuration constraint for that type is satisfied.
Independence is tested by one rank query: for an independent current set \(B\), the good \(g\) can be accepted precisely when \(v_t(B\cup\{g\})=|B|+1\). A separation call therefore uses at most \(\tau m\) rank queries, together with polynomially many rational operations.
We use the constructive rational-LP theorem for column access: a feasible linear program with bounded optimum, polynomially many rows, uniformly bounded coefficient encoding lengths, and a polynomial-time dual separation oracle returning violated original column constraints admits polynomial-time exact optimization and sparse primal recovery. The ellipsoid method identifies polynomially many relevant columns, after which a polynomial-size restricted primal is solved. This is the standard configuration-LP recovery described in [Roughgarden, Section 8.3.2, including footnote 9](https://www.nowpublishers.com/article/DownloadSummary/TCS-085#page=51).
All hypotheses hold here:
The objective coefficients also have polynomial encoding length. In both versions, \(0\le\delta_t\le1\), and \(|H|\le\tau(m+1)\). In the priority version all utility levels, and hence all \(A_t(k)\), have denominator dividing \(\tau^2\); in the unperturbed version the coefficients are integers. Their magnitudes are at most \(\tau(m+1)^2\).
Thus exact LP optimization takes time polynomial in \(m,\tau,L,c\), including oracle costs.
Finally, choose an optimal basic feasible solution of the recovered restricted primal. Adding capacity slacks gives \(m+\tau\) equality rows, so this solution has at most \(m+\tau\) positive configuration variables. Their rational encoding lengths are polynomial: basic solutions solve systems of order at most \(m+\tau\) with integer incidence coefficients and the supplied rational right-hand side.
The algorithm computes the possible utility levels, forms the summed capped-utility objective, and solves its configuration LP using weighted matroid greedy for dual separation. Every optimal allocation Lorenz dominates all feasible allocations.
The proof covers both \(\delta_t=0\) and the exact supplied offsets \(\delta_t=\pi(t)/\tau^2\), including repeated offsets among replicated agents and arbitrary positive rational type masses.
⟨structured verdict parsed — rendered above⟩
Assessment: proved with a minor edge-case omission. The argument establishes polynomial-time computability for both versions, including rational output with at most \(m+\tau\) positive configuration masses. No major mathematical or complexity gap was found.
Independence gives \(v_t(B)=|B|\), so the displayed capped objectives represent the specified utility distributions.
The integral inequality has the correct direction. Its equality conditions establish both variational identities, including distributions with atoms and the endpoints \(a=0\) and \(a=1\). Applying the supremum identity transfers capped-objective dominance to Lorenz dominance; applying the infimum identity establishes the converse.
The finite threshold reduction is valid. All attainable utilities lie in \(H\); between successive thresholds, differences of capped objectives are affine. Below the smallest threshold the objectives coincide, and above the largest threshold each objective equals its allocation’s mean utility. Thus checking every threshold in \(H\) suffices.
The necessity inequality correctly separates assigned goods inside and outside \(A\).
For sufficiency, truncation at each nonnegative integer \(x_i\) produces a matroid with the stated rank function. The matroid-union formula is accurately stated for a finite family on a common finite ground set, as confirmed by [Oxley, Section 11.3](https://www.math.ens.psl.eu/~benoist/refs/Oxley.pdf#page=440).
The choice \(S_A=\{i:x_i>r_i(A)\}\) makes the displayed rearrangement valid. Every expression in the union minimum is at least \(\sum_i x_i\), while the constituent truncations bound any union by that same quantity. Consequently, the maximum union has precisely the required size. Deleting overlaps preserves independence; attaining the sum of the individual size bounds forces all required sizes.
Nonnegativity, integrality, monotonicity, and normalization follow from the definition.
The uncrossing inequality uses the appropriate ground-set intersection for agents in the union and ground-set union for agents in the intersection. Shared agents contribute rank submodularity; agents appearing on only one side contribute rank monotonicity. The complement-cardinality terms balance exactly.
Taking minima on the right therefore proves the claimed submodularity inequality. There is no unsupported general assertion that an arbitrary minimum of submodular functions remains submodular.
Heredity follows directly from the count inequalities.
In the augmentation argument, integrality ensures that rejection identifies a tight constraint containing the slot’s agent. The displayed inequalities correctly prove closure of tight sets under union and intersection.
The union of the selected tight sets covers every slot in \(J\setminus I\). Outside that union, \(J\)’s slots are contained in \(I\)’s slots; inside it, feasibility and tightness give the required count comparison. This contradicts \(|I|<|J|\) and establishes augmentation.
Slots for agents of rank zero cause no difficulty.
The marginal-weight formula is valid for arbitrary real offsets and thresholds. Each marginal is nonnegative and decreases with the slot’s ordering key. Hence one order works for every cap, including tied offsets.
Greedy’s accepted set within each ordered prefix is maximal independent there. Augmentation justifies the maximum-cardinality assertion. The summation identity then establishes weight optimality for every nonincreasing nonnegative weight sequence.
Each agent’s slots occur in increasing slot index. A rejected count increment cannot become feasible after other counts increase, so the resulting slots form an agentwise prefix. The telescoping calculation correctly converts weight optimality into capped-utility optimality. The finite-population lemma is established.
The configuration polytope is finite-dimensional, nonempty, bounded, and rational. Each capped objective has rational coefficients, so a rational maximizer can be selected.
Only finitely many selected maximizers are involved. Their masses and the input masses and capacities therefore admit a common denominator \(D\).
The copied-good independence rule is the stated parallel-copy matroid construction, with absent goods omitted. It preserves the restriction of at most one seat of each original good per agent. Capacity inequalities ensure that each selected allocation can be realized using distinct copies.
Aggregation of the finite-population allocation produces rational feasible configuration masses. Normalizing the capped sums by \(D\) gives the displayed comparison with every individual threshold optimum.
The potentially enormous replication is used solely for existence. It does not undermine the algorithm’s polynomial-time claim.
Existence of a common maximizer is essential here and was established beforehand.
Every threshold deficit is nonnegative. At an optimum of the summed objective their sum is zero, forcing every deficit to vanish. Thus every optimum of this LP is Lorenz dominating.
The dual correctly uses unrestricted variables for type-mass equalities and nonnegative variables for capacity inequalities.
The minimum-price independent set of each cardinality is obtained by the corresponding greedy prefix. The rank-\(k\) truncation satisfies the hypotheses of weighted matroid greedy, and the stated change of weights preserves comparisons between cardinality-\(k\) sets.
Enumerating those prefixes therefore computes the exact maximum violation and returns an actual configuration constraint. The empty bundle is included through \(k=0\). The independence test is correct, and the greedy scans require at most \(\tau m\) such tests.
Minor issue: when \(m=0\), the expression \(K=\max_g p_g\) is undefined. The task does not exclude an empty ground set. The write-up should explicitly specify how the separation routine handles that case before introducing \(K\). This is a routine edge-case clarification, not a missing substantive argument.
The invoked configuration-LP recovery method is supported by [Roughgarden, Section 8.3.2 and footnote 9](https://www.nowpublishers.com/article/DownloadSummary/TCS-085#page=50): dual separation supplies polynomially many configuration columns from which a primal optimum can be recovered.
The application checks the relevant hypotheses: polynomially many rows, feasibility, bounded objective, bounded rational encoding lengths, compact column descriptions, and separation returning original column constraints.
The coefficient bounds are correct. Since \(0\le\delta_t\le1\), every summand has magnitude at most \(m+1\), yielding the stated bound \(\tau(m+1)^2\). The denominator claims also hold.
After adding capacity slacks, a basic feasible solution has at most \(m+\tau\) positive variables altogether, hence at most that many positive configuration variables. The incidence matrix and rational right-hand side give polynomial encoding lengths for their masses.
Required feedback: explicitly handle \(m=0\) in Section 4.1. No new lemma or substantive proof modification is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.