Almost Envy-Free Allocations with Connected Bundles

1. Introduction

• Connectivity matters for indivisible spatial or temporal resources because severely disconnected allocations may have little practical use.The paper models items as graph vertices and requires each allocated bundle to induce a connected subgraph.Source: §1 · pp. 1–2
• For monotonic valuations on a path, connected EF1 allocations exist for two, three, or four agents, while connected EF2 allocations exist for five or more.The results also guarantee the maximin share guarantee, and envy can be eliminated by removing an outer item that preserves connectivity.Source: §1 · p. 2
• For identical valuations, an egalitarian-welfare-optimal allocation can be made EF1 by reallocating items, and the identical-valuation and two- or three-agent procedures are efficiently implementable.The paper does not establish efficient computation for its Sperner-based cases.Source: §1 · pp. 2–3
• Prior concurrent work also adapts cake-cutting protocols to paths, but does not study non-path graphs or general non-identical valuations with more than two agents.It also gives a three-agent procedure with a constant number of connected components, rather than requiring connected bundles.Source: §1 · p. 3
• The discrete protocols adapt cake-cutting tools: moving knives alternate between edges and items, while Sperner-based arguments establish higher-agent existence results.Covering an item models hiding it, which can show that envy vanishes after its removal.Source: §1 · pp. 2–3
• For two agents, graphs guarantee EF1 exactly when their biconnected components can be arranged in a path; the corresponding characterization for three or more agents remains open.Graphs failing the condition, including a star, can fail even with identical, additive, binary valuations.Source: §1 · p. 3

2. Preliminaries

• Items are vertices of a finite undirected graph, and a bundle is a set of vertices inducing a connected subgraph.An allocation assigns each item to exactly one agent, with every agent’s bundle connected.Source: §2 · pp. 3–4
• Valuations are nonnegative, monotonic over connected bundles, and zero for the empty bundle; the model excludes bads or chores.The paper distinguishes identical valuations, which agree on every connected bundle, from additive valuations, whose bundle values sum item values.Source: §2 · p. 4
• Connected EF1 requires that each agent can eliminate envy toward another bundle by removing one item whose removal leaves that bundle connected.Thus, unlike unconstrained EF1, removing an interior item is not allowed when it disconnects the remaining bundle.Source: §2 · p. 4
• On the path instance 2–1–3–1, allocation (2–1, 3–1) is EF1, whereas (2, 1–3–1) fails because removing either outer item does not eliminate envy.The paper notes that the latter allocation would satisfy standard EF1 without connectivity constraints.Source: §2 · p. 4
• A graph guarantees EF1 for a specified number of agents when every allowed valuation profile admits a connected EF1 allocation.The definition also permits guarantees restricted to a specified class of valuations.Source: §2 · p. 4

3. EF1 existence for two agents

• A discrete cut-and-choose protocol on a path yields a connected EF1 allocation: Alice selects a lumpy tie, Bob chooses a side, and Alice receives the remainder with the tie item.A lumpy tie makes the two sides weakly comparable to Alice up to the tie item.Source: §3 · p. 5
• Every traceable graph has a bipolar numbering, while some non-traceable graphs do as well.Thus, the two-agent guarantee includes graphs beyond those containing a Hamiltonian path.Source: §3 · pp. 5–6

3.1. Characterization of graphs guaranteeing EF1 for two agents

• No non-trivial disconnected graph guarantees EF1 for two agents.A connected component with at least two valued items can be forced entirely to one agent, leaving the other envious beyond one good.Source: §3.1 · p. 6
• A graph admits a bipolar numbering if its block tree is a path, so the two-agent criterion can be checked in linear time.The paper states that the block tree and a bipolar numbering can be computed in linear time.Source: §3.1 · pp. 7–8
• If the block tree is not a path, the graph contains a trident, and identical additive binary valuations can make every connected allocation fail EF1.For a type I trident, the shared cut vertex and three separated valued vertices force an allocation with envy exceeding one good.Source: §3.1 · p. 8
• For two agents, a connected graph guarantees EF1 exactly when it admits a bipolar numbering, its block tree is a path, and it contains no trident.These conditions are equivalent even for guarantees restricted to identical, additive, binary valuations.Source: §3.1 · p. 8

