| paper | Fair Division of a Graph |
| authors | S. Bouveret, K. Cechlárová, Edith Elkind, Ayumi Igarashi, Dominik Peters |
| venue | IJCAI 2017 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable for binary-encoded rational inputs. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3.1
statement extracted from the paper’s text layer
Given a path \(P=(V,E)\), complete valuation types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and replicated per-capita supply, decide whether there are variables \(x_{t,I}\ge 0\) for integral intervals \(I\subseteq V\) such that \(\sum_I x_{t,I}=\mu_t\), \(\sum_{t,I\ni v}x_{t,I}\le\beta_v\), and \(x_{t,I}>0\Rightarrow u_t(I)\ge\rho\). In the uniform replication of a finite \(n_0\)-agent instance, take \(K\) path copies and \(K\) population copies, scale item utilities by \(1/K\), and set \(\beta_v=\rho=1/n_0\), so the finite quota \(1/(Kn_0)\) becomes the mass-limit quota \(\rho\).
A replicated-corridor high-multiplicity model: types carry mass \(\mu_t\), each unit receives one integral connected interval, \(x_{t,I}\) is assigned mass, \(\beta_v\) is per-capita item supply, and \(\rho\) is the consistently scaled proportional quota; the decision problem is feasibility.
The exact lift is not canonical: without fixing how copies are connected and how utilities, \rho, and \beta_v scale, the displayed formulation could become a new quota-and-supply problem rather than the limit of PROP-CFD. The proponent flags the supply issue but does not fully specify this normalization.
fatal: False
The mirror covers the path proportionality feasibility result in Theorem 3.1. It does not by itself cover the star and tree algorithms, complete envy-freeness, or the MMS results.
My lead mirror is a population-continuized version of PROP-CFD on a path.
The anchor is Theorem 3.1, proved in this paper: “PROP-CFD is NP-complete even if \(G\) is a path.” Here PROP-CFD asks whether a graph-constrained allocation exists in which every agent \(i\) receives a connected bundle worth at least \(1/n\) to that agent. The theorem is proved by reducing \(\mathrm{X3C}\). For an instance with \(3s\) elements and \(r\) triples, the construction uses a path containing three vertices for each triple, \(s\) “big” vertices, and one dummy vertex. There is one player for each triple, each element, and one dummy player. The dummy must receive the dummy vertex; element players must receive occurrence vertices; and each triple player must receive either its three-vertex interval or one big vertex. A proportional allocation exists exactly when the original elements admit an exact cover by \(s\) triples. The paper uses its stated unary utility convention, and proves NP-completeness rather than merely citing it.
The corresponding continuous problem, which I would call C-PROP-CFD\(_{\mathrm{path}}\), is this. The item-location graph is a path \(P=(V,E)\). There is a finite set \(T\) of complete agent types. Type \(t\) has a rational additive valuation \(u_t:V\to\mathbb{Q}_{\ge 0}\), normalized by \(\sum_{v\in V}u_t(v)=1\). The society is a rational mass vector \(\mu\), with \(\mu_t\ge 0\) and \(\sum_t\mu_t=1\). The path has per-capita inventory capacities \(\beta_v\): these represent many interchangeable copies of the item-location \(v\), while each individual copy remains indivisible. Finally, a rational proportional quota \(\rho\) is given; in the finite \(N\)-agent normalization, \(\rho=1/N\).
A solution is a collection of nonnegative variables
\[ x_{t,I}, \]
one for every type \(t\) and every integral interval \(I\subseteq V\). The variable \(x_{t,I}\) is the mass of type \(t\) receiving the connected bundle \(I\). It must satisfy
\[ \sum_I x_{t,I}=\mu_t \]
for every type \(t\),
\[ \sum_t\sum_{I\ni v}x_{t,I}\le \beta_v \]
for every item-location \(v\), and
\[ x_{t,I}>0 \quad\Longrightarrow\quad \sum_{v\in I}u_t(v)\ge \rho. \]
Thus every unit of mass receives an integral connected bundle; only the population of identical agents is divisible. The question is whether such an \(x\) exists.
This is a genuine high-multiplicity scenario: for example, many households or research groups occupy a large collection of repeated linear land corridors or office layouts. Agents fall into a small number \(\tau=|T|\) of standardized valuation types, while the number of agents and item copies is large. The graph constraint remains exactly the paper’s connected-bundle requirement. The per-capita inventory scaling is necessary: with finitely many indivisible items and an atomless population, proportionality would become impossible for almost everyone.
On a path every connected bundle is an interval, so there are only \(O(|V|^2)\) bundle configurations. The problem is therefore a polynomial-size linear program with \(O(\tau |V|^2)\) variables. I expect this mirror to be Class A: the NP-hardness in Theorem 3.1 dissolves when masses of identical agents can be distributed across integral intervals. The exact-cover obstruction is replaced by linear capacity and quota constraints. Clearing denominators recovers finite cloned populations, while the continuous model permits arbitrary rational mass splits among their possible bundles.
The original authors should recognize this as their problem rather than a generic fractional-allocation variant. Their model is explicitly about additive utilities, connected bundles, and proportionality; moreover, Theorem 3.3 already studies the number of player types as a parameter and its dynamic program tracks how many agents of each type are satisfied. The proposed mirror replaces those integer type-counts by masses, without replacing connected bundles by fractional pieces.
The weakest point is the inventory scaling. A strict reading of the paper’s single finite graph with one copy of each item would reject an atomless population because there is not enough indivisible supply. My mirror therefore uses the programme’s permitted co-modification: replicated item copies or repeated local path instances. If that is judged too far from the original setting, the proposal becomes an extension rather than a direct mirror. The substantive core nevertheless survives: type masses are active allocation variables, bundles remain integral and connected for each individual, and proportionality is still the paper’s predicate.
This mirror also raises useful follow-up questions: whether the same configuration LP remains tractable on trees or general graphs; whether a continuous complete-envy-free version of Theorem 4.1 retains Independent Set hardness; and how many finite clones are needed to round a rational continuous allocation while losing at most a prescribed additive amount of proportionality.
The strongest negative case is that the proposed formulation is not, as written, a continuization of Theorem 3.1. In the paper, proportionality is defined relative to the finite number of agents: each agent must receive value at least \(1/n\). In an atomless society there is no such \(n\). If one realizes the masses by \(K\) clones while retaining the paper’s normalized valuations, the quota becomes \(1/K\) and tends to zero; proportionality then degenerates. If instead one fixes \(\rho\), one has introduced a new quota problem rather than preserved proportionality.
The supply modification is equally substantive. The paper has one indivisible copy of each vertex. A positive mass of agents cannot all receive that item. The proposed capacities \(\beta_v\) therefore replace the paper’s item set by a repeated-resource model. This is not merely replacing agent counts by masses: it changes both the resource supply and the normalization of utilities. Nor is the lift canonical. Copies arranged as parallel paths, as a blow-up of each vertex, or as disjoint path instances induce different connectivity constraints.
One can repair these objections. Take \(K\) repeated path instances, \(K\) scaled copies of each type, define bundles as integral intervals within one instance, and normalize utilities and proportionality consistently. Then rational \(x_{t,I}\) can indeed be implemented by clearing denominators. But this establishes a new high-multiplicity fair-allocation problem, not a uniquely determined continuous form of Theorem 3.1. The paper gives no reason to privilege this replicated-corridor interpretation over other supply lifts.
That is the limit of the negative argument. The repaired model is mathematically coherent, retains indivisible connected bundles for every individual, and its polynomial-size interval LP is precisely the kind of Class-A phenomenon the programme seeks. Calling it “just fractional allocation” would be wrong, and calling its tractability uninteresting would be an impermissible answer-based objection. Thus I can reject the proponent’s formulation as under-specified, but I cannot honestly defeat the best repaired mirror. The universal negative case is weak: Theorem 3.1 is a genuine and worthwhile anchor.
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.