Comparing Approximate Relaxations of Envy-Freeness

The strongest positive case is a high-multiplicity version of the paper’s \(\mathrm{PMMS}\)-allocation problem. The paper contains no named NP-hardness result; my lead anchor is the constructive algorithmic result:

Corollary 3.9, proved in this paper using earlier algorithms, states that for \(n\ge 3\):

• the round-robin algorithm, in which agents successively choose their favourite remaining good, produces a \(\frac12\)-\(\mathrm{PMMS}\) allocation; and
• if all agents agree on the ordering of goods by value, then a \(\frac23\)-\(\mathrm{PMMS}\) allocation can be computed in polynomial time.

The first conclusion combines the known polynomial-time construction of an \(\mathrm{EF1}\) allocation with the paper’s Proposition 3.8, which proves that every \(\alpha\)-\(\mathrm{EF1}\) allocation is an \(\frac{\alpha}{1+\alpha}\)-\(\mathrm{PMMS}\) allocation. At \(\alpha=1\), this gives \(\frac12\)-\(\mathrm{PMMS}\). The second combines polynomial-time exact \(\mathrm{EFX}\) algorithms under a common item ordering, cited from Barman and Krishnamurty and from Plaut and Roughgarden, with Proposition 3.7, which turns exact \(\mathrm{EFX}\) into \(\frac23\)-\(\mathrm{PMMS}\). Thus Corollary 3.9 is stated here, but its algorithmic ingredients are partly cited from elsewhere.

Here is the continuous mirror I would put before the authors.

There is a finite catalogue \(G=\{g_1,\ldots,g_r\}\) of standardized indivisible goods, with \(q_g\) copies of good \(g\) per capita. Every agent receives exactly \(\ell\) goods, where \(\sum_{g\in G}q_g=\ell\). A voter or agent type \(t\in T\), with \(|T|=\tau\), is specified by its complete additive valuation vector \(v_t(g)\). The society is a distribution \(\mu\in\Delta(T)\). Thus \(\mu_t\) is the fraction of the population having valuation type \(t\).

This describes, for example, a national benefits programme serving millions of households, where only a small number of household profiles occur and the programme distributes many copies of a fixed catalogue of indivisible benefits. The high-multiplicity regime is \(N\gg \tau,r,\ell\): there may be millions of agents but only a few dozen valuation types and a small fixed number of goods per agent. For rational \(\mu\) and \(q\), an ordinary finite instance is recovered by taking \(N\) large enough that \(N\mu_t\) and \(Nq_g\) are integers.

Let

\[ \mathcal B_\ell=\left\{b\in\mathbb Z_{\ge 0}^{G}:\sum_{g\in G}b_g=\ell\right\} \]

be the set of integral bundles. The action is a mass assignment \(x=(x_{t,b})\), where \(x_{t,b}\) is the mass of type \(t\) receiving bundle \(b\). It must satisfy

\[ \sum_{b\in\mathcal B_\ell}x_{t,b}=\mu_t \]

for every type \(t\), and

\[ \sum_{t\in T}\sum_{b\in\mathcal B_\ell}b_gx_{t,b}=q_g \]

for every good \(g\). Hence every unit of population receives an integral bundle; only the aggregate assignment is fractional.

For two bundles \(b,b'\), define the type-\(t\) pairwise maximin share by

\[ \operatorname{pmm}_t(b,b') = \max_{\substack{u+w=b+b'\\u,w\in\mathbb Z_{\ge0}^{G}}} \min\{v_t(u),v_t(w)\}. \]

The continuous problem is:

Continuous High-Multiplicity PMMS. Given \((G,T,v,\mu,q)\), output a mass assignment \(x\) maximizing the largest \(\lambda\in[0,1]\) such that, whenever \(x_{t,b}>0\) and \(x_{s,b'}>0\),

\[ v_t(b)\ge \lambda\,\operatorname{pmm}_t(b,b'). \]

The direct mirror of Corollary 3.9 asks whether one can output such an \(x\) with \(\lambda\ge\frac12\); in the common-ordering regime, it asks for \(\lambda\ge\frac23\).

This is recognisably the authors’ problem. Preferences remain additive, goods remain indivisible for each individual, the fairness condition remains pairwise maximin share fairness, and the output is still an allocation of goods rather than a fractional division of goods. The only co-modification is the necessary one: the supply of each good scales with the population, so that a continuum of agents does not receive nothing simply because the original paper has only finitely many goods.

I expect the fixed-\(\ell\) version to be a plausible Class A problem. A round-robin execution over a huge cloned electorate can potentially be compressed into an event-driven sweep over type masses and item supplies. Equivalently, one can seek a configuration formulation whose columns are integral bundles and whose output is the mass vector \(x\). In the common-ordering case, the \(\frac23\) guarantee should be especially amenable to such compression. The unrestricted version, with \(\ell\) part of the input, is a worthwhile boundary question: the number of possible integral bundle configurations may become large, and selecting a mutually compatible support for the PMMS inequalities could create genuine continuum-specific hardness. It would not be hardness transferred from this paper, since the finite source problem has the positive algorithmic result of Corollary 3.9.

The mirror covers only the algorithmic part of the paper: Corollary 3.9, supported by Propositions 3.7 and 3.8. It does not claim to continuize every implication among \(\mathrm{EF1}\), \(\mathrm{EFX}\), \(\mathrm{MMS}\), and \(\mathrm{PMMS}\). Those propositions can generate follow-up questions, such as whether the \(\frac12\) and \(\frac23\) guarantees survive in compressed form, whether exact continuous \(\mathrm{PMMS}\) is computable, and whether the optimum \(\lambda\) agrees with the limit of finite high-multiplicity instances.

The weakest point is that Corollary 3.9 does not itself provide a compressed high-multiplicity algorithm. The ordinary round-robin algorithm may take time proportional to the enormous population \(N\), and PMMS constraints are global and support-dependent rather than obviously linear. So the positive case rests on a credible but nontrivial bridge: compressing a known finite constructive allocation into mass variables without allowing fractional bundles. That bridge is exactly the computational question the continuous mirror would expose.