PaperlayerView exact revision on arXiv

Source-linked AI summary

A rainbow partition theorem for trees and connected maximin share allocations of chores

Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek, Jarosław Grytczuk, Zbigniew Lonc, Paweł Rzążewski

arXiv:2609.38628v1math.COcs.DMecon.THmath.OC

TL;DR

Whether chores on trees can be allocated in connected bundles within each agent’s connected maximin share was less clear. The paper proves a rainbow partition theorem for trees and uses it to establish connected maximin-share allocations for arbitrary monotone costs.

  • Problem

    Whether chores on trees can be allocated in connected bundles within each agent’s connected maximin share was less clear.

    Source: §1 · p. 1

  • Method

    The proof reduces the problem to inward partitions of oriented trees and applies Gale’s colourful KKM theorem on a simplex of edge weights.

    Source: §1.1 · p. 3, §1.3 · p. 5

  • Results

    Connected maximin-share allocations of chores exist on every tree for arbitrary monotone costs, with each agent receiving a connected subset of one of its benchmark parts.

    Source: §1 · p. 2

  • Takeaways & Limitations

    A rainbow partition can be computed in time k^O(k) plus polynomial time.

    Source: §1.1 · p. 4

    On cycles, the k−1 edge-occurrence bound is already best possible, so that threshold cannot generally be relaxed.

    Source: §5.3 · p. 19

Abstract

from arXiv · show

Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechl\'arov\'a, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if $\mathcal P_1,\ldots,\mathcal P_k$ are partitions of the vertex set of a finite tree, each into at most $k$ connected parts, then the vertex set can be split into disjoint sets $B_1,\ldots,B_k$, some possibly empty, such that each nonempty $B_i$ is connected and contained in a part of $\mathcal P_i$. Equivalently, if each of $k$ colours occurs on at most $k-1$ edges of a tree, then the vertices can be partitioned into connected sets labelled by distinct colours, none containing an edge of its own colour; in particular, one can choose for every colour a component of the forest obtained by deleting that colour so that the chosen components cover the tree. The bound is already best possible for paths, and for additive costs, the theorem is equivalent to the fair-division statement. The proof reduces the problem to inward partitions of oriented trees, which we obtain from the colourful KKM theorem on a simplex of edge weights, using a leaf-elimination labelling that remains compatible when weights vanish. We also give an algorithm running in time $k^{O(k)}$ plus polynomial time.

1. Introduction

The paper proves a rainbow partition theorem for connected partitions of a tree and uses it to settle the existence of connected maximin-share allocations for chores. It develops the proof through inward partitions of oriented trees and a colourful KKM argument.

1.2. Why trees, and why chores are harder than goods.

  • The goods case on trees has a polynomial-time solution, but the chore analogue is harder because taking an acceptable bundle can disconnect the remaining tree.The four-cycle example also shows that connected allocations of this kind need not exist on cycles.Source: §1 · p. 1, §1.1 · p. 4, §1.2 · p. 4

1.1. Main results.

  • For arbitrary monotone costs, every tree admits a connected MMS allocation, with each nonempty bundle contained in a part of that agent’s MMS-attaining partition.For additive costs, existence of connected MMS allocations for all instances on a given tree is equivalent to the rainbow partition theorem there.Source: §1 · p. 2, §1.1 · p. 3
  • For k connected partitions of a finite tree, each with at most k parts, the vertices can be allocated to k indices so every nonempty piece is connected and lies within a part of its indexed partition.If the tree has at least k vertices, all pieces can be nonempty.Source: §1.1 · p. 2
  • Equivalently, if each of k edge-colours occurs at most k−1 times, the vertices can be partitioned into connected pieces with distinct labels, each avoiding edges of its own colour.In particular, one can choose a component of each colour-deleted forest so the chosen components cover the tree.Source: §1.1 · p. 3

1.3. Proof strategy.

  • The proof reduces the problem to inward partitions of oriented trees, using colourful KKM on a simplex of edge weights and a leaf-elimination labelling compatible with vanishing weights.The labelling constrains the labels inside merged components to a set sized to their available vertices.Source: §1.1 · p. 3, §1.3 · pp. 5–6

