| paper | Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division |
| authors | — |
| venue | AAMAS 2024 |
| filed under | frontier · tools-data |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | no |
Both anchors satisfy the computational bit, but neither proposed question preserves a single shared allocation problem with a continuously represented population. Fixed indivisible resources cannot support the claimed population growth, while replicated resources turn the construction into an ensemble of independent instances. The opponent's objection is fatal to these concrete mirrors, though it does not rule out a substantially new model.
fails bit b — no continuous question survives
The proposed copies and frequencies change the object from one society allocating one resource graph to a distribution over complete finite allocation instances, with potentially different \uoperatorname{MMS}_r benchmarks.
fatal: True
The proposed mirrors cover only the two-agent approximation algorithm and the identical-utility tree algorithm; they leave the paper's general local-fairness, heterogeneous-utility, and multi-agent results without a population-only analogue.
The strongest mirror is a high-multiplicity version of the paper’s identical-utility tree case, anchored on Corollary 6.8, proved in this paper via Lemma 6.4 and Theorem 6.5. Corollary 6.8 states that, for a tree \(G\) and \(n\) agents with identical additive utilities, a PMMS and SMMS connected allocation can be found in polynomial time.
I would call the continuous problem Tree-PMMS\(_\infty\). A resource template is a finite tree \(G=(V,E)\), with each vertex an indivisible office, plot, or time slot. All agents have the same additive utility \(u:V\to\mathbb{Q}_{\ge0}\), so the type set is \(T=\{u\}\) and \(\mu_u=1\). The regime is a large population of interchangeable research groups or households using many identical tree-shaped facilities. Thus the number of agents is large while the number of types is \(\tau=1\).
To make the population genuinely continuous without fractionalizing goods, consider a large number \(K\) of copies of the resource template. Each copy remains an ordinary finite graph with indivisible items. Let \(\lambda_A\) be the fraction of copies using connected allocation \(A\), where \(A\) may contain \(r\) agents and \(r\lambda_A\) is the corresponding agent mass per copy. The constraints are \(\sum_A\lambda_A=1\) and \(\sum_A r(A)\lambda_A=\rho\), where \(\rho\) is the prescribed average population mass per resource copy. The support of \(\lambda\) must consist only of allocations that are simultaneously PMMS and SMMS, hence MMS. For an allocation \(A\), PMMS is exactly the paper’s condition: every agent’s bundle must meet \(\operatorname{PMMS}(A_i\cup A_j)\) for each neighboring bundle, with the paper’s convention for empty bundles.
The question is therefore: given \(G\), \(u\), and rational agent density \(\rho\), does there exist such an allocation measure \(\lambda\), and can one produce it? A rational \(\lambda\) is realized by taking sufficiently many finite copies: \(K\lambda_A\) copies receive the ordinary indivisible allocation \(A\). The continuous object is the mass of interchangeable agents and allocation frequencies, not a fractional office or plot.
This should be Class A. For every integer \(r\), Corollary 6.8 supplies a polynomial-time fair allocation on a tree. For nonintegral \(\rho\), mixing the solutions for \(\lfloor\rho\rfloor\) and \(\lceil\rho\rceil\) gives a finite-support \(\lambda\). The result is particularly credible because the paper’s dynamic programming and SMMS machinery already compresses the large population into tree-structured utility information; the continuum removes the irrelevant enumeration of interchangeable agents.
The scenario is plausible: a university may allocate offices across many tree-shaped buildings to a large cohort of research groups whose valuations are standardized by office capacity, equipment access, and distance to shared facilities. A hospital or public authority could similarly allocate connected plots to many households with a common valuation rule. The authors would recognize the mirror because the graph, indivisibility, connectivity, PMMS, and MMS notions are unchanged. Only the repeated population is represented by mass.
A second, more heterogeneous anchor is Theorem 4.1, also proved in this paper. It states that for any connected graph and two agents with additive utilities, a \((3/4)\)-PMMS connected allocation can be found in polynomial time. Its continuous mirror is Mass-\((3/4)\)-PMMS for Connected Estates. Let \(T\) be a finite set of additive claimant types and let \(\eta_{ab}\) be the mass of two-claimant cases whose ordered claimant types are \((a,b)\). For each connected bipartition \(A=(X,Y)\) of \(G\), let \(x_{ab,A}\) be the mass of cases of type \((a,b)\) assigned according to \(A\). The constraints are \(\sum_A x_{ab,A}=\eta_{ab}\), and \(x_{ab,A}\) may be positive only when \(u_a(X)\ge(3/4)\operatorname{PMMS}_a(V)\) and \(u_b(Y)\ge(3/4)\operatorname{PMMS}_b(V)\). The objective is feasibility at factor \(3/4\), or maximization of the worst-case factor \(\alpha\).
This is a natural high-multiplicity regime for recurring inheritance settlements, divorce divisions, or standardized office-allocation cases. Theorem 4.1 gives a polynomial algorithm for each pair type, so setting \(x_{ab,A}\) to the corresponding allocation yields a Class A solution whose complexity depends on \(G\), \(\tau\), and encoding length, not on the number of cases. Each case still allocates indivisible goods; \(x\) records frequencies across many actual cases.
The weakest point is that these mirrors use many repeated local resource graphs rather than one shared graph on which every agent competes simultaneously. A hostile referee could call this an ensemble of instances rather than a single continuous society, and that criticism is real. The case survives only because repeated connected allocation is itself a plausible high-multiplicity regime, the paper explicitly motivates the two-agent case by inheritance and divorce, and no continuity has been moved into the goods or the fairness test. I would not claim that this covers the paper’s arbitrary-\(n\), heterogeneous-utility setting; that is a separate and genuinely harder continuous question.
The proposed anchors do not yet continuize a society. They continuize either a collection of independent finite instances or a distribution over complete allocations.
For Corollary 6.8, the singleton type space \(T=\{u\}\) with \(\mu_u=1\) loses the parameter that the theorem fundamentally depends on: the number \(n\) of agents. Both \(\operatorname{MMS}_n\) and SMMS depend on \(n\), and the connected partition itself has \(n\) bundles. A fixed finite tree with indivisible vertices cannot support an atomless population in any nontrivial way: it has at most \(|V|\) nonempty bundles. Beyond that point, either connected \(n\)-partitions cease to exist, or—under the paper’s empty-bundle convention—the MMS benchmark collapses to zero and fairness becomes vacuous.
The proposed copies repair capacity only by changing the object. A mass \(\lambda_A\) of copies allocated according to \(A\) is not a mass of agents in one society; it is a frequency distribution over complete finite allocation instances. Each copy is solved independently, and Corollary 6.8 is simply applied pointwise. The added density \(\rho\) is a resource-load parameter, not a population distribution over types. Moreover, mixing \(r\)-agent allocations mixes different benchmarks \(\operatorname{MMS}_r\), so there is no single continuous PMMS/SMMS object being evaluated. This is configuration or outcome-space continuity, which the programme explicitly excludes.
The strongest rescue would use one large tree and let both \(n\) and \(|V|\) grow. But then the utility vector \(u:V\to\mathbb{Q}_{\ge0}\), the topology, and the indivisible resource supply all change with the limit. The resulting problem is a continuum limit of resource graphs, not a continuization of the population alone. Using many identical trees instead returns to the independent-instance ensemble.
Theorem 4.1 is weaker still. It concerns exactly two agents. A distribution \(\eta_{ab}\) over claimant pairs therefore represents many independent inheritance or divorce cases, not many agents jointly allocating one graph. The variables \(x_{ab,A}\) assign a separate copy of \(G\) to each case; the theorem applies independently to every support type. Any interesting aggregate objective would be newly introduced rather than mirrored from the paper.
If instead all agents share one graph, the proposed formulation is invalid: two-agent allocations \(A=(X,Y)\) compete for the same vertices, and pairwise adjacency is induced by the final allocation. Type masses alone do not determine which bundles are adjacent or which types occupy them. Preserving that information requires mass over full connected allocation configurations, including their graph embedding—again a distribution over outcomes, not a society represented by \(\mu\).
Thus the common obstruction is structural: local PMMS is not an anonymous property of agent types. The comparison network is endogenous, created by assigning indivisible graph vertices. Fixed resources make population growth degenerate; scaled resources make the graph part of the continuum; replicated resources turn the model into a batch of independent instances.
This is a strong case against the two proposed mirrors and against any direct population mirror of the paper. It is not an airtight universal impossibility claim. A genuinely new model of large trees with a limiting utility field, or a repeated-estate model with a nonseparable cross-case objective, could be worthwhile. But each would be an extension or re-modelling requiring a second continuum or a new computational predicate. Under ChoCo’s population-only scope, the paper should not be greened on these anchors.
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.