Source-linked AI summary
Nearly Tight Bounds for Proportional Group Fair Divisions and One-Sided Discrepancy
Alexander Shekhovtsov, Georgy Sokolov, Mikhail Cherniavskii, Andrey Kupavskii
TL;DR
For asymmetric groups, earlier upper and lower bounds are far apart. This paper develops an approach to exploit one-sided discrepancy constraints and establishes almost-tight upper and lower bounds for the general setting.
Problem
Earlier bounds are far apart for asymmetric groups.
Source: §1.1 · p. 2Method
The paper develops an approach to benefit from one-sided discrepancy constraints and formulates linear discrepancy for (∆i)-structured matrices.
Source: §1.1 · p. 2, §1.3 · p. 5Results
The paper establishes almost-tight upper and lower bounds for the asymmetric-group setting in general.
Source: §1.1 · p. 2Takeaways & Limitations
For unbalanced groups, gifting covers possible large-row error, addressing the earlier approach’s Ω(√n1) error when one group is large and the others are singletons.
Source: §3 · pp. 12–13The log2 r term in Lemma 7 cannot be reduced, and Lemma 8 shows the log2(4r) term in Theorem 6 is necessary.
Source: §1.3 · p. 5, §2 · p. 7
Abstract
from arXiv · showhide
This paper studies the problem of fair division of indivisible goods among $k$ groups of $n_1,\ldots, n_k$ agents. We look at the worst downward deviation $\textit{PROP}(n_1,\ldots, n_k)$ of an agent in a group from its $1/k$-share. We improve the bounds of (Manurangsi and Meka, 2026) and show that $\textit{PROP}(n_1,\ldots, n_k) = \tilde{\Theta}(\sqrt{n/k})$, where $n = n_1 + \ldots + n_k$ is the total number of agents. For the proof of the upper bound, we develop novel discrepancy-type tools and, in particular, a way to efficiently work with one-sided discrepancy constraints.
1 Introduction
The paper studies proportional division of indivisible goods among groups with different agent valuations, focusing on the gap in earlier bounds for asymmetric group sizes. It develops one-sided discrepancy techniques and reports almost tight bounds for this general setting.
1.1 Fair division
- The paper reports almost tight bounds for proportional group fair division in general, addressing a gap between earlier bounds for asymmetric group sizes.The earlier bounds were tight for nearly equal groups but far apart for asymmetric groups.Source: §1.1 · p. 2
1.2 Discrepancy
- The paper develops techniques for one-sided discrepancy constraints, including a gifting algorithm that rebalances commodities among groups.The gifting mechanism is presented as part of the approach to benefit from one-sided constraints.Source: §1.1 · p. 2, §1.2 · p. 4
1.3 Discrepancy and the Top-down Beck-Fiala Problem
- The paper proves a discrepancy result for the Top-down Beck-Fiala problem, an asymmetric generalization of the Beck-Fiala problem.The stated setting allows different row-complexity bounds rather than requiring a uniform bound.Source: §1.3 · p. 5
1.4 Related work
- Prior work connected group fair-division questions, including approximate proportionality, with multi-color and weighted discrepancy.This connection provides the discrepancy-theoretic context for the paper's approach.Source: §1.4 · p. 6, Discrepancy · p. 6
2 Proof of Theorem 6
The proof rounds points in structured matrices to binary vectors while controlling row-wise error. It uses repeated partial rounding, row-norm accounting, and a stacked-matrix extension; the logarithmic factor in the bound cannot be reduced.
2 Proof of Theorem 6
- Dyadic bucketing of row weights bounds the number of rows whose ℓ1 norm exceeds 2t(log2 r + 2)∆i by counting total matrix mass within each bucket.The proof sums the per-bucket bounds over the dyadic ranges of ∆i.Source: §2 · p. 7
- The log2 r term in the row-count bound cannot be reduced, as demonstrated by a separate construction.The cited lemma begins with a matrix construction for sufficiently large m.Source: §2 · p. 7
- For a (∆i)-structured matrix A and any x0 ∈ [0,1]^m, an absolute C > 0 guarantees a binary x ∈ {0,1}^m with error bounded by C(log2(r) + 2)∆i.Source: §2 · pp. 8–9
- Repeated applications of the Lovett–Meka rounding corollary nearly round at least half the remaining coordinates at each step, then handle the final residual coordinates separately.The first phase iterates at most log2(m/∆n) + 2 times; the residual phase continues until all coordinates are nearly rounded before final rounding.Source: §2 · p. 9
- The rounding result extends to vertically stacked structured matrices, giving one binary vector that controls rows across all component matrices.The proof sorts rows by their ∆ values before applying the single-matrix theorem.Source: §2 · pp. 9–10
3 Upper Bound in Theorem 4
The section proves an upper bound by combining a structure-aware partition procedure and a gifting step that rebalances group advantages through bounded partial assignments. It completes the proof of Theorem 16 using a matrix bound on remaining-row column sums, together with a separate bound for gifted objects.
3 Upper Bound in Theorem 4
- Theorem 13 recursively halves the groups, applying Theorem 12 at each split to partition goods with row discrepancy controlled by the groups’ matrix structure.The recursion follows a binary tree from all groups to individual groups.Source: §3 · p. 11
- Gifting addresses the imbalance that can make direct use of Theorem 13 disadvantageous to a large group, by assigning carefully chosen goods before partitioning the remainder.Theorem 14 gives a partial assignment and constrains the remaining valuation matrices; its conditions account for rows whose potential error is covered by gifting.Source: §3 · pp. 12–13
- They show it is possible to rebalance the advantage/disadvantage that groups get when applying Theorem 13, by gifting or simply assigning a carefully chosen amount of goods to larger groups.Source: §3 · p. 12
3.1 Proof of Theorem 14
- Theorem 14’s proof uses k iterations, selecting goods for group i at iteration i; the gifting algorithm chooses an unassigned object maximizing summed valuations of active agents and removes agents once fulfilled.Source: §3.1 · p. 15
- The proof orders agents by removal time and forms B from the matrix after deleting gifted-item columns; B is (Δ_p1, Δ_p2, …, Δ_pns)-structured.For each position, the corresponding Δ value upper-bounds the column sums of the remaining rows.Source: §3.1 · pp. 17–18
- Considering whether an agent was removed from the active set establishes the desired bound (5) for gifted objects.The proof conditions on removal status and uses the threshold condition at the time of removal when applicable.Source: §3.1 · p. 18
- Claims 18 and 19 together conclude the proof of Theorem 16.Source: §3.1 · p. 18
4 Lower Bound in Theorem 4
The lower-bound argument uses weighted discrepancy and complementary valuations to turn deviations in either direction into evidence of downward dissatisfaction. It then places the construction in group-specific blocks so the discrepancy bound applies within subgroups.
4 Lower Bound in Theorem 4
- The theorem guarantees that the maximum absolute deviation of ⟨Ai, (v − 1/k)⟩ from 0 is at least √r − 1/16; complementary valuations convert an upward deviation into a downward one.Source: §4 · p. 19
- The matrix construction pads A with zero columns, forms complementary rows, and vertically concatenates the two matrices to obtain B.The proof invokes Theorem 21 for A and its padded version before applying the complementary-row construction.Source: §4 · p. 19
4.1 Proof of the Lower Bound
- Groups with fewer than 2r agents value every object at 1, while larger groups are partitioned into subgroups of 2r agents that value separate object blocks according to B.The remaining fewer than 2r agents in a large group receive arbitrary valuations, set to 0 for concreteness.Source: §4.1 · p. 19, Figure 1 · p. 20
- The construction uses all-ones valuations in small groups to force a roughly proportional allocation to large groups, where the discrepancy bound can be applied within a subgroup.This lets the proof use the bound of Lemma 22 inside a subgroup rather than across an entire group.Source: §4.1 · p. 20