1.1. Main results.

  • For paths, the bound of at most k−1 occurrences per colour is sharp; on cycles, k−1 parts suffice and k parts do not.Source: §1.1 · pp. 3–4
  • A rainbow partition can be computed in k^{O(k)} plus polynomial time, and an additive-chore allocation in n^{O(n)} plus polynomial time.Source: §1.1 · p. 4

1.4. Related work.

  • The theorem gives a connected, disjoint version of cooperative colouring for a class of dense graphs built from connected partitions of a common tree.Source: §1.4 · pp. 6–7

2. Preliminaries

The preliminaries establish tree properties and an edge-colour formulation used to prove the rainbow partition theorem. They also normalize instances and show that empty pieces can be eliminated when the tree has at least as many vertices as colours.

2.1. Tree facts.

  • Connected sets in a tree contain the unique paths between their vertices; contracting a connected partition yields a tree, and deleting a set of edges creates one more component than the number of deleted edges.These facts support the path, quotient, and component arguments used throughout the proofs.Source: §2.1 · pp. 7–8

2.2. The edge-colour form.

  • The rainbow partition statement is equivalent to the edge-colour statement, and any solution also yields a cover by choosing one component of each colour-deleted forest.Partitions with at most k parts correspond to deleting at most k−1 boundary edges; the covering form follows by extending each allocated piece to a component.Source: §2.2 · pp. 8–9

2.3. Normalization.

  • Arbitrary admissible edge-colour instances can be normalized to singly coloured edges with unchanged per-colour counts, then saturated while preserving solution transfer.The transformations contract uncoloured edges, subdivide edges carrying multiple colours, and attach pendant edges to colours below the k−1-edge bound.Source: §2.3 · p. 9

2.4. Nonempty pieces.

  • If the tree has at least k vertices, any solution with empty pieces can be converted into one with all pieces nonempty.Repeatedly move a leaf from a piece with at least two vertices into an empty piece; connectivity and the relevant containment or edge constraint are preserved.Source: §2.4 · p. 10

3. From inward partitions to rainbow partitions

The inward-partition theorem yields balanced and integer splittings of trees, which drive an induction proving the rainbow partition theorem. The proof contracts one colour’s edges, splits the quotient into smaller instances, and combines their solutions.

3.1. Balanced splittings.

  • Corollary 3.1 partitions a tree into at least two connected regions and groups of indices of matching sizes, with each nonzero-index group member’s region having nonpositive measure.Orient each edge toward a side of nonnegative mass; inwardness ensures every component outside an inward set has nonpositive mass, and Theorem 1.4 supplies the splitting.Source: §3.1 · p. 10
  • For a tree Q=(W,D) with s≥2 vertices, if each of the s−1 nonnegative integer-valued vertex functions e_c has total e_c(W)=s−1, Corollary 3.2 yields partitions as in Corollary 3.1.Source: §3.1 · p. 10
  • For probability distributions, connected regions and equal-sized index groups can be chosen so each grouped nonzero index assigns its region measure at most, or at least, the group’s proportional share.The two directions follow from the respective choices µc(v)=1/s−νc(v) and µc(v)=νc(v)−1/s.Source: §3.1 · p. 10

3.2. Proof of the rainbow partition theorem.

  • Theorem 1.2 follows by induction after contracting one colour’s edges and splitting the quotient tree into connected parts that define smaller admissible instances.The quotient has k vertices; Corollary 3.2 groups parts and colours with matching sizes and bounds each local colour count by its part size minus one.Source: §3.2 · p. 11
  • In the saturated induction step, solutions of the local instances combine into a rainbow partition of the original tree, with every nonempty piece connected.The example illustrates the reduction: the quotient path is split into {H1} and {H2,H3}, then local solutions cover the corresponding vertex sets.Source: §3.2 · p. 11, Figure 3 · p. 12

4. Inward partitions of oriented trees

