| paper | Fair Division via Social Comparison |
| authors | Rediet Abebe, J. Kleinberg, D. Parkes |
| venue | ATAL 2017 |
| filed under | fairalloc · cake |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable (\(\mathrm{P}\)), with zero Robertson–Webb queries; every admissible allocation automatically satisfies the support comparisons. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Theorem 3.2
statement extracted from the paper’s text layer
Given a finite role graph \(H=D\star c\), positive role masses \(\mu\in\Delta(T)\), nonatomic valuation oracles \(v_t\), and a scaled cake supply \(\lambda\) per unit population, form the complete bipartite blow-up in which every role-\t\ agent compares with every role-\u\ agent whenever \t\to u\. Output a measurable allocation law \(\nu_t\) over individual bundles, realizable by disjoint bundles in the scaled cake, such that for every edge \t\to u\, every \(B\in\operatorname{supp}\nu_t\), and every \(B'\in\operatorname{supp}\nu_u\), \(v_t(B)\ge v_t(B')\); determine whether this can be computed by a type-level Robertson–Webb protocol using queries polynomial in \(|T|\) and independent of the replication factor.
Types are complete repeated network roles \(t\), masses are \(\mu_t\), the divisible cake supply scales per capita, and each type receives a law \(\nu_t\) of individual bundles. The objective is type-level query complexity under exact support-wise local envy-freeness along role edges.
The proposed type-average condition is not equivalent to ex-post local envy-freeness, and a single cutter with query complexity independent of population mass is not immediate; an exact mirror needs bundle distributions or a symmetric blow-up model.
fatal: False
The mirror covers the cone-of-DAG protocol and the oblivious single-cutter characterization. It leaves the graph-comparison separation result, the basic fairness implications, the price-of-fairness theorem as a noncomputational welfare bound, and the appendix extension lemma largely untouched.
The strongest mirror is a high-multiplicity version of the paper’s local envy-free allocation problem, with the social network represented by a finite graph of repeated roles.
Let \(T\) be a finite set of complete agent types. A type includes its nonatomic valuation \(v_t\) over the cake and its network role: which other role-types it compares with. The society is a distribution \(\mu\in\Delta(T)\). A finite realization with replication factor \(M\) has approximately \(M\mu_t\) agents of type \(t\), with \(M\gg |T|\). This is plausible for repeated housing cooperatives, school districts, departments, or local benefit-allocation units: many residents occupy the same small number of preference and social-network roles.
Because the resource must scale with the population, I would use \(M\) copies of the unit cake, or equivalently a per-capita cake supply. A continuous allocation is represented by the mean bundle \(q_t\) received by type \(t\); \(q_t\) may be fractional even though every individual receives an ordinary measurable bundle. Feasibility is
\[ \sum_{t\in T}\mu_t q_t=\lambda, \]
where \(\lambda\) is the per-capita cake supply. For a directed role edge \(t\to u\), local envy-freeness is
\[ v_t(q_t)\ge v_t(q_u). \]
The welfare objective is
\[ W(q)=\sum_{t\in T}\mu_t v_t(q_t). \]
This is not merely “fractional cake cutting”: the continuous object is the population distribution and its repeated social-network roles. The fractional \(q_t\)'s are type averages generated by many integral allocations.
The paper has no named NP-hardness, \(\mathrm P\), W[1]-hardness, or FPT theorem. Its computational anchors are Robertson–Webb query bounds and structural classifications. My lead anchor is therefore Theorem 3.2, proved in this paper.
Theorem 3.2 states: if \(G\) is a cone of a directed acyclic graph, Protocol 1 computes a locally envy-free allocation using a bounded number of queries. The protocol is explicit: the apex \(c\) cuts the cake into \(n\) pieces of equal value to \(c\); the remaining nodes are topologically ordered; they choose their preferred remaining piece in that order; and \(c\) receives the last piece. The paper proves local envy-freeness and gives the exact query count
\[ \frac{n^2+3n-4}{2}. \]
My continuous problem is High-Multiplicity Local Envy-Freeness on a Cone:
Given a finite role graph \(H=D\star c\), nonatomic valuation oracles \(v_t\) for the roles, and a continuum of repeated copies of the role network, output a type-symmetric allocation rule that gives every copy a cake partition satisfying local envy-freeness. In the oracle model, the rule must use only type-level queries and should be evaluated by its query complexity as a function of \(\tau=|T|\), independently of the replication factor \(M\).
The direct continuous analogue of Protocol 1 cuts each repeated cake using the apex role, lets the other role-types choose in a topological order, and gives the residual piece to the apex. It uses
\[ \frac{\tau^2+3\tau-4}{2} \]
type-level queries, while serving an arbitrarily large population. The expected classification is tractable: this is a genuine compression from \(M\) agents to \(\tau\) types, not a change in the local envy-free condition or the valuation model. The further question is whether arbitrary type masses \(\mu\), rather than one copy of each role, admit an equally clean weighted protocol.
A closely related second mirror is anchored in Theorem 3.3, also proved here. It states that if an oblivious single-cutter protocol produces a locally envy-free allocation for every valuation profile on \(G\), then \(G\) must be a subgraph of a cone of a DAG. Together with Theorem 3.2 and the subgraph observation, this gives the paper’s characterization of the graphs supporting such protocols. The proof’s obstruction is concrete: if deleting the cutter leaves a directed cycle, the other agents can be assigned geometrically decreasing values for the cutter’s pieces so that some agent on the cycle must envy its successor.
The corresponding continuous problem is Type-Level Single-Cutter Characterization:
Given a finite quotient network \(H\), decide whether there is a type-level oblivious single-cutter protocol that, for every valuation profile, partitions each repeated cake using only one cutter role’s valuation and then allocates the resulting pieces by choices of the other roles, always producing local envy-freeness.
The expected answer is exact: yes precisely when \(H\) is a subgraph of a cone of a DAG; otherwise the directed-cycle adversary defeats every such protocol. This is a structural result rather than a complexity result, but it is a particularly convincing mirror because the quotient graph retains exactly the paper’s relevant information: who compares with whom and in what direction.
The paper’s main welfare result supplies a third, more ambitious mirror. Theorem 4.1, proved in the paper, states that for every connected undirected graph \(G\), there are valuation functions for which the price of local envy-freeness is \(\Omega(\sqrt n)\). In full, the unrestricted welfare can exceed the maximum welfare of any locally envy-free allocation by a factor proportional to \(\sqrt n\), even when the comparison graph is sparse and connected. The proof uses the linked-partition construction of Lemma 4.2 and the graph-theoretic guarantee of Theorem 4.4; it adapts the valuation idea of Caragiannis et al., but the theorem itself is established here.
The continuous problem is High-Multiplicity Price of Local Envy-Freeness:
Given \((T,\mu,H,\{v_t\})\), compute
\[ W^*=\max_q \sum_t\mu_t v_t(q_t) \]
over all feasible allocations, compute
\[ W^{\mathrm{LEF}} =\max_q \left\{\sum_t\mu_t v_t(q_t): v_t(q_t)\ge v_t(q_u)\text{ for every }t\to u\right\}, \]
and determine the ratio
\[ P_{\mathrm{LEF}}=\frac{W^*}{W^{\mathrm{LEF}}}. \]
The asymptotic question is whether the paper’s welfare loss survives when every role is replicated arbitrarily many times while the number of distinct valuation/network types stays small. I expect the lower-bound phenomenon to transfer. The construction has a small number of specialized leader roles, each preferring a different interval, and many repeated uniform follower roles connected to it. Replicating every role preserves the valuation inequalities and path arguments while making \(M/|T|\) arbitrarily large. Thus high multiplicity should not remove the welfare cost; it should expose that the cost is driven by the number and arrangement of distinct roles, not by individually named voters.
For piecewise-constant valuations this becomes a finite linear optimization problem over allocation densities or configuration variables. Whether the corresponding oracle problem has efficient exact or approximation algorithms is a new computational question, not answered by this paper. The expected result is therefore a transferred structural lower bound together with an open continuous-optimization problem.
My weakest point is the co-modification of the model. The original paper has one finite cake and a graph on individually named agents, whereas the mirror uses repeated typed network motifs, per-capita resource, and sometimes type-average bundles. A single globally designated cutter also becomes measure-zero in the limit; the natural mirror has one cutter role per repeated allocation unit. If the authors insist that only one cutter for the entire population counts, the protocol mirror is weak.
The case nevertheless survives for the paper’s central local-fairness problem. The types preserve the agents’ valuations and comparison roles, the repeated-network regime is a sensible high-multiplicity scenario, and the welfare formulation retains the same local envy-free inequalities and welfare objective. I would therefore claim a strong mirror for Theorem 3.2 and Theorem 3.3, and a substantive, though more model-dependent, mirror for Theorem 4.1.
The strongest negative case is that the proposed continuization does not preserve the paper’s central object: local envy-freeness is an ex-post, identity-sensitive constraint, whereas a distribution over role-types only records averages.
For copies of types \(t\) and \(u\), the exact blow-up of an edge \(t\to u\) requires
\[ v_t(A_{t,a})\ge v_t(A_{u,b}) \]
for every pair of copies \(a,b\). The proposed condition
\[ v_t(q_t)\ge v_t(q_u) \]
compares only average bundles. It is not equivalent. Two copies of \(t\) may receive bundles worth \(0\) and \(2\), while a \(u\)-bundle is worth \(1\); the averages satisfy the proposed inequality, but one \(t\)-agent envies \(u\). Enforcing the original condition requires the full distribution of bundles and the exact edge coupling, not merely \(\mu\) and type-average bundles.
This defeats the proposed mirror of Theorem 3.2. If every repeated network copy receives its own cake, the construction is just the same finite protocol copied \(M\) times; there is no shared population-level allocation. If instead there is one cake whose supply scales with \(M\), Protocol 1 must cut enough pieces for the individual copies and its query count grows with \(M\). Obtaining a bound depending only on \(\tau\) requires replacing individual choices by a new weighted, ex-ante or type-symmetric allocation problem. That may be interesting, but it is not the theorem’s Robertson–Webb protocol any longer. A single “cutter role” is not a single cutter agent in the paper’s sense.
Theorem 3.3 has the same problem. A finite graph can be quotiented by roles only when copies have a highly artificial block structure: every copy of one role compares with exactly the same collection of copies of another role. For a general social network, the neighbors are part of an agent’s complete type, so preserving them makes almost every vertex a distinct type and destroys the high-multiplicity compression. If one imposes the block structure, the proposed characterization is simply a statement about the finite role graph \(H\); the population masses do not define the local comparisons. If one instead retains a matching or arbitrary network among copies, the model needs an additional edge measure or graphon, and the cycle proof no longer establishes the claimed type-level characterization.
Theorem 4.1 is an even weaker anchor. It is a welfare lower bound, not a computational-complexity result. More importantly, its construction needs \(\sqrt n\) specialized leader agents with distinct preferred intervals. Since valuation is part of a complete type, it needs at least \(\sqrt n\) distinct types. Replicating those roles does not turn the theorem into a fixed-type continuum result: with fixed \(\tau\), the construction has only finitely many distinct leaders; with \(\tau\) growing, the claimed phenomenon is driven by the number of types and the graph, not by population multiplicity. The linked-partition proof also uses inequalities between individual bundle sizes along paths, which type averages do not preserve.
Thus every repair faces the same fork. Independent cakes give a collection of repeated finite instances. A common scaled cake requires bundle distributions and identity-level edge couplings. Enforcing type symmetry changes ex-post local envy-freeness into a stronger or weaker aggregate notion, depending on the implementation. None is the paper’s continuous-population analogue.
This is not an airtight impossibility claim: a genuinely new model of repeated network motifs with ex-post bundle distributions could be worthwhile. But the paper itself provides no strong anchor for it. The proposed mirrors either abandon the shared-cake allocation problem, replace its fairness notion, or retain so much identity and network structure that the continuous population disappears.
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.