PaperlayerView exact revision on arXiv

Source-linked AI summary

A tight negative example for MMS fair allocations

Uriel Feige, Ariel Sapir, Laliv Tauber

arXiv:2104.04977v2cs.GT

TL;DR

Kurokawa, Procaccia and Wang give instances where no allocation gives every agent her maximin share, but their examples have exponentially small gaps. This paper constructs larger-gap examples, including a three-agent, nine-item instance where every allocation leaves someone with at most 39/40 of her MMS.

  • Problem

    Kurokawa, Procaccia and Wang show that MMS allocations need not exist, but their examples have exponentially small gaps, far below known positive guarantees.

    Source: §1 · p. 1

  • Method

    The paper constructs negative instances with larger MMS gaps than the examples of Kurokawa, Procaccia and Wang.

    Source: §1 · p. 1

  • Results

    39/40: with three agents and nine items, every allocation leaves someone at or below that MMS fraction; for integer-valued instances with at most nine items, totals up to 119 guarantee MMS.

    Source: §1.1 · p. 2, §1 · p. 2

  • Takeaways & Limitations

    Larger negative gaps help pursue tight guarantees, and the paper establishes tight bounds in special cases.

    Source: §1 · pp. 1–2

    The LP solution falls short of the 39/40 target and is not a negative example, since it still admits an MMS allocation.

    Source: §5.2 · p. 20

Abstract

from arXiv · show

We consider the problem of allocating indivisible goods to agents with additive valuation functions. Kurokawa, Procaccia and Wang {[JACM, 2018]} present instances for which every allocation gives some agent less than her maximin share. We present such examples with larger gaps. For three agents and nine items, we design an instance in which at least one agent does not get more than a $\frac{39}{40}$ fraction of her maximin share. {Moreover, we show that there is no negative example in which the difference between the number of items and the number of agents is smaller than six, and that the gap (of $\frac{1}{40}$) of our example is worst possible among all instances with nine items.} For $n \ge 4$ agents, we show examples in which at least one agent does not get more than a $1 - \frac{1}{n^4}$ fraction of her maximin share. {In the instances designed by Kurokawa, Procaccia and Wang, the gap is exponentially small in $n$.} Our proof techniques extend to allocation of chores (items of negative value), though the quantitative bounds for chores are different from those for goods. For three agents and nine chores, we design an instance in which the MMS gap is $\frac{1}{43}$.

1 Introduction

With differing additive valuations, an allocation giving every agent at least her maximin share need not exist. The paper gives stronger negative examples, including a tight nine-item result for three agents, and extends its constructions to more agents and chores.

1 Introduction

  • The maximin share is the highest value an agent can guarantee as the minimum bundle value in a partition, using that agent’s valuation for every bundle.An MMS allocation gives each agent at least her own MMS; with a shared valuation, one exists.Source: §1 · p. 1

1.1 Our results

  • 39/40: With three agents and nine items, some agent receives at most 39/40 of her MMS in every allocation, and no nine-item instance can force a larger gap.The nine-item instance has the largest possible gap for that item count.Source: §1.1 · p. 2
  • MMS allocations always exist when m ≤ n + 5; for three agents, nine items are therefore the smallest possible size of a negative example.The paper improves the prior m ≤ n + 3 bound.Source: §1.1 · p. 2, §1.2 · p. 3
  • For every n ≥ 4, examples with at most 3n + 3 items force some agent to receive no more than 1 − 1/n^4 of her MMS.The constructions adapt ingredients from, using a less demanding sufficient property and a modular-arithmetic design.Source: §1.1 · p. 3
  • For three agents and nine chores, the paper constructs an instance with an MMS gap of 1/43; it also reports that eight chores always admit an MMS allocation.The computer-assisted verification that nine chores have the largest possible gap is not detailed in the manuscript.Source: §1.1 · p. 3

2 An MMS gap of 1 40

The section constructs a three-agent, nine-item instance with MMS 40 for each agent and shows no allocation can give every agent her MMS. Its proof rules out all possible partitions by bounding bundle values under a combined valuation.

2 An MMS gap of 1 40

  • The instance arranges nine items in a 3-by-3 matrix and defines row, column, and unbalanced agents with different additive valuations.The unbalanced agent's MMS bundles are the pair p, diagonal d, and quadruple q.Source: §2 · pp. 5–6
  • No allocation gives all three agents their MMS of 40 in the constructed nine-item instance.The row agent values each row at 40, the column agent values each column at 40, and the unbalanced agent has three specified MMS bundles.Source: §2 · p. 6
  • A combined valuation M assigns each item its highest value among the three agents, and any MMS allocation would partition M into bundles worth 40 to 42.The total value under M is 3 × 40 + 2, which bounds the value of each of three bundles worth at least 40.Source: §2 · p. 6
  • If an MMS partition contains a two-item bundle, it must be p, forcing the remaining bundles to be d and q, a partition already excluded.The only possible three-item bundles containing e9 have value 42; the resulting remaining bundles must each be worth 40.Source: §2 · p. 6