The paper proves an inward-partition theorem by assigning weighted reversal costs to vertices of an oriented tree and finding common edge weights for several orientations. A leaf-elimination labelling and the colourful KKM theorem keep the assignment valid when weights vanish and components merge.

4.1. Weighted reversal costs.

  • A vertex’s weighted reversal cost is the total weight of edges that must be reversed to direct every edge toward it; minimizers form inward components of the zero-weight-edge forest.On a positive-weight edge, the cost changes by that edge’s weight between its endpoints.Source: §4.1 · p. 12

4.2. The common-weight theorem.

  • Theorem 4.2 finds common edge weights and assigns distinct minimizing vertices to s−1 orientations of a tree.The injection maps each orientation to a vertex minimizing its weighted reversal cost.Source: §4.2 · p. 12
  • Theorem 4.2 yields a nontrivial connected partition whose parts are inward for their assigned orientations, with one free index.The proof groups vertices and indices by the components remaining after deleting positive-weight edges; the free index cannot be replaced by an s-th orientation in general.Source: §4.2 · p. 13

4.3. A labelling compatible with coarsening.

  • The leaf-elimination labelling assigns a component the first edge toward the largest edge in the support, or that largest edge when incident to it.Under coarsening, labels inside a merged part fit its internal edges plus one designated boundary edge, a set of exactly the part’s size.Source: §4.3 · pp. 13–14, Figure 4 · p. 14

4.4. The colourful KKM theorem and the limit argument.

  • Gale’s colourful KKM theorem supplies a common limiting weight vector and distinct labels, while the compatible labelling controls the component mergers caused by vanishing weights.The proof uses closedness of the minimizer condition and that positive coordinates at the limit remain positive nearby.Source: §4.4 · pp. 15–16

5. Sharpness and limitations

The section establishes sharpness on paths and cycles: relaxing the path bound by one part can defeat coverage, while cycles satisfy a stricter bound but fail at the next threshold. It also relates path instances to permutation subsequences and shows that aggregate edge counts do not replace per-colour bounds.

5.1. One additional edge.

  • On a path, one partition with k+1 parts and k−1 partitions with k parts may have no choice of one part from each covering all vertices.The construction uses a path with N = k(k−1) + 1 edges and a repeated colour word followed by one extra 0.Source: §5.1 · p. 16

5.2. Paths and permutation words.

  • For paths, a solution exists exactly when some ordering of the colours is not a subsequence of the edge-colour word.If every colour occurs at most k−1 times, some ordering is omitted, so the path bound holds.Source: §5.2 · pp. 17–18
  • For k≥4, counterexample paths exist with k²−2k+4 edges, and for k≥5 this is strictly fewer than k(k−1).Thus a bound on the total number of coloured edges cannot replace the individual per-colour bounds.Source: §5.2 · p. 18

5.3. Cycles.

  • For cycles, connected partitions with at most k−1 parts admit a rainbow partition, and this bound is best possible for every k ≥ 2; for k=2, the four-cycle is a failure example.Source: §5.3 · pp. 18–19
  • A covering by selected components need not be convertible into a connected partition subordinate to those components on a branching tree.On paths, by contrast, every such covering contains a solution.Source: §5.4 · p. 19

6. Fair division consequences

The paper transfers the rainbow partition theorem to connected maximin-share allocations of chores on trees with monotone costs. It also establishes the converse combinatorial connection for additive costs and gives the packing counterpart for goods.

6.1. Conventions.

  • The connected MMS benchmark can be defined using at most n parts or, when |V(T)|≥n, exactly n parts, without changing its value.Monotonicity permits splitting parts until there are exactly n, and empty bundles extend connected allocations when needed.Source: §6 · p. 19, §6.1 · p. 19

6.2. Proof of Theorem 1.3.

  • For monotone costs, every tree admits a connected MMS allocation in which each agent’s nonempty bundle lies within a part of that agent’s benchmark partition.The proof chooses benchmark-attaining partitions and applies the rainbow partition theorem.Source: §6.2 · p. 20
  • A constructed additive cost makes any connected set costing at most 1−η stay within a benchmark part, where η=1/(4k).Every edge joining distinct parts has endpoint costs summing to at least 1+η.Source: §6.2 · p. 20

