| paper | Towards Optimal Subsidy Bounds for Envy-Freeable Allocations |
| authors | — |
| venue | AAAI 2024 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 1
statement extracted from the paper’s text layer
Given rational masses over finitely many complete monotone additive valuation types, integral bundle classes built from repeated indivisible item copies with rational masses, and a baseline type–bundle incidence promised to be EF1, choose a mass-preserving reassignment of bundle classes and nonnegative subsidies for occupied type–bundle pairs so that every recipient weakly prefers its subsidized bundle to every other occupied recipient's bundle, minimizing total mass-weighted subsidy or maximum subsidy, and determine whether Theorem 1-style polynomial-time bounds hold.
A high-multiplicity repeated-item fair-division market with typed agents, bundle-copy classes, baseline incidence, transport variables for reassignment, and per-recipient-type subsidies constrained by envy-freeness.
The proposed transportation dual does not by itself optimize the stated mass-weighted subsidy and discards baseline type–bundle incidence, so neither the compact formulation nor K-based analogues of the n−1 bounds follow from Theorem 1.
fatal: False
The mirror covers Theorem 1's EF1-to-envy-free subsidy completion in a monotone repeated-item regime, while leaving Theorem 2's sharper bound, the EFk generalization, and the structural lemmas as separate results.
The strongest positive case is a high-multiplicity version of the paper’s subsidy-completion result, anchored on Theorem 1, proved in this paper. The theorem says that, for doubly monotone valuations or two agents, an EF1 allocation can be converted in polynomial time into an envy-free allocation with maximum subsidy at most \(n-1\) and total subsidy at most \(n(n-1)/2\).
The appropriate regime is a large allocation market: for example, a university assigning many indivisible course seats, or a public agency assigning large batches of indivisible housing or service slots. There may be hundreds of thousands of agents but only a few dozen or hundred complete valuation types. A type includes the entire additive valuation vector, eligibility restrictions, and any other feature used by the allocation problem. Agents of the same type are genuinely interchangeable. The item catalogue also has repeated classes of individually indivisible copies; a continuous supply is only the normalized count of copies, not a fractional item allocated to one person.
Here is the lead problem.
HM-EF-Subsidy Completion. The input consists of:
\[ v_t(B)=\sum_{e\in E}a_{t,e}B_e,\qquad 0\le a_{t,e}\le1; \]
The continuous allocation variable is \(y_{t,j}\): the mass of type-\(t\) agents receiving the whole indivisible bundle \(B_j\). It must satisfy
\[ \sum_j y_{t,j}=\mu_t,\qquad \sum_t y_{t,j}=\lambda_j,\qquad y_{t,j}\ge0. \]
Thus \(y\) merely counts how many agents receive each integral bundle. It does not split an item between agents. For every bundle class \(j\), choose a nonnegative subsidy \(p_j\). The output is envy-free if, whenever \(y_{t,j}>0\),
\[ v_t(B_j)+p_j\ge v_t(B_h)+p_h \]
for every bundle class \(h\). The objective can be to minimize the mass-weighted total subsidy \(\sum_j\lambda_jp_j\), or alternatively the maximum subsidy \(\max_jp_j\).
This is recognisably the paper’s problem: the multiset of bundles is preserved and agents receive bundles through a reassignment, exactly as Theorem 1 uses a maximum-weight permutation. In the discrete paper, the assignment subproblem is
\[ \max \sum_{i,j}v_i(A_j)x_{i,j}. \]
In the mirror, it becomes the capacitated transportation problem
\[ \max \sum_{t,j}v_t(B_j)y_{t,j}. \]
Its dual has variables \(q_t\) and \(p_j\):
\[ q_t-p_j\ge v_t(B_j),\qquad p_j\ge0. \]
Complementary slackness gives equality on every used pair, so a type receiving \(B_j\) obtains utility \(q_t\), which is at least its utility from every other available bundle. Hence the transportation solution and its dual subsidy vector are an envy-free allocation with subsidies. Exact rational solutions are computable in polynomial time in \(|T|+K+|E|\) and the input bit length.
I therefore expect this mirror to be Class A: tractable. The paper itself already exposes the relevant assignment dual: its proof of Lemma 2 says explicitly that \(p\) and \(q\) are dual variables of an assignment problem. Aggregating identical agents changes unit-capacity matching into transportation with masses; it does not change the underlying optimization machinery. In the unit-mass special case, the formulation reduces exactly to the paper’s assignment problem. With an EF1 baseline, one should expect the paper’s subsidy bounds to become bounds in terms of the number of occupied bundle classes \(K\), rather than the enormous number of named agents, with the total bound naturally weighted by bundle masses.
The high-multiplicity interpretation is also reversible. A rational solution can be scaled by a common denominator into a discrete market with many copies of each type and item class. Conversely, any such discrete allocation aggregates to the variables \(y_{t,j}\). The population is the continuous object; each realized agent still receives an indivisible bundle.
This case deliberately does not claim to mirror every result in the paper. It covers Theorem 1’s bundle-reassignment and subsidy-computation result in a monotone, repeated-type regime. Finding the initial EF1 allocation is a separate question; the continuous problem takes it as part of the input or as a promise, just as Theorem 1’s proof starts from one. I also would not claim, without a separate proof, that the exact \(n-1.5\) improvement of Theorem 2 survives unchanged under unequal masses.
The weakest point is genuine: Theorem 1’s proof is stated for a one-to-one permutation of named agents and bundles, whereas the mirror permits type mass to split across bundle classes and requires repeated item copies. A referee insisting on a fixed set of unique one-copy items could reasonably reject the continuum as degenerate: almost all agents would receive nothing. The mirror is persuasive only in the large-batch regime where repeated indivisible copies and repeated agent types are the actual application. Under that regime, however, the continuous problem is not a tractability-forced caricature. It is the paper’s own assignment-dual structure with the named-agent multiplicity removed.
The only serious anchor is Theorem 1, and it is not defeated by claiming that the paper lacks a computational result or that fair-division agents can never repeat. The best objection is that the proposed formulation does not actually preserve the theorem’s computational object.
Theorem 1 starts from a named-agent allocation \(A\). EF1 is defined relative to each agent’s own bundle, and the proof’s bound comes from the diagonal quantities
\[
\beta_i=\max_j(v_i(A_j)-v_i(A_i))\le 1.
\]
The algorithm then reassigns those already-formed bundles by a maximum-weight permutation and computes subsidies. The owner–bundle incidence in the original allocation is therefore part of the input used by the proof.
The proposed \(y_{t,j}\) formulation discards that incidence and retains only type masses and bundle masses. If the baseline type-to-bundle assignment is not supplied, “the baseline is EF1” is not even checkable. If it is supplied, the formulation is merely a conditional capacitated assignment postprocessing problem. Its transportation dual certifies a welfare-maximizing reassignment, but its dual objective is not the mass-weighted subsidy objective \(\sum_j\lambda_jp_j\); complementary slackness produces some envy-eliminating prices, not necessarily the minimum subsidy vector. Nor does Theorem 1’s \(n-1\) or triangular bound automatically become a bound in \(K\): after reassignment, EF1 bounds valuations relative to the original bundle, not necessarily relative to the bundle to which the type is transported. Establishing a \(K\)-based analogue would be a new theorem.
The obvious repairs expose the dilemma. A common \(p_j\) for every recipient of bundle class \(B_j\) imposes an anonymity condition absent from the paper: the paper permits different named recipients of identical bundles to receive different subsidies. Allowing recipient-type-specific subsidies restores fidelity, but then bundle classes must be split by recipient and subsidy status; the compact transportation dual disappears, and the number of effective classes can return to the number of named agents. Alternatively, keeping the paper’s fixed finite item set while sending the population to infinity makes every nonempty bundle a zero-mass exception. The meaningful EF1 and subsidy information then vanishes from the population distribution. Scaling item copies with population avoids that degeneration, but changes the resource side and creates a new repeated-market fair-division problem rather than a population-only continuization of this paper.
Thus the proponent has shown a coherent high-multiplicity extension, not a faithful mirror of Theorem 1 as stated. It is either routine transportation conditional on a fully specified allocation, or a new configuration-allocation problem once one restores the missing structure. That is the strongest negative case.
It is not airtight universally. Repeated course seats, housing slots, or service batches with finitely many complete valuation types are genuinely plausible, and a newly proved \(K\)-type subsidy theorem could make the extension worthwhile. So I would reject the proponent’s claimed derivation from Theorem 1, but I could not honestly defend the stronger claim that no worthwhile continuous mirror exists in any such repeated-resource regime.
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.