| paper | Achieving Envy-freeness and Equitability with Monetary Transfers |
| authors | H. Aziz |
| venue | AAAI 2021 |
| filed under | fairalloc · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Both the general problem and its \(K=0\) restriction are \(\mathrm{NP}\)-complete, already for \(\tau=1\) with nonnegative additive valuations and supplies \(b_j=1/2\). Both admit exact algorithms running in \(2^{O(m)}\operatorname{poly}(\tau,L)\) time. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 5
statement extracted from the paper’s text layer
Given rational type masses \(\mu_t\), rational per-capita supplies \(b_j\) of indivisible task categories, and valuation functions \(v_t\) over integral bundles \(B\), choose mass variables \(\lambda_{t,B}\ge 0\) and subsidies \(p_{t,B}\le 0\) satisfying \(\sum_B\lambda_{t,B}=\mu_t\) and the task-capacity constraints, minimizing \(S=\sum_{t,B}\lambda_{t,B}(-p_{t,B})\), subject to every positive-mass state \((t,B)\) having equal utility \(v_t(B)-p_{t,B}\) and weakly preferring its own state to every assigned state; decide in particular whether \(S=0\).
A high-multiplicity configuration model with integral bundle configurations, mass allocation \(\lambda_{t,B}\), type-dependent valuations \(v_t\), per-capita task capacities, subsidy variables \(p_{t,B}\), and total subsidy \(S\) as the objective.
The mirror covers the minimum-payment optimization and hardness question of Theorem 5, especially its identical-valuation case. It does not establish worthwhile mirrors for Corollary 2, Theorem 3, or the paper's other finite-agent characterization and transfer-process results.
The strongest positive case is a genuine high-multiplicity fair-allocation mirror, with Theorem 5 as the lead anchor. The paper’s hard instance is especially promising because its proof already uses identical valuations: the population can therefore contain arbitrarily many agents of one complete type.
Consider a large recurring task-allocation market: a hospital network, logistics platform, or municipal workforce has many interchangeable workers, while task supplies scale with the workforce. A type \(t\) is a complete valuation function \(v_t\) over integral task bundles: workers of the same type have exactly the same preferences, costs, and outside parameters. Let \(\mu_t\) be the fraction of workers of type \(t\), with \(\tau\) fixed or modest while the number of workers is large.
Tasks remain indivisible for every individual worker. The continuum appears only in the assignment masses. If \(B\) is an integral bundle, let \(\lambda_{t,B}\) be the mass of type-\(t\) workers receiving \(B\). Thus \(\sum_B\lambda_{t,B}=\mu_t\), while per-capita task-supply constraints specify which \(\lambda\)'s are feasible. A worker never receives a fractional bundle; only the population share receiving each integral bundle is fractional. This is a population continuization, not an outcome-space relaxation.
A payment \(p_{t,B}\) is made by each worker of type \(t\) receiving \(B\), with utility \(u_{t,B}=v_t(B)-p_{t,B}\). The aggregate outcome is equitable if all positive-mass workers obtain the same utility. It is envy-free if every such worker weakly prefers their own bundle-payment pair to every other assigned pair. The normalized welfare is \(W(\lambda)=\sum_{t,B}\lambda_{t,B}v_t(B)\).
The lead anchor is Theorem 5, proved in this paper. It states that computing the minimum payments needed to achieve envy-freeness and equitability simultaneously is strongly NP-hard, and that, unless \(\mathrm{P}=\mathrm{NP}\), no deterministic polynomial-time algorithm approximates the minimum payments within any prescribed positive factor. The proof uses the NP-completeness of deciding whether an envy-free allocation exists when all agents have identical valuations; with identical valuations, zero-payment envy-freeness also implies equitability.
The corresponding problem is:
Continuous Minimum-EFEQ-Payment\(_\infty\). Given rational type masses \(\mu\), rational per-capita task supplies, valuation functions \(v_t\), and integral bundle feasibility constraints, choose a feasible mass allocation \(\lambda\) and payments \(p_{t,B}\le 0\) so that the resulting outcome is envy-free and equitable, minimizing total subsidy \(S(\lambda,p)=\sum_{t,B}\lambda_{t,B}(-p_{t,B})\). The decision version asks whether \(S=0\).
The subsidy convention is the natural continuous version of the paper’s payment discussion and its later subsidy-only construction. If one prefers balanced transfers, one can instead require \(\sum_{t,B}\lambda_{t,B}p_{t,B}=0\) and minimize total transfer magnitude; the zero-payment question is the same.
This is a substantive question. In the one-type case, \(\mu_1=1\), it asks whether a large population of identical workers can be assigned integral bundles of equal value with zero subsidy. The continuous relaxation may make aggregate assignment fractional, but it does not permit fractional bundles or average-out unequal utilities. Hence the equal-bundle partition structure remains. I would expect hardness to transfer in the general version, because the combinatorics lives in the task catalogue and valuation structure rather than in named-agent identities. The repeated-supply additive subcase is also a natural place to test whether configuration-LP methods dissolve some of the discrete hardness. That boundary is precisely the kind of Class B versus Class A question ChoCo is meant to expose.
A second, algorithmic anchor is Corollary 2, proved here. It says that, with additive valuations and constant-time access to an agent’s value for a bundle, there is an \(O(n^2)\) algorithm for checking whether a given allocation is EFEQ-convertible. Its continuous counterpart is:
Continuous EFEQ-Convertibility\(_\infty\). Given \(\mu\), additive type valuations, and an explicit finite-support mass allocation \(\lambda\), decide whether there exists a payment schedule making the allocation envy-free and equitable, and output such payments if one exists.
The relevant continuous condition is the mass version of transfer-stability: for every pair of positive-mass assigned states \((t,B)\) and \((u,D)\), transferring the second integral bundle to the first worker must not improve welfare. Under additive valuations this reduces to checking that no type values another type’s assigned bundle more highly than its owner does. If the condition holds, the Knaster-style payments \(p_{t,B}=v_t(B)-W(\lambda)\) are balanced, equitable, and envy-free. With explicit support, this is expected to be Class A, with complexity depending on the number of supported bundle states rather than the number of individual workers.
The third useful anchor is Theorem 3, also proved here. It states that, for superadditive valuations and a given allocation \(Y\), one can compute in polynomial time an allocation \(X\) and balanced payment function \(p\) such that the outcome is envy-free and equitable and \(SW(X)\ge SW(Y)\).
The continuous problem is:
Continuous Fairness Improvement\(_\infty\). Given \(\mu\), superadditive type valuations, task supplies, and an initial mass allocation \(\lambda^0\), compute a feasible \(\lambda\) and balanced payments \(p\) such that the outcome is envy-free and equitable and \(W(\lambda)\ge W(\lambda^0)\).
The natural analogue of the paper’s transfer algorithm moves a positive mass \(\delta\) from states \((t,B)\) and \((u,D)\) to \((t,B\uplus D)\) and \((u,\emptyset)\) whenever this strictly increases welfare. The final payments are \(p_{t,B}=v_t(B)-W(\lambda)\). I would expect this problem to be tractable for explicit finite-support allocations and valuation oracles, although proving a polynomial bound in the compressed parameters \((\tau,|G|,L)\) would itself be a worthwhile result.
The authors should recognize these mirrors as their questions. They preserve their objects—indivisible task bundles, arbitrary or additive valuations, monetary transfers, envy-freeness, equitability, welfare, and transfer-stability—while replacing a long list of essentially interchangeable workers by their type distribution. The paper’s identical-valuation hardness case is not an artificial rescue: it is exactly the regime in which high multiplicity is most plausible.
The weakest point is the task supply. If the paper is interpreted as allocating one finite inventory of unique tasks to a finite set of named agents, then an atomless population is not meaningful: almost all agents would receive the empty bundle. The mirror therefore needs repeated task batches or per-capita task supplies. That is a real co-modification, though a natural one for recurring workforce allocation. A second caveat is that Theorem 5’s hardness does not automatically transfer: fractional assignment masses may eliminate the original partition obstruction. Establishing when integral bundle configurations retain hardness, and when configuration-LP machinery makes the high-multiplicity version tractable, is the main further question rather than something to assume.
The strongest negative case is that the paper’s two algorithmic anchors do not survive as meaningful population continuizations. Corollary 2 is only a finite scan over named agents, and Theorem 3 relies essentially on named-agent identities. Theorem 5 is more difficult, but it is also the point at which the negative case becomes genuinely weak.
For Corollary 2, an explicit mass allocation must record states \((t,B)\): the same valuation type may receive several different integral bundles. Transfer-stability is then checked pairwise over the finitely many states with positive mass, and the Knaster payment is simply \(p_{t,B}=v_t(B)-W\). This is a mechanical replacement of \(n\) by the support size. The population distribution \(\mu\) contributes no computational content. If the support is implicit, the problem becomes one of representing or separating over exponentially many bundle configurations; that is a new configuration problem, not the \(O(n^2)\) theorem being continuized.
Theorem 3 fares worse. Its termination proof depends on transferring an entire named bundle \(X_j\) and thereby making agent \(j\) empty. The bound comes from counting empty agents and showing that a bundle cannot return to a previous agent. In an atomless population, transferring mass \(\delta\) does not create an analogous combinatorial event. One can split a state, create a new merged-bundle state, and repeat; the proof’s potential argument and \(O(n^4 f(I))\) bound disappear. Forcing transfers to occur only in indivisible cohorts restores the proof’s structure, but then the population is again a finite collection of cohorts rather than a genuine continuum. Allowing arbitrary mass transfers produces a new configuration-dynamics problem for which this paper supplies no algorithmic result.
Theorem 5 initially appears to provide the decisive rescue. With the paper’s fixed finite task set, however, an atomless population is degenerate: each task can be assigned to at most one measure-zero individual, so almost every agent receives the empty bundle. To avoid that, the proposed mirror scales task supplies with population mass. That is a plausible workforce model, but it changes the computational object substantially. In the one-type additive case, zero-subsidy EFEQ feasibility becomes
\[ b\in\operatorname{conv}\{\chi_B : v(B)=Q\}, \qquad Q=\sum_j b_jv(\{j\}), \]
where \(b\) is the per-capita task-supply vector and \(\chi_B\) is the incidence vector of an integral bundle. The original equal-partition question has become convex-hull membership over equal-value configurations. Retaining the original partition obstruction requires indivisible positive-mass cohorts; scaling tasks instead produces a new configuration-LP problem whose complexity is not established by Theorem 5.
That is a real objection to the proposed mirror as an anchor: either the finite inventory makes the continuum collapse, or per-capita supplies replace the paper’s problem with a different aggregate assignment problem. The same dilemma affects attempts to preserve the theorem by encoding every original item as a distinct task type: the type catalogue then grows with the hard instance, and there is no repeated-agent regime doing the work.
But this does not support the requested universal negative conclusion. Theorem 5 uses identical valuations, so its hard instance is unusually compatible with high multiplicity. A recurring market with many interchangeable workers, repeated task categories, integral bundles per worker, and fractional assignment masses is a coherent continuous-population model. The resulting convex-hull/configuration question may be exactly the sort of Class A versus Class B boundary that ChoCo is meant to study. It is not defeated merely because it is not the same discrete partition problem.
Thus the negative case can convincingly reject Corollary 2 and Theorem 3 as worthwhile continuous mirrors. It cannot honestly defeat Theorem 5: the first anchor survives in a plausible high-multiplicity scenario, even though the paper itself gives no result about the resulting configuration problem. A universal “no mirror in any scenario” verdict would therefore be overreach.
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.