• To adapt Stromquist’s procedure, the sword moves in half-steps, lumpy ties smooth jumps, and termination while an item is covered requires at least two shouters.Source: §4 · p. 9
• A lumpy tie splits a subsequence so each side is valued at least as much as the other side with the tie item included; the median tie defines left, middle, and right agents.Source: §4 · pp. 9–10
• At a median lumpy tie, the two-agent Lumpy allocation is EF1, and each recipient weakly prefers their bundle to either side bundle.Source: §4 · p. 10
• The protocol maintains left, middle, and right bundles, moves pointers, and assigns the left bundle when shouters or median-tie conditions trigger a case.Source: §4 · p. 10
• The moving-knife protocol finds an EF1 allocation for three agents on a path in O(m) time.Source: §4 · p. 11
• The algorithm terminates as the left bundle grows until at least two agents regard it as best, and its possible termination cases yield EF1 allocations.Source: §4 · p. 11

5. EF2 existence for any number of agents

• The proof applies Sperner’s lemma directly to indivisible goods, obtaining a stronger fairness guarantee than the earlier cake-rounding approach.That earlier approach bounded envy by 2umax.Source: §5 · p. 13
• EF2 is stronger than bounding envy by 2umax: in the 1–10–2–2 example, envy is 13 < 20 but the allocation is not EF2.The example has four path items and two agents with additive valuations.Source: §5 · p. 13

5.1. Sperner’s lemma

• A generalized Sperner lemma guarantees a fully-labeled simplex when each of n labeling functions is used once across its vertices.The proof’s labels encode agents’ most-preferred bundles in the corresponding partial partitions.Source: §5.1 · p. 14, §5.2 · p. 15

5.2. Existence of EF2 allocations

• The construction discretizes knife coordinates into integral or half-integral positions, with integral knives covering an item omitted from adjacent bundles.Each step through the relevant simplex moves one knife by half a step.Source: §5.2 · p. 15
• Agents label each partial partition with a most-preferred nonempty bundle, and Sperner’s lemma yields a sequence in which each agent’s selected bundle is a favorite.The fully-labeled simplex assigns each agent a distinct bundle index across the sequence.Source: §5.2 · pp. 15–16
• The rounding step combines items common to each bundle across the sequence with boundary items, producing a complete partition.Monotonicity ensures each agent values each final bundle at least as much as its basic bundle.Source: §5.2 · pp. 16–17
• For any number of agents with monotone valuations, a path admits a connected EF2 allocation.EF2 allows envy to be removed by taking up to two goods from the envied bundle while keeping it connected.Source: §5 · p. 13, §5.2 · p. 17

6. EF1 existence for four agents

• The earlier Sperner proof guarantees only EF2 because an agent’s expected bundle may differ from the rounded bundle by up to two goods.The discrepancy arises when an agent selects a favorite bundle from a partial partition while implicitly assuming its basic bundle remains unchanged after rounding.Source: §6 · p. 17
• For four agents, revised labeling functions and rounding make agents’ bundle expectations wrong by at most one good.The construction aims for each interior bundle to receive at least one adjacent boundary item, as the rounding scheme ensures.Source: §6 · pp. 17–18
• The virtual valuations treat end bundles differently from interior bundles when assigning values to bundles in a partial partition.The passage specifies separate cases for bundles 1 and 4 versus bundles 2 and 3.Source: §6 · p. 17
• A case analysis establishes that agents’ valuations of the rounded bundles are bounded by the corresponding virtual valuations.This proposition supports the argument that the allocation induced by agents’ preferred indices satisfies EF1.Source: §6 · pp. 18–19
• A connected EF1 allocation exists on a path for four agents with monotone valuation functions.The argument adapts the Sperner-based approach used to establish EF2 for any number of agents.Source: §6 · pp. 17, 19
• For five or more agents, the authors could not construct labeling and rounding schemes that keep bundle expectations accurate up to one item.With five agents, a middle bundle has neighboring bundles that are also interior.Source: §6 · p. 19

7. EF1 existence for identical valuations

• For identical valuations on a path, an EF1 allocation exists for any number of agents and can be found in polynomial time.The algorithm starts with a leximin allocation and then reallocates items from high-value bundles toward lower-value bundles.Source: §7 · pp. 19–20
• The leximin-optimal connected allocation need not be EF1, even with three agents and identical additive valuations.For the path with item values 1–3–1–1–1, the unique leximin allocation (1, 3, 1–1–1) induces envy even up to one good.Source: §7 · p. 19
• The algorithm fixes a worst-off agent and moves items inward from bundles that agent envies even up to one good.It processes the bundles outside-in; the construction preserves the worst-off agent’s position while removing that agent’s EF1 envy.Source: §7 · pp. 19–20, Figure 7 · p. 20
• The proof maintains the minimum utility and the set of agents receiving it throughout the reallocation loops.After the loops, the selected worst-off agent does not envy any other bundle up to one good, yielding EF1.Source: §7 · p. 20
• With identical valuations, dynamic programming finds a leximin allocation in time O(m^2n^2), and the remaining algorithm takes O(mn).The paper also describes a refined implementation with running time O(mn).Source: §7 · pp. 20–21