6.3. The packing counterpart for goods.

  • For goods, if each agent has at least k pairwise disjoint connected candidate bundles, the tree can be partitioned into k connected bundles, each containing one candidate for its agent.Applying this packing result to parts of maximin-share partitions yields connected MMS allocations of goods on trees.Source: §6.3 · pp. 20–21

7. Beyond trees

Beyond trees, the paper classifies exactly which connected graphs retain the rainbow partition and packing properties. Both properties hold precisely for triangular cacti, equivalently for graphs with no cycle of length at least four.

7. Beyond trees

  • The graph-extension question is resolved by classifying connected graphs that retain the rainbow partition and packing properties.Those properties respectively yield connected MMS allocations for chores and goods under the corresponding monotone valuations or costs.Source: §7 · p. 21

7.1. Graphs with a long cycle.

  • Any connected graph containing a cycle of length at least four admits two-part partitions that defeat both the rainbow partition and packing conclusions.The construction begins with four connected arcs on the cycle and extends the partitions to the rest of the graph.Source: §7.1 · p. 21

7.2. Triangular cacti.

  • A connected graph has no cycle of length at least four exactly when it is a triangular cactus, and every triangular cactus has both properties.The proof converts triangles into new vertices to form a tree, transfers partitions to that tree, and transfers the resulting sets back.Source: §7.2 · p. 22

7.3. The characterization.

  • For connected graphs, being a triangular cactus, having no cycle of length at least four, and having either partition property are equivalent.Connected MMS allocations of chores for all monotone costs and agent counts likewise exist exactly for triangular cacti; the analogous goods conclusion follows from packing.Source: §7.3 · pp. 22–23

8. Algorithms

The paper gives a finite-search algorithm for rainbow partitions whose superpolynomial dependence is confined to the number of colours. It also derives an algorithm for additive connected MMS allocations and notes that polynomial-time solvability in both input size and colour count remains unresolved.

8. Algorithms

  • A rainbow partition for k edge sets, or for k input partitions, can be computed in time k^O(k) plus polynomial time in the tree size and k.Source: §8 · p. 23
  • The search enumerates boundary-edge sets, then tests whether a matching assigns each resulting component a compatible colour.For partition inputs, the algorithm first computes the edge sets joining distinct parts.Source: §8 · p. 23
  • For nonnegative rational additive costs, a connected MMS allocation can be computed in time n^O(n) plus a polynomial in the input length, and in polynomial time for fixed n.The algorithm computes each agent’s benchmark partition and then applies the rainbow-partition algorithm.Source: §8 · p. 23
  • The paper leaves open whether rainbow partitions or additive connected MMS allocations can be found in time polynomial in both tree size and k.The authors also do not know whether these search problems belong to PPAD.Source: §8 · p. 24

9. Open problems

The open problems ask about the computational complexity of rainbow partitions and connected MMS allocations, extensions beyond trees, and conditions for unequal entitlements. They also identify implications for weighted maximin shares.

9. Open problems

  • Can a rainbow partition subordinate to k connected partitions of a tree, or an additive-chores connected MMS allocation on a tree, be computed in polynomial time, or is the search problem in PPAD or hard for it?It suffices to consider singly coloured instances with at most k(k −1) edges.Source: §9 · p. 24
  • The full conclusion holds for all k on triangular cacti, while cycles satisfy it when each connected partition has at most k −1 parts.Open questions ask whether a bound depending on a graph parameter suffices more generally, and about approximate connected MMS allocations on graphs with cycles; 7/6-approximate allocations are known for three agents on cycles [62].Source: §9 · p. 24
  • The condition that the sum of reciprocal part counts is at least 1 does not guarantee a rainbow partition, as shown by the path with colour word 3231323.The question is which conditions on the part counts guarantee a rainbow partition, with implications for connected weighted maximin shares for chores.Source: §9 · p. 24
Loading 2609.38628v1…