| paper | On the existence of Pareto Efficient and envy-free allocations |
| authors | R. Cole, Yi-Xin Tao |
| venue | JET 2021 |
| filed under | fairalloc · markets |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: Requires exponentially many communicated bits in \(m\), even for \(\tau=2\) and \(L=O(\log m)\); an upper bound of \(O(2^mL)\) bits holds. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given private submodular utility types \(u_L,u_R:2^{[m]}\to\mathbb{Q}\), each of mass \(\frac12\), and an atomless population of independent cells with one integral copy of every item per cell, output a mass vector \(x=(x_A)_{A\subseteq[m]}\) with \(x_A\ge0\) and \(\sum_A x_A=1\). Define \(U_L(x)=\sum_Ax_Au_L(A)\), \(U_R(x)=\sum_Ax_Au_R([m]\setminus A)\), and require \(U_L(x)\ge\sum_Ax_Au_L([m]\setminus A)\) and \(U_R(x)\ge\sum_Ax_Au_R(A)\), with no feasible \(y\) Pareto-improving both type-average utilities. Determine the worst-case communication needed for the two types to agree on \(x\).
The society has two complete utility types \(u_L,u_R\) with masses \(\mu_L=\mu_R=\frac12\). The decision variable is population mass \(x_A\) assigned to each integral cell allocation \(A\subseteq[m]\), with type-average utilities \(U_L(x)\) and \(U_R(x)\); the computational objective is minimizing or lower-bounding communication needed to produce an exact PE and EF \(x\).
The strongest objection is that \(x\) has exactly the same feasible polytope as the paper's mixed allocation \(\mathbf p\), while the type masses remain fixed at \(\mu_L=\mu_R=\frac12\), so a public random seed could simulate it.
fatal: False
The mirror covers Theorem 3.2's two-player submodular communication lower bound; it does not cover Theorem 3.1's existence theorem, the fixed-point lemmas, or the discussion of divisible allocations and gross substitutes.
The strongest honest positive case is narrow: I would anchor only on Theorem 3.2, not on Theorem 3.1. The latter proves existence, not a computational classification.
Theorem 3.2, proved in this paper using the cited Disjointness lower bound of Theorem 5.3, states that any communication protocol which finds a Pareto-efficient and envy-free allocation for two players with submodular utility functions must communicate exponentially many bits. In the reduction, \(m=2p\) items encode \(\mathcal L=\frac12\binom{2p}{p}\) coordinates of a Disjointness instance, yielding a lower bound of \(\Omega(\mathcal L)=2^{\Omega(m)}\) bits. The players privately know their utility functions, and the allocation set contains all partitions of the items.
I would mirror this with the following problem, Continuum-PE-EF Communication.
There is an atomless population of repeated two-person allocation cells. Every cell contains one left-role agent and one right-role agent, together with one integral copy of each of \(m\) indivisible items. All left-role agents have the same submodular utility \(u_L:2^{[m]}\to\mathbb Q\), and all right-role agents have the same submodular utility \(u_R:2^{[m]}\to\mathbb Q\). Thus the population has two complete utility types with masses \(\mu_L=\mu_R=\frac12\), while the number of agents is arbitrarily large.
A pure cell allocation gives the left agent some \(A\subseteq[m]\) and the right agent the complement \([m]\setminus A\). A continuous allocation is a mass vector \(x=(x_A)_{A\subseteq[m]}\), where \(x_A\ge0\) and \(\sum_A x_A=1\); \(x_A\) is the fraction of cells receiving that integral allocation. Define
\[ U_L(x)=\sum_A x_Au_L(A),\qquad U_R(x)=\sum_A x_Au_R([m]\setminus A), \]
and the utilities each type would obtain from the other type’s bundles by
\[ V_{L\leftarrow R}(x)=\sum_A x_Au_L([m]\setminus A),\qquad V_{R\leftarrow L}(x)=\sum_A x_Au_R(A). \]
The task is to output a finite description of \(x\) such that
\[ U_L(x)\ge V_{L\leftarrow R}(x) \quad\text{and}\quad U_R(x)\ge V_{R\leftarrow L}(x), \]
and such that there is no feasible \(y\) with \(U_L(y)\ge U_L(x)\), \(U_R(y)\ge U_R(x)\), and at least one strict inequality. In the distributed version, the left population knows only \(u_L\), the right population knows only \(u_R\), and all parties must agree on the same \(x\). The objective is to find any exact Pareto-efficient and envy-free mass allocation while minimizing worst-case communication.
This is genuinely a population mirror rather than fractionalizing an individual’s bundle: every cell receives integral bundles, and \(x_A\) is population mass. If \(x_A=k_A/N\), it is realized by assigning exactly \(k_A\) of \(N\) repeated cells that allocation. The per-capita item supply scales with \(N\), as it should in a high-multiplicity regime.
I expect this problem to be Class B: the communication hardness transfers. The paper’s reduction already uses only two utility types, so repeating those types across arbitrarily many cells does not remove the obstruction. The combinatorics live in the \(m\) items and in the exponentially many possible bundles, not in the number of named agents. The Disjointness construction should therefore give the same \(2^{\Omega(m)}\) communication lower bound for the continuum problem.
The plausibility is strong but limited. The authors would recognize the same objects—indivisible bundles, arbitrary complementarity-compatible utilities, ex ante envy-freeness, Pareto efficiency, and swappable allocations. The continuous interpretation changes the regime from one two-player instance to a large population of repeated two-role cells, while preserving the underlying question.
The weakest point is that the aggregate variable \(x\) is mathematically identical to the paper’s mixed-allocation vector \(\mathbf p\). An opponent can therefore argue that this is merely reinterpreting outcome randomization as population mass. The defence is that \(x\) has a different semantics and a finite high-multiplicity realization, but I would not claim a new tractability phenomenon. If communication complexity is excluded from the programme’s notion of a computational anchor, then this paper has no qualifying anchor at all; Theorem 3.1 is only an existence theorem.
The proponent is right to abandon Theorem 3.1: it is an existence theorem, not a computational result. The only plausible anchor is Theorem 3.2, and even that does not survive the population-continuization gate.
The proposed variable \(x\) is exactly the paper’s mixed-allocation vector \(\mathbf p\). For every bundle \(A\), \(x_A\) is simply the probability assigned to the corresponding pure allocation. The quantities \(U_L(x)\), \(U_R(x)\), \(V_{L\leftarrow R}(x)\), and \(V_{R\leftarrow L}(x)\) are precisely the paper’s expected utilities and envy constraints. Replacing that lottery by an atomless collection of cells, with fraction \(x_A\) of cells receiving allocation \(A\), is only a deterministic implementation of the same lottery.
The population itself contributes no computational object. Its type distribution is fixed at \(\mu_L=\mu_R=\frac12\), never supplied as input, changed by an operation, or used in the constraints. All the information remains in the two utility functions over \(2^{[m]}\), and all the combinatorics remain in the exponentially many integral bundle allocations. One can replace the whole population by two named players and a public random seed without changing the feasible set, the communication problem, or the lower bound. The continuous quantity is therefore the distribution over outcomes, exactly the kind of outcome-space continuity the programme excludes.
The “integral bundle per cell” defence does not repair this. If fairness and efficiency are imposed on type-average utilities, then the construction collapses back to the mixed allocation \(\mathbf p\). If they are imposed ex post on every individual cell, \(x\) is no longer sufficient: one must track which agents receive which bundles, and the paper’s ex ante EF and PE theorem no longer applies. Likewise, removing the cell walls to obtain one genuine high-multiplicity economy changes the feasible allocation set and requires utilities over bundles of all replicated items; Theorem 3.2 then gives no direct reduction.
A more ambitious model could distribute many complete utility types through a nontrivial \(\mu\) and study type-level Pareto efficiency and envy-freeness. That might be worthwhile, and repeated complete utility types are perfectly legitimate high-multiplicity types. But it would be a new allocation problem, not a continuous mirror of the paper’s communication theorem. With two types it degenerates to the lottery above; with many types, the paper supplies no theorem or lower-bound transfer.
Thus, even granting communication complexity as an admissible computational anchor, Theorem 3.2 supports only a communication lower bound for mixed allocations. It does not provide a computational question whose society has been continuized. The negative case is strong against this paper, though not a proof that no entirely new heterogeneous-population fairness model inspired by it could ever be valuable.
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.