3 MMS gaps that are inverse polynomial in the number of agents

For every number of agents n ≥ 4, the paper constructs negative examples using modified matrix-based valuations. The construction forces an MMS shortfall of at least 1/f(n), where f(n)=n^2(n−2)^2+n.

3 MMS gaps that are inverse polynomial in the number of agents

  • The construction for n ≥ 4 places selected items along an n-by-n matrix perimeter and diagonal, then creates row-type and column-type valuations from a base matrix.At least two agents have each valuation type, and the two group sizes sum to n.Source: §3 · p. 7
  • The base matrix B uses only seven distinct item values, with every row and column summing to tB=n(n−2)^2+1.The paper calls a bundle good when its value is tB; row and column partitions are examples.Source: §3 · p. 7
  • Every partition of B into n good bundles must split the bottom row, split the right column, or place items from both in a bundle excluding Bnn.The bottom row and right column are each split one item per bundle in the first two cases.Source: §3 · p. 7
  • The proof uses special items on the bottom row and right column to constrain good partitions, with a separate case analysis for n=4.For n≥5, the mixed case cannot reach tB; the n=4 case is addressed by checking the remaining combinations.Source: §3 · p. 8
  • Allowing B to have more than just row and column good partitions enables smaller integer entries than the construction pattern in.The proof pattern used in still applies despite this additional flexibility.Source: §3 · p. 8
  • Each row-type and column-type agent has MMS tV=ntB=n^2(n−2)^2+n after the base matrix is scaled and modified.Rows or columns supply the corresponding MMS bundles.Source: §3 · pp. 8–9
  • In every allocation, at least one player receives value at most tV−1, because each possible good partition incurs a one-unit loss for some row- or column-type agent.If any bundle is below tB in B, it also falls at least one short after the valuation transformation; otherwise the three structural alternatives force the loss.Source: §3 · p. 9
  • For every N ≥ 4, an instance with at most N + 4n − 7 items forces some agent to receive at most 1 − 1/f(n) of her MMS, where f(n)=n^2(n−2)^2+n and n=⌈(N+4)/2⌉.This strengthens the stated inverse-fourth-power gap; the item count is 3N+1 for even N and 3N+3 for odd N.Source: §3 · p. 9

4 An MMS allocation whenever m ≤n + 5

Every instance with n agents and at most n+5 items has an MMS allocation. The proof reduces the item and agent counts in selected cases, then handles the remaining small-agent cases with bundle arguments and matching.

4 An MMS allocation whenever m ≤n + 5

  • Every instance with n agents and m≤n+5 items has an MMS allocation, proved by induction after reducing to m=n+5 and considering n≤5.The proof assumes MMS bundles have size at least two; for n≥6, that assumption cannot hold when m=n+5.Source: §4 · pp. 10–11

4.1 Three agents, eight items

  • For three agents and eight items, the proof selects two-item bundles from their MMS partitions and applies a reduction lemma when bundles intersect.If the selected bundles are disjoint, each agent receives her bundle and the two remaining items are allocated arbitrarily.Source: §4.1 · p. 11

4.2 Four agents, nine items

  • For four agents and nine items, a bipartite graph connects agents to bundles they value at least at their MMS; Hall’s condition then yields an MMS allocation.The first three bundles each have degree at least three, the fourth has degree at least one, and every agent values some bundle at least her MMS.Source: §4.2 · p. 12

4.3 Five agents, ten items

  • For five agents and ten items, ordering the items lets the proof choose a pair bundle to which the reduction lemma applies, establishing an MMS allocation.The chosen pair is the bundle containing e1 whose second item has the highest index among the five candidate bundles.Source: §4.3 · p. 12

5 Tightness of MMS ratio for nine items

This section establishes the MMS bound for three agents and nine items by characterizing possible negative-example structures and bounding their gap, using LP and MIP methods to find and verify an example.

5 Tightness of MMS ratio for nine items

  • Every three-agent, nine-item instance has an allocation giving each agent at least 39/40 of her MMS, so no negative example has a gap larger than 1/40.The bound is verified by solving the refined linear programs for both possible structures.Source: §5 · p. 13

5.2 The LP approach

  • The two structures induce valuation constraints, and refining them into finitely many classes yields linear programs that a computer verifies have no negative example with a gap larger than 1/40.The initial LPs are under-constrained, so additional class-specific constraints are needed to exclude solutions that are not true negative examples.Source: §5 · p. 13

