Connected EF1 Allocations Exist in Discrete Chore Cutting

1 Introduction

• Bil`o et al. [2019; 2022] established EF1outer for at most four agents, and Igarashi [2023] extended existence to any number of agents for discrete cake cutting.EF1outer allows envy to be eliminated by removing a boundary item; for chores, removal is from the envious agent’s own bundle.Source: §1 · pp. 1–2

1.1 Our Results and Contributions

• The paper proves that connected EF1outer divisions of indivisible chores exist for any number of agents with monotone disutility functions.The authors note that goods protocols do not generally transfer to chores because positive-valuation protocols are not usually applicable to negative valuations [Aziz, 2016].Source: §1.1 · p. 2, §1 · p. 2
• The approach follows Simmons-Su: Sperner’s lemma identifies a fully colored simplex representing similar divisions in which different agents prefer different bundles.Finer triangulations yield approximate solutions that converge to an envy-free cake-cutting division.Source: §1.1 · p. 2
• The rounding adapts goods methods to chores by defining virtual functions that use bundle information and the item immediately outside its left boundary.Earlier virtual functions relied only on information between the knives; the paper says this information is unlikely to suffice for chores, even with left-right asymmetry [Bil`o et al., 2022; Igarashi, 2023].Source: §1.1 · p. 2
• Because rounding depends on the coloring functions, the paper rebuilds both virtual functions and the rounding procedure for monotone-disutility chores.The paper follows the general framework of [Bil`o et al., 2022; Igarashi, 2023] while changing these components.Source: §1.1 · p. 2

1.2 Other Related Work

• Related work spans connected cake-cutting, discrete connected allocations for goods and chores, and fairness-efficiency trade-offs.Prior work includes connected envy-free cake divisions [Stromquist, 1980; Su, 1999], discrete connectivity results, and chore complexity studies [Bouveret et al., 2019].Source: §1 · p. 1, §1.2 · pp. 2–3

2 Preliminaries

• The instance has m indivisible chores ordered on a path and allocated to n agents, each receiving a connected bundle with monotone disutility.The notation v_j denotes both a chore and its path position; the division partitions the path into connected bundles from left to right.Source: §2 · p. 3
• EF1outer requires that, for each pair of agents, either the assigned bundle is no more costly than the other’s or removing a boundary chore from it eliminates envy while preserving connectivity.This strengthens EF1 by requiring the bundle remaining after removal to stay connected.Source: §2 · p. 3

2.1 Sperner’s Lemma and Simmons-Su Protocols

• Sperner’s lemma guarantees at least one fully colored elementary simplex in a properly colored triangulation of a simplex.A fully colored simplex assigns distinct colors to its vertices.Source: §2.1 · p. 3
• In the Simmons-Su protocol, each vertex encodes a division and its owner marks the most-preferred piece; a fully colored simplex yields similar divisions with different agents preferring different pieces.For cake cutting, successively finer triangulations give approximate solutions converging to an envy-free connected division.Source: §2.1 · pp. 3–4, Figure 1 · p. 4

• Connected EF1outer divisions always exist for discrete chore division with an arbitrary number of agents and monotone disutility functions.Source: §3 · pp. 4–5
• Agents color owned vertices using chore-specific virtual disutilities rather than their actual disutilities, producing a Sperner coloring.Source: §3 · pp. 5–6
• For interior bundles, virtual disutility depends on bundle contents, adjacent knife positions, boundary items, and a neighboring left item outside the bundle.Source: §3 · p. 5
• A new rounding algorithm initializes bundles with items fully present across the simplex vertices, then allocates hidden items according to where they appear.Source: §3 · p. 6
• When adjacent boundary chores coincide, the proof treats them as one chore v*, so Bj is empty and P*j is either empty or {v*}.Source: §3 · p. 8
• The proof uses Sperner’s lemma to find a fully colored simplex, then assigns each agent their most-preferred bundle to obtain the division.The argument applies the lemmas cited in the proof to show the resulting division satisfies EF1outer.Source: §3 · p. 9

4 Conclusion

• Connected EF1 divisions exist for indivisible chores with any number of agents and monotone disutility functions.The proof builds on Simmons-Su’s framework and uses virtual disutility functions that incorporate information outside the bundle.Source: §4 · p. 9
• The computational complexity of finding an EF1 chores division remains unknown.The paper provides a constructive proof.Source: §4 · p. 9
• Whether EF1 and Pareto optimality are compatible in discrete chores division remains an open research question.The paper notes compatibility for additive disutilities without connectivity constraints, but asks whether it holds in the discrete chores setting.Source: §4 · p. 9