8. Concluding remarks

• For monotone valuations on traceable graphs, EF1 allocations exist for two, three, or four agents, and EF2 allocations exist for any number of agents.The latter results use Sperner’s lemma, which the authors apply in an indivisible-goods setting.Source: §8 · p. 21
• The existence of EF1 allocations on paths with five or more agents remains open.The authors could not construct labeling and rounding schemes that keep bundle expectations accurate up to one item for those cases.Source: §8 · p. 21
• Efficient implementations are given for identical valuations and for two- or three-agent cases, but efficient computation from the Sperner-based proofs is unclear.The authors know of no computational complexity result for finding EF1 or EF2 allocations on a path.Source: §8 · p. 21
• For two agents, the paper gives a forbidden-minor-type characterization of graphs that guarantee EF1 allocations.The paper also notes that extending the characterization to more agents presents difficulties.Source: §8 · pp. 21–22
• On paths, no connected allocation may be both EF1 and Pareto-optimal, and deciding whether one exists is NP-hard.This contrasts with the unconstrained setting described in the paper, where maximum Nash welfare yields both properties.Source: §8 · p. 22
• The paper considers goods with monotonic valuations; EF1 or EF2 existence for chores on a path remains open.The cited result establishes PROP1, not EF1 or EF2, for connected allocations on a path with chores.Source: §8 · p. 22

A.1. Maximin share allocations

• For a path, MMS is defined over connected partitions, and the paper notes that MMS allocations need not exist on cycles or complete graphs.The cited existence result for trees does not extend to those graph classes.Source: §A.1 · p. 25
• EF1 does not imply MMS for every allocation on a path, as a three-agent example leaves the middle agent below her MMS.The middle agent receives utility 1 despite an MMS value of 3.Source: §A.1 · p. 25
• 1/3-MMS is guaranteed by any EF1 allocation on a path when valuations are subadditive.The proof uses subadditivity and the fact that a path bundle intersects at most two other allocation bundles after accounting for removed goods.Source: §A.1 · p. 25
• Without subadditivity, EF1 does not guarantee any positive fraction of MMS, even with three path items and two agents.The example has MMS 1 but gives one agent utility 0 in an EF1 allocation.Source: §A.1 · p. 25
• For any chosen n−1 cut items on a path, each agent values at least one of the resulting n basic bundles at least as much as her MMS.The lemma underpins the appendix’s MMS guarantees for constructed allocations.Source: §A.1 · p. 26
• The paper’s constructed EF1 allocations on a path guarantee every agent her full MMS value.This is established for the discrete cut-and-choose protocol, the three-agent moving-knife protocol, and the identical-valuation and four-agent Sperner constructions.Source: §A.1 · p. 26

A.2. Example of an instance with no EFX allocation

• The path instance 2–3–1–3 with three agents has no connected EFX allocation.The listed connected divisions fail EFX, and allocations with an empty bundle fail as well.Source: §A.2 · pp. 26–27

A.3. Example of a non-traceable graph that guarantees EF1

• In the three-leaf star, sequentially assigning favorite available leaves and giving the center to the last agent yields EF1.Envy toward single-item bundles is bounded by removing one good; envy toward the last agent is bounded by removing the center.Source: §A.3 · p. 27

A.4. Efficient computation of SMMS allocations for identical valuations

• SMMS selects an allocation with maximum egalitarian welfare and uses the fewest losers to break ties.A loser is an agent who receives the minimum utility in the allocation.Source: §A.4 · p. 27, A suboptimal algorithm · p. 27
• The dynamic program tracks the best egalitarian welfare and number of losers for each prefix subpath and agent count.It reconstructs the final allocation from stored indices after computing these values.Source: A suboptimal algorithm · p. 27, An improved algorithm · pp. 29, 31
• Monotonicity reduces the dynamic program’s running time from O(m^2n) to O(mn) by enabling constant amortized-time rounds.The simple algorithm examines all candidate cut indices, whereas the refinement uses monotonicity to narrow the search.Source: §A.4 · p. 27, An improved algorithm · p. 28, A suboptimal algorithm · p. 28
• For each subpath and agent count, an optimal SMMS allocation can be found among allocations using three candidate cut indices.The candidates are k1[i,j], k2[i,j], and k3[i,j].Source: An improved algorithm · pp. 28–29
• The refined dynamic program computes an SMMS allocation in O(mn) time.SMMS maximizes egalitarian welfare and, among ties, minimizes the number of losers.Source: An improved algorithm · p. 29