5.1 Only two possible structures

  • A negative example must have one of two structures: agents’ MMS partitions are rows and columns, while the third agent’s partition contains a pair, a diagonal, and the remaining four items.The pair is good for all agents, and the diagonal and quadruple are bad for the row and column agents.Source: §5.1 · p. 15

5.2 The LP approach

  • Under the parallel-diagonals structure, each agent’s MMS-partition bundles have value b; every allocation leaves some agent with value at most b−1, and bad cross-agent MMS bundles are worth at most b−1.Every item is worth at least 1. Except for two exceptions, (e6, e9) and (e8, e9), and two partial exceptions, vR(e8) ≥ vR(e2) and vC(e6) ≥ vC(e4), items in different bundles of an agent’s MMS partition differ in value by at least 1.Source: §5.2 · pp. 17–18
  • The initial LP’s b = 13 optimum certifies that every agent in a max-gap PD-instance gets at least 12/13 of her MMS, but its solution is not a negative example.That solution has an MMS allocation.Source: §5.2 · p. 20
  • Adding order constraints raises the LP optimum to b = 16, and three allocation constraints raise it to b = 19 in the 60-constraint root LP.The root LP is then used as the basis for a mixed integer program.Source: §5.2 · p. 21

5.3 Using mixed integer programming

  • The MIP extends the root LP with binary selected-order and selected-allocation constraints to explore item orderings and restrict solutions to max-gap instances.The implementation uses selected-order constraints for seven item pairs and selected-allocation constraints for forty allocations.Source: §5.3 · pp. 22–23
  • A MIP solution with b = 40 yielded a negative example proving Theorem 1, which the authors manually modified to make its correctness easier to verify.The solver could return several negative examples with b = 40 and did not necessarily find the one easiest for human analysis.Source: §5.3 · p. 23

6 Extension to chores

The paper extends its negative-example analysis to chores, where maximin share is defined using disutility and a three-agent, nine-chore instance has an MMS gap of 1/43.

6 Extension to chores

  • For chores, MMS is the minimum over n-partitions of the maximum disutility of a bundle in the partition.All chores must be allocated; the definition interchanges maximum and minimum relative to the goods definition.Source: §6 · p. 23
  • For R, each row has disutility 43 and gives her MMS; for C, each column has disutility 43 and gives her MMS.U’s MMS partition consists of the pair {e2, e4}, diagonal {e3, e5, e7}, and quadruple {e1, e6, e8, e9}.Source: §6 · p. 23
  • To analyze allocations, the proof defines M by taking each chore’s minimum disutility across the three agents.This reverses the goods analysis’s use of maximum values.Source: §6 · p. 23
  • In every allocation of the three-agent, nine-chore instance, some agent receives disutility at least 44, although the MMS is 43.The proof adapts the goods analysis; further proof details are omitted.Source: §6 · p. 24

7 Discussion

The discussion leaves open how large the MMS gap can be for goods, both with three agents and as the number of agents grows. It also notes that analogous questions apply to chores, with different quantitative bounds.

7 Discussion

  • The open questions concern goods; analogous questions apply to chores, but their quantitative bounds would differ.Source: §7 · p. 24
  • For three agents, the largest possible gap δ3 lies between 1/40 and 1/9, and narrowing this interval remains open.The authors suggest computer-assisted techniques may help determine δ3 more precisely.Source: §7 · p. 24
  • For n ≥ 3, the known bounds are 1/n^4 ≤ δn ≤ 1/4 + 1/(12n); whether δn tends to 0 remains open.The known results do not rule out convergence to 1/4, though the authors say they would be very surprised by that outcome.Source: §7 · p. 24

A Some further details on the MIP

The appendix describes how order constraints and mixed-integer programming are used for diagonal structures. For crossing diagonals, the MIP value is 47, compared with 40 for parallel diagonals.

A Some further details on the MIP

  • For parallel diagonals, many order constraints are implied by the root LP, which may explain why relatively few selected constraints suffice to enforce a consistent total order.Source: A Some further details on the MIP · p. 25
  • For crossing diagonals, the MIP value is 47, compared with 40 for parallel diagonals, using a root LP with 60 constraints in both structures.The crossing-diagonals root LP is extended to an MIP.Source: A Some further details on the MIP · p. 25
  • For crossing diagonals, additional useful order constraints can be inferred, while other constraints need not be added because they follow from existing constraints.One derived constraint is e4 ≥ e9 + 1.Source: A Some further details on the MIP · pp. 25–26
  • The authors balance the effort of deriving constraints analytically against adding binary selection variables to the MIP, aiming to keep both proofs and code manageable.Source: A Some further details on the MIP · p. 26

Related papers

Loading 2104.04977v2…