| paper | Fair Division of a Graph into Compact Bundles |
| authors | Jayakrishnan Madathil |
| venue | IJCAI 2023 |
| filed under | fairalloc · indivisible |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Fix \(\alpha=1\), \(\beta\), and a graph \(H\) of treewidth at most \(w\). Given complete additive agent types \(a\in[\tau]\), rational per-building masses \(\mu_a\), valuations \(u_a(v)\), \(\rho=\sum_a\mu_a\), and \(U_a=\sum_{v\in V(H)}u_a(v)\), a local configuration is an integral allocation in one copy of \(H\) to a finite multiset of type-labelled agents, with pairwise disjoint \((1,\beta)\)-compact bundles and every type-\(a\) bundle worth at least \(U_a/\rho\). Decide whether finite-support masses \(\lambda_\sigma\ge0\) exist with \(\sum_\sigma\lambda_\sigma=1\) and \(\sum_\sigma\lambda_\sigma q_a(\sigma)=\mu_a\) for every type \(a\), where \(q_a(\sigma)\) counts type-\(a\) agents in configuration \(\sigma\).
A configuration LP over integral \((1,\beta)\)-compact allocations of one bounded-treewidth building, whose variables are masses of local patterns and whose constraints match prescribed masses of complete agent types.
The finite correspondence requires repeated disjoint copies, copy-symmetric valuations, and a repaired configuration model; Theorem 2 itself does not provide type-level separation or justify the original one-agent-per-type-per-building restriction.
fatal: False
Covers the proportionality component of Theorem 2 for \(\alpha=1\) in a repeated-building regime; it leaves envy-freeness, maximin fairness, strongly compact variants, \(\alpha>1\), and Theorem 1's hardness results untouched.
My strongest positive case is a narrow but credible mirror of the proportionality part of Theorem 2, proved in this paper. The theorem gives a pseudo-XP algorithm for \(\operatorname{PROP}\)-\((\alpha,\beta)\)-COMPACT-FD parameterized by treewidth and the number of agents. The continuous analogue should replace the large number of repeated agents by finitely many complete agent types and mass.
Call the problem \(\textsc{TW-Mass-PROP-(\alpha,\beta\))-Compact-FD}_{\infty}\). Its natural setting is a chain of many identical university buildings or hospital branches. Let \(H\) be the finite graph describing one building, with \(\operatorname{tw}(H)\le w\). There are \(\tau\) complete agent types. Type \(a\) is specified by its additive valuation \(u_a(v)\) for every room \(v\in V(H)\), together with all other parameters relevant to eligibility or assignment. Let \(\mu_a\in\mathbb{Q}_{\ge0}\) be the mass of type \(a\) per building, with \(\rho=\sum_a\mu_a>0\). The number of buildings is not part of the input: it is the high-multiplicity scale.
A local allocation pattern \(\sigma\) assigns each room of \(H\) either to no agent or to one bundle \(B_a^\sigma\) of a type \(a\). Each bundle must be \((\alpha,\beta)\)-compact in \(H\), and there is at most one agent of each type in a building. Put
\[ U_a=\sum_{v\in V(H)}u_a(v). \]
The pattern is proportional if every allocated type-\(a\) bundle satisfies
\[ u_a(B_a^\sigma)\ge \frac{U_a}{\rho}. \]
The continuous decision variable is a mass \(\lambda_\sigma\ge0\) assigned to each proportional local pattern. We ask whether there exists a finite-support vector \(\lambda\) satisfying
\[ \sum_\sigma \lambda_\sigma=1 \]
and, for every type \(a\),
\[ \sum_{\sigma}\lambda_\sigma \mathbf{1}[a\text{ is allocated in }\sigma] =\mu_a. \]
That is the whole problem: can the population of repeated buildings be distributed over whole, discrete, proportional compact allocations with exactly the prescribed type masses? A solution is the list of patterns with \(\lambda_\sigma>0\) and their rational masses. This is not a lottery over one room or a fractional bundle. It is a census of how many physically distinct buildings use each integral allocation pattern.
The finite bridge is exact for rational data. Choose \(K\) clearing all denominators. Construct \(K\) disjoint copies of \(H\), \(K\mu_a\) agents of type \(a\), and use \(K\lambda_\sigma\) copies of pattern \(\sigma\). Every room remains indivisible and every bundle remains compact. Moreover, each type-\(a\) agent’s proportionality threshold in the finite instance is
\[ \frac{K U_a}{K\rho}=\frac{U_a}{\rho}, \]
so the fairness predicate is preserved exactly. The continuous problem is therefore a high-multiplicity version of the paper’s own problem, not merely an outcome-space relaxation.
I expect this problem to be Class A when \(w,\tau,\alpha,\beta\) are fixed and valuations are polynomially bounded. Theorem 2 already supplies the relevant structural machinery: tree-decomposition dynamic programming, guessed compactness centres, rooted forests, distances, and valuation states. In the repeated-type setting, the large population scale \(K\) disappears; the algorithm should operate on the \(\tau\) type slots and generate a configuration LP over local patterns. A natural target is a pseudo-XP bound with the theorem’s \(n\)-dependence replaced by \(\tau\)-dependence, and hence polynomial time for fixed \(\tau,w,\alpha,\beta\) and unary-bounded values.
This is also why Theorem 2 is a better anchor than Theorem 1. Theorem 2 is proved here and explicitly exploits structural graph parameters and agent types. By contrast, Theorem 1’s strong NP-hardness reduction uses a distinct valuation pattern for essentially every set in an exact-cover instance. That is evidence for a boundary question, but not good evidence that hardness survives type aggregation.
The further questions are substantial: can the configuration LP be separated in polynomial time for bounded-treewidth \(H\); can binary-valued inputs be handled without the pseudo-polynomial dependence on \(W\); does the result survive if one type may receive several different bundles; and what are the corresponding mass formulations for envy-freeness and maximin fairness? The paper’s Theorem 2 covers all three fairness notions, but I would claim only its proportionality component here.
My weakest point is the resource scaling. With a fixed finite graph and an unbounded population, proportionality degenerates because only finitely many agents can receive nonempty bundles. The mirror therefore scales the item graph through repeated buildings as well as scaling the population. That is a joint population/resource high-multiplicity regime, not the narrowest possible population-only continuation. I think it is nevertheless the scenario the authors’ office-space motivation naturally suggests: many repeated local facilities, finitely many recurring agent roles, indivisible rooms, and compact bundles. If that regime is accepted, this is a recognizable and technically worthwhile continuous mirror of the paper’s main algorithmic result.
The strongest negative is that the proposed mirror is not yet a continuization of Theorem 2; it is a new repeated-facility allocation problem.
The claimed finite bridge hides a semantic mismatch. The equation
\[ \frac{K U_a}{K\rho}=\frac{U_a}{\rho} \]
assumes that every type-\(a\) agent values all \(K\) copies of \(H\). But the local-pattern formulation assumes that agents are assigned to one particular building and cannot receive rooms elsewhere. The original paper has neither building ownership nor locality constraints. If agents value only their own building, their proportionality threshold is instead \(U_a/(K\rho)\). If they value every building, the local restriction has been added by hand.
The mismatch is not repaired merely by clearing denominators. That construction proves only that a continuous solution can be expanded into a specially structured finite allocation. It does not show that every proportional compact allocation of the resulting instance decomposes into the proposed local patterns. For \(\alpha\ge2\), a compact bundle may span several disconnected building copies; the one-agent-per-type-per-building restriction is also absent from the paper. Encoding building identity into the agent type restores locality only by creating \(K\) distinct location-types, destroying the claimed fixed finite type space.
Keeping the graph fixed does not help. With \(m\) indivisible vertices and an unbounded number of positive-utility agents, proportionality eventually requires more nonempty bundles than the graph can supply; the remaining cases are infeasible or vacuous. Thus a nontrivial limit must scale the item graph as well as the population. That is legitimate as a possible research direction, but it is a joint population-and-resource high-multiplicity model, not the population continuization described by the programme.
The best repair is to define a genuine configuration model over repeated copies, allowing arbitrary numbers of agents of each type in each copy and, where compactness permits it, bundles spanning copies. But then the continuous object is a census of integral allocations of a multi-unit repeated-resource market. Theorem 2 does not establish that its agent-indexed treewidth dynamic programme can be compressed from \(n\) agents to \(\tau\) types: its states guess agent-specific roots and store the full matrix \(v_i(\pi(j))\). A type-level configuration LP and a polynomial separation procedure would be new results, not consequences of Theorem 2.
That is the strongest case against the anchor: as written, the proposed mirror has altered locality, resource supply, and sometimes the fairness threshold, so it should be labelled a re-modelling rather than a direct continuous mirror.
The universal negative, however, is not convincing. For \(\alpha=1\), take a disjoint union of repeated copies of \(H\), assign identical valuations across copies, and represent the population by rational masses over complete integral local allocation patterns. Compactness itself prevents a bundle from crossing components, and denominator clearing gives a credible clone correspondence. Repeated university buildings with recurring research-group types are also a natural high-multiplicity scenario. So the proponent’s exact formulation needs repair, but a worthwhile mirror of the proportionality part of Theorem 2 probably does exist.
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.