How to Resolve Envy by Adding Goods

My strongest case is a Class A mirror of the paper’s Theorem 3, proved in this paper: “ENVY ELIMINATION BY ADDING GOODS is polynomial-time solvable when \(\#(r)=\infty\) for all \(r\in R\) and \(k\) is unbounded.” I would use this anchor alone; the paper’s finite-supply hardness results require more delicate modelling and would weaken the case if treated casually.

The natural regime is a large population of recipients of standardized entitlements: for example, a city-wide charity or voucher programme serving millions of people, with only a small number of eligibility and valuation profiles. A type \(t\) records the recipient’s valuation \(v_t\) over all goods and their initial bundle \(B_t\). A society is a rational mass vector \(\mu\in\mathbb{Q}_{\ge 0}^{\tau}\), with \(\sum_t\mu_t=1\). Thus \(\mu_t\) is the fraction of recipients having exactly that valuation and initial entitlement. The number of people may be enormous, while \(\tau\) remains small.

The additional goods \(R\) have unlimited supply. They remain indivisible: each recipient receives an integer number of copies. A solution assigns an integer vector \(q_t\in\mathbb{N}^{R}\) to every type \(t\), meaning that every mass unit of type \(t\) receives that bundle. The aggregate amount of resource \(r\) issued is \(\sum_t\mu_tq_{t,r}\); there is no supply constraint because every \(r\) is unlimited.

Call this problem Continuous Envy Elimination with Unlimited Supply, or \(\mathrm{CEAG}_{\infty}\). Its instance consists of \(T\), \(\mu\), the initial bundle \(B_t\) and additive valuation \(v_t\) for each type, and the unlimited-supply item catalogue \(R\). The question is whether there exist integer vectors \(q_t\) such that, for every pair of types \(t,u\),

\[ v_t(B_t)+\sum_{r\in R}q_{t,r}v_t(r) \;\ge\; v_t(B_u)+\sum_{r\in R}q_{u,r}v_t(r). \]

If so, the output is the collection of bundles \((q_t)_{t\in T}\), together with the aggregate mass of each added item.

This is not a fractional-goods reformulation. The population is continuous, but every individual still receives an integral bundle and envy is checked pairwise, not in expectation. The common bundle \(q_t\) is also not an arbitrary simplifying restriction in the unlimited-supply regime. If a finite replicated population has an envy-free solution in which members of one type receive different bundles, choose one representative bundle for each type and give that bundle to all members of the type. Since unlimited copies are available, this is feasible; and the original envy-free inequalities already guarantee that the representatives’ bundles are mutually acceptable. Hence a type-homogeneous solution is without loss of generality.

The authors should recognise this as their problem under high multiplicity. A rational vector \(\mu\) with denominator \(N\) is exactly the population obtained by cloning type \(t\) into \(N\mu_t\) recipients, including cloned initial bundles. Conversely, a large discrete instance with repeated recipient roles compresses to \((T,\mu)\). The continuous input is therefore a high-multiplicity encoding, not a new fairness notion.

I expect \(\mathrm{CEAG}_{\infty}\) to be in Class A. The proof of Theorem 3 survives with the number of explicit agents replaced by the number of types. Proportional valuation classes are formed over \(R\); within each class, the gcd criterion from Lemma 2 and the totally unimodular difference-constraint ILP use one variable per type. Between non-proportional types, Lemma 1 supplies the same two-item repair used in the paper, and there are at most \(\tau^2\) type-level envy edges. Thus the resulting running time should be polynomial in \(\tau\), \(|R|\), and the encoding length, without expanding a population whose size may be exponential in the input length.

This covers exactly the paper’s unbounded-supply, unbounded-budget result. It does not claim to mirror Proposition 4 or Proposition 5. Those reductions exploit finite item supplies and, in Proposition 5, the discrete partitioning of finitely many item copies among bins. A faithful continuous version of that regime would need a measure over integral bundles and would lead to a configuration or pricing problem; its complexity is genuinely open rather than automatically inherited.

The weakest point is that, because supply is unlimited and there is no budget, \(\mu\) does not affect feasibility—only the aggregate quantity of goods issued. A sceptic can therefore call this “type compression” rather than a mass-sensitive new phenomenon. I think it still qualifies: the programme explicitly treats high multiplicity as the relevant regime, and here the compressed instance admits an algorithm polynomial in \(\tau\) even when the underlying population is huge. A natural next question is the weighted optimization version, minimizing

\[ \sum_{t\in T}\mu_t\sum_{r\in R}w_rq_{t,r}, \]

or the finite-supply version with supply densities. Those would test whether the same continuization yields further algorithmic gains rather than merely a compressed decision procedure.