Fair Division via Social Comparison (d4-conf-atal-2017-0337)

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.

A society is given by its support: a list of \(\tau\) types \(T\), each with positive binary-rational mass \(\mu_t\), with \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types.
Let \(H=D\star c\), where \(D\) is a nonempty DAG on \(T\setminus\{c\}\); retain its directed edges and add both \(t\to c\) and \(c\to t\) for every other type. There are no comparisons within a type.
Represent the population by \([0,1]\), partitioned into intervals \(P_t\) of lengths \(\mu_t\). The cake is \(C=[0,\lambda]\), where \(\lambda>0\) is a binary rational. Each type has a nonnegative, countably additive, nonatomic Borel valuation \(v_t\), normalized by \(v_t(C)=1\), accessible through Robertson–Webb queries.
An allocation is a measurable assignment \(p\mapsto B_p\) whose bundles partition all of \(C\) into pairwise disjoint finite unions of intervals; empty bundles and degenerate intervals are allowed. Its finite representation consists of arithmetic and comparison formulas for bundle endpoints, using input constants and oracle replies.
For each type, \(\nu_t\) is the bundle law induced by normalized Lebesgue measure on \(P_t\). Take support in the bundle space with pseudometric \(d(B,B')=\operatorname{Leb}(B\triangle B')+\sum_{s\in T}v_s(B\triangle B')\), identifying distance-zero bundles.
Require \(v_t(B)\geq v_t(B')\) for every edge \(t\to u\) and every \(B\in\operatorname{supp}\nu_t\), \(B'\in\operatorname{supp}\nu_u\). A protocol may query each type oracle directly and need not use a single cutter.
Is computing such an allocation polynomial-time solvable in the type-level Robertson–Webb model, with time and query bounds polynomial in \(m,\tau,L\) and independent of any finite replication factor, or is it NP-hard already for explicitly encoded rational piecewise-constant valuations?
Here \(m=1\) is the number of cake components and \(L\) is the finite input bit length, including valuation descriptions when supplied; exact oracle replies and arithmetic on them have unit cost.
For finitely many agents on a cone of a DAG, a locally envy-free complete allocation can be computed using \(O(n^2)\) Robertson–Webb queries. [Source](https://arxiv.org/html/1611.06589)
No result settling the continuum problem defined above was identified in the source search.

1. Classification

The problem as explicitly defined is polynomial-time solvable, with zero Robertson–Webb queries.

The immediate witness is \(B_p=\{\lambda p\}\). More substantially, the degeneracy is unavoidable: every admissible measurable allocation has the same bundle law, concentrated at the empty-bundle class, for every type. Thus there is no case with positive-value bundles for a positive-mass population under the stated requirements.

2. Structural lemma: only countably many people can receive positive-value bundles

Define the finite Borel measure
\( q=\operatorname{Leb}+\sum_{s\in T}v_s \)
on \(C\). Its total mass is
\( q(C)=\lambda+\tau. \)
The given pseudometric is exactly
\( d(B,B')=q(B\triangle B'). \)

Consider any admissible allocation \((B_p)_{p\in[0,1]}\). For each positive integer \(k\), put
\( E_k=\{p:q(B_p)\geq 1/k\}. \)

Claim. \(E_k\) is finite.

Indeed, if \(p_1,\ldots,p_N\) are distinct members of \(E_k\), pairwise disjointness and finite additivity give
\( N/k\leq\sum_{i=1}^{N}q(B_{p_i}) =q\!\left(\bigcup_{i=1}^{N}B_{p_i}\right) \leq\lambda+\tau. \)
An infinite \(E_k\) would contain finite subsets of arbitrarily large cardinality, contradicting this bound.

Every strictly positive real number is at least \(1/k\) for some positive integer \(k\). Consequently,
\( E:=\{p:q(B_p)>0\}=\bigcup_{k=1}^{\infty}E_k \)
is countable.

For every \(p\notin E\),
\( d(B_p,\varnothing)=q(B_p)=0. \)
Thus all but countably many people receive the empty-bundle class in the specified quotient space. This argument uses only measurability of individual bundles, pairwise disjointness, and finiteness of \(q\); restricting bundles to finite unions of intervals does not avert it.

3. Consequence: every support comparison is automatic

Write \(o=[\varnothing]\) for the empty-bundle class. Each type interval \(P_t\) has positive Lebesgue measure \(\mu_t\). Since \(E\) is countable,
\( \frac{\operatorname{Leb}(E\cap P_t)}{\mu_t}=0. \)
Therefore the induced law is
\( \nu_t=\delta_o \)
for every type \(t\).

Its support is exactly \(\{o\}\): every neighborhood of \(o\) has probability one, while any other point has an open ball excluding \(o\), hence of probability zero.

Valuations are well-defined on equivalence classes. For any bundles \(B,B'\),
\( |v_t(B)-v_t(B')| \leq v_t(B\triangle B') \leq d(B,B'). \)
In particular, every representative of \(o\) has value zero under every type valuation.

It follows that, for every edge \(t\to u\) and every pair of supported bundles, the required inequality is simply
\( 0\geq 0. \)
Hence every admissible measurable allocation satisfies the fairness requirement, regardless of the comparison graph.

4. Explicit complete allocation and complexity

Output the endpoint formula
\( B_p=[\lambda p,\lambda p], \qquad p\in[0,1]. \)

This satisfies every requirement:

• Each bundle is an allowed degenerate interval.
• Since \(\lambda>0\), distinct people receive distinct singletons, so bundles are pairwise disjoint.
• For every \(x\in C\), the person \(p=x/\lambda\) receives \(x\). Thus their union is exactly \(C\).
• Nonatomicity gives \(v_s(\{\lambda p\})=0\) for every \(s,p\), and singleton Lebesgue measure is zero. The assignment into the quotient bundle space is therefore constant and measurable.
• Both endpoints use one arithmetic expression involving the population parameter \(p\) and the input constant \(\lambda\).

The protocol makes zero oracle queries. Its output has size \(O(L)\), allowing for the binary encoding of \(\lambda\), and can be produced in polynomial time. These bounds are independent of any replication factor.

The same construction applies to explicitly encoded rational piecewise-constant valuations.

5. Why the substantive continuum extension fails here

The structural lemma addresses more than the singleton witness. For every admissible allocation and every type \(t\),
\( \operatorname{Leb}\{p\in P_t:v_t(B_p)>0\}=0. \)
Indeed, this set is contained in the countable set \(E\). Thus requiring positive own-value bundles on any population subset of positive mass would make the problem infeasible.

Completeness does not prevent this: countable additivity does not constrain an uncountable union of singleton bundles.

The cited finite-agent protocol uses finitely many equally valued pieces followed by choices in topological order. [Abebe, Kleinberg, and Parkes, Theorem 3.2](https://arxiv.org/html/1611.06589). The continuum formulation here instead forces all type-level bundle laws to collapse to \(\delta_o\). A substantive extension would require changing the allocation or resource-accounting model; it cannot be obtained while retaining all the present requirements.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The prover establishes polynomial-time solvability with zero Robertson–Webb queries for the problem as stated. The structural lemma and the explicit allocation are correct. No major or minor mathematical issues were found.

The degeneracy is relevant to the target: the task expressly permits degenerate intervals, specifies support after identifying distance-zero bundles, and imposes no positive-value requirement. The construction therefore satisfies the stated problem without adding an assumption or exploiting an unspecified convention.

1. Definition of the controlling measure

The definition
\(q=\operatorname{Leb}+\sum_{s\in T}v_s\), restricted to \(C\), is valid. The support size \(\tau\) is finite, and every valuation is a finite Borel measure with \(v_s(C)=1\). Consequently,
\(q(C)=\lambda+\tau<\infty\).

For every pair of admissible bundles, their symmetric difference is Borel, and the identity
\(d(B,B')=q(B\triangle B')\)
follows directly from the specified pseudometric.

Finding: correct, with all required finiteness and domain hypotheses satisfied.

2. Countability of the exceptional population

For each positive integer \(k\), the prover defines
\(E_k=\{p:q(B_p)\geq 1/k\}\).

For any \(N\) distinct members of \(E_k\), their bundles are pairwise disjoint Borel sets. Finite additivity therefore gives
\(N/k\leq q(\bigcup_{i=1}^{N}B_{p_i})\leq\lambda+\tau\).

This bounds the cardinality of every finite subset of \(E_k\). An infinite set would have finite subsets of arbitrarily large cardinality, so \(E_k\) is finite. The identity
\(\{p:q(B_p)>0\}=\bigcup_{k=1}^{\infty}E_k\)
is also correct: every positive real number exceeds or equals \(1/k\) for some positive integer \(k\).

Thus the exceptional set \(E\) is countable. No measurability assumption about \(E_k\) is needed for the counting argument; their established finiteness, and the resulting countability of \(E\), also ensure Lebesgue measurability.

Finding: correct. The argument uses only finite additivity on finite disjoint collections and does not incorrectly invoke countable additivity on an uncountable collection.

3. Collapse of each type’s bundle law

For every \(p\notin E\),
\(d(B_p,\varnothing)=q(B_p)=0\).
Hence the quotient-valued allocation equals the empty-bundle class \(o\) outside a countable population subset.

Each type has \(\mu_t>0\). Therefore
\(\operatorname{Leb}(E\cap P_t)/\mu_t=0\),
and its induced bundle law is precisely \(\nu_t=\delta_o\).

In the specified metric quotient, the support of this Dirac law is exactly \(\{o\}\). The prover checks both directions: every neighborhood of \(o\) has positive probability, and every other point has a neighborhood excluding \(o\).

Finding: correct. Positive type masses justify normalization, and exceptional individuals contribute no mass to any type’s law.

4. Valuations and fairness on the quotient

For finite nonnegative measures, the inequality
\(\lvert v_t(B)-v_t(B')\rvert\leq v_t(B\triangle B')\)
is valid. The further bound by \(d(B,B')\) follows from the definition of \(d\).

Thus valuations are well-defined on equivalence classes, and every representative of \(o\) has value zero under every type valuation. Since each type support consists solely of \(o\), every required comparison evaluates to \(0\geq0\).

This checks the universal quantifiers over all edges and all supported bundles. No property of the DAG or its apex is needed.

Finding: correct. The stronger claim that every admissible measurable allocation satisfies the support comparisons is established.

5. Explicit allocation and boundary cases

The proposed formula is
\(B_p=[\lambda p,\lambda p]\) for \(p\in[0,1]\).

The checks are valid:

• Each bundle is an expressly permitted degenerate interval.
• Because \(\lambda>0\), distinct population points receive distinct singletons.
• Every cake point \(x\in[0,\lambda]\) belongs to the bundle of \(p=x/\lambda\in[0,1]\).
• Both cake endpoints are included, through \(p=0\) and \(p=1\).
• Nonatomicity makes every singleton null for every valuation; it is also Lebesgue null.
• The assignment into the specified quotient bundle space is constant and therefore measurable.
• The endpoint formula uses only an allowed arithmetic expression and the input constant \(\lambda\).

Finding: correct. Completeness, exact disjointness, measurability, and representability are all satisfied.

6. Complexity claim

The protocol needs no valuation information and makes zero oracle queries. Its finite output consists of a fixed formula containing \(\lambda\), whose binary encoding is included in \(L\). The asserted output-size bound \(O(L)\) and polynomial running-time bound are justified.

The construction applies equally to explicitly encoded rational piecewise-constant valuations. Its bounds do not involve any replication factor.

Finding: the claimed polynomial-time classification follows.

7. Structural interpretation and source reference

The positive-own-value population subset is contained in \(E\), since \(v_t(B_p)\leq q(B_p)\). Its Lebesgue measure is therefore zero. The stated infeasibility of additionally requiring positive own-value on a positive-mass population subset follows.

The finite-agent protocol description agrees with [Abebe, Kleinberg, and Parkes, Protocol 1 and Theorem 3.2](https://arxiv.org/html/1611.06589): the apex cuts pieces equal in its valuation, and other agents choose in topological order. This is background context; the continuum proof does not apply or depend on that theorem.

Actionable feedback: no mathematical repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