Source-linked AI summary
On Allocating Goods to Maximize Fairness
Deeparnab Chakrabarty, Julia Chuzhoy, Sanjeev Khanna
TL;DR
Max-Min Allocation asks how to allocate indivisible items to maximize the least agent's additive utility, but its approximation status had a gap between algorithms and hardness. The paper uses iterative LP rounding for the general problem and weighted-graph orientations for the 2-restricted case. It obtains an Õ(n^ε)-approximation for the general problem and a (2 + ε)-approximation for the restricted case, which remains hard to approximate below 2 even when uniform.
Problem
Max-Min Allocation seeks to maximize the minimum additive utility across agents, and its known general approximation and hardness bounds leave its approximability incompletely understood.
Source: §1 · p. 2Method
The general algorithm iteratively rounds LP solutions to construct smaller-terminal instances, while the 2-restricted algorithm uses a weighted-graph orientation approach.
Source: §1.1 · p. 4Results
The general problem has an Õ(n^ε)-approximation in n^O(1/ε) time, while the 2-restricted problem has a polynomial-time (2 + ε)-approximation and is NP-hard to approximate below 2 even when uniform.
Source: §1.1 · pp. 3–4Takeaways & Limitations
The 2-restricted case has a tight factor-2 boundary in the limit, while the general case admits an approximation whose guarantee depends on n and ε.
Source: §1.1 · pp. 3–4The general-problem LP can have an Ω(√m) integrality gap, so rounding that relaxation directly cannot yield better than O(√m).
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
Given a set of $m$ agents and a set of $n$ items, where agent $A$ has utility $u_{A,i}$ for item $i$, our goal is to allocate items to agents to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an $\tilde{O}(\sqrt{m})$-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an approximation algorithm that achieves an $\tilde{O}(n^{\eps})$ approximation for any $\eps=\Omega(\log\log n/\log n)$ in time $n^{O(1/\eps)}$. In particular, we obtain poly-logarithmic approximation in quasi-polynomial time, and for any constant $\eps > 0$, we obtain $O(n^{\eps})$ approximation in polynomial time. An interesting aspect of our algorithm is that we use as a building block a linear program whose integrality gap is $\Omega(\sqrt m)$. We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. We also investigate the special case of the problem, where every item has a non-zero utility for at most two agents. We show that even in this restricted setting the problem is hard to approximate upto any factor better tha 2, and show a factor $(2+\eps)$-approximation algorithm running in time $poly(n,1/\eps)$ for any $\eps>0$. This special case can be cast as a graph edge orientation problem, and our algorithm can be viewed as a generalization of Eulerian orientations to weighted graphs.
1 Introduction
The paper studies fair allocation by maximizing the minimum utility and develops approximation algorithms for both general and 2-restricted instances. Its main techniques use iterative LP rounding for the general case and weighted-graph orientations for the restricted case.
1 Introduction
- Max-Min Allocation models fairness by protecting the least-utility agent, unlike maximizing total utility, and is a dual of min-max scheduling.The paper notes that envy-free allocations and max-min allocations are not equivalent fairness notions.Source: §1 · p. 2, §1.2 · p. 5
- For general Max-Min Allocation, Bezakova and Dani gave the first non-trivial approximation algorithm, an (n − m + 1)-approximation, and proved NP-hardness of approximation up to any factor smaller than 2.Source: §1 · p. 2
1.1 Overview of Results and Techniques
- The general problem admits an Õ(n^ε)-approximation in n^O(1/ε) time, obtained by iteratively rounding LPs and constructing instances with fewer terminals.The guarantee holds for ε ≥ 8 log log n / log n.Source: §1.1 · pp. 3–4
- Although the general-problem LP has an Ω(√m) integrality gap, phased rounding uses almost-feasible solutions to create instances with fewer terminals.After poly(1/ε) phases, the process either certifies infeasibility of the integral optimum or yields an Õ(n^ε)-approximation.Source: §1.1 · p. 4
- For any fixed ε > 0, the paper also obtains a quasi-polynomial-time m^ε-approximation from its general theorem.Source: §1.1 · p. 4
- For 2-restricted instances, a poly(n, 1/ε)-time (2 + ε)-approximation is possible, while approximation within any factor below 2 is NP-hard even for uniform instances.The configuration LP has integrality gap exactly 2 in this special case; approximate LP solving accounts for the extra ε.Source: §1 · p. 3, §1.1 · p. 4
- The 2-restricted problem reduces to orienting weighted graph edges, and its approximation uses a weighted generalization of Eulerian orientations.The orientation gives each vertex more than half its incident weight minus its heaviest incident edge.Source: §1 · p. 2, §1.1 · pp. 4–5
1.2 Related Work
- Related work also studies submodular and sub-additive utilities, while the paper's algorithms assume additive utilities.For submodular utilities, the cited prior algorithm gives an Õ(n^1/4)-approximation; applying the paper's main theorem yields Õ(n^(1/2+ε)) in n^O(1/ε) time.Source: §1.2 · p. 5
2 Preliminaries
The preliminaries establish a structured framework for analyzing allocation solutions, including canonical reductions, private-item flows, and tree representations. They also describe a tree-decomposition step and bound the sum of y-values in the resulting subtree.
2 Preliminaries
- The target is an ˜O(n^eps)-approximation in time n^O(1/eps), with n^eps at least Omega(log^8 n).The paper assumes n is larger than a suitable constant.Source: §2 · p. 6
2.1 Polynomially Bounded Utilities
- An ˜O(n^eps)-approximate solution can be obtained after transforming utilities to the range 1 through 2n, with at most a factor-2 loss in the optimum.The transformation assumes nonzero utilities are at least 1 and caps utilities at the guessed optimum M.Source: §2.1 · p. 6
2.2 Canonical Instances
- An instance can be converted in polynomial time to a canonical instance with a 1-satisfying solution, and an alpha-approximation there yields a max{O(alpha log n), O(n^eps log n)}-approximation to the original.Canonical instances distinguish light and heavy agents and specify the item sets that can satisfy them.Source: §2.2 · pp. 6–7
2.3 Private Items and Flow Solutions
- A canonical optimum induces a feasible integral flow, while an integral alpha-feasible flow yields an alpha-approximate allocation.The flow network uses private items and item-to-agent edges to represent assignments; alpha-feasibility relaxes the incoming-flow requirement for light agents to N_A/alpha.Source: §2.3 · p. 9
2.4 Structured Near-Optimal Solutions for Canonical Instances
- Every canonical instance has an (h + 1)-approximate h-layered solution for h = 8/eps.The construction converts the flow forest so each root-to-leaf path has the same number of light agents, bounded by h.Source: §2.4 · p. 10
2.5 The [BS] Tree Decomposition
- The Bansal–Sviridenko decomposition partitions the bipartite graph into disjoint trees, each allowing all but one of its agents to be satisfied by its items.For each tree, the sum of agent values x_A is at least 1/2.Source: §2.5 · pp. 11–12
- Step 3 selects a child Aj with yAj,i < 1/2, removes an edge from i, and adds the subtree rooted at Aj, whose item vertices all have degree 2.The passage specifies the removed edge as (A, i).Source: §2.5 · p. 13
- For the added subtree τ′, the sum of yA′,i′ over i′ in I(τ′) is at most |I(τ′)| = |A(τ′)| − 1.Source: §2.5 · p. 13
3 An ˜O(√
The section gives an O(log n)-approximation for optimal 1-layered solutions, which supports an overall ˜O(√n)-approximation. Its rounding scheme decomposes the instance into trees, selects light agents, and routes flow while controlling congestion.
3 An ˜O(√
- O(log n) for 1-layered instances yields an overall ˜O(√n)-approximation for Max-Min Allocation.The analysis reduces to instances with M ≥ 4√n, where the optimal solution can be assumed to consist of trees with h(τ)=1.Source: §3 · pp. 13, 15
- The LP sends N_A·x_A flow units to each light agent while limiting its flow through any item in I* to x_A.Total flow through any item, across all types, is bounded by 1.Source: §3 · p. 13
- The rounding first decomposes the graph induced by I′ into trees, then rounds the assignment and handles the resulting congestion.The fractional assignment assigns each agent in Z a (1−x_A)-fraction of items in I′.Source: §3 · p. 14
- Tree decomposition and randomized rounding select one light agent per tree, then use tree items to satisfy the other agents.The selected light agent A is chosen with probability x_A/X, where X sums the x-values in its tree.Source: §3 · p. 14
- O(log n) vertex congestion with high probability is handled by routing ⌊N_A/log n⌋ integral flow units to each selected light agent.The integral flow follows internally disjoint paths, using the existence of a fractional flow and flow integrality.Source: §3 · p. 14
4 Almost Feasible Solutions for Multi-Layered Instances
This section develops LP rounding for multi-layered instances to produce almost-feasible solutions, despite an Ω(√m) integrality gap. Its flow-based method converts path collections with bounded vertex appearances and sufficient paths terminating at each receiver into vertex-disjoint collections with controlled termination counts.
4 Almost Feasible Solutions for Multi-Layered Instances
- The multi-layered LP-rounding algorithm yields paths satisfying the constraints except for limited overlaps between paths to terminals and paths to light agents.The LP has an Ω(√m) integrality gap; the later algorithm bypasses this obstacle while using this section’s rounding as a subroutine. The theorem’s path collections have disjointness, endpoint, and light-agent path-count properties.Source: §4 · p. 15
4.1 The Graph Nh(I, P)
- The graph uses layered subgraphs for trees of different heights, with copies of agents and items encoding paths and a separate routing part connecting flow to terminals.Each item-agent pair has at most h^2 copies; feasible integral flows in a layered subgraph represent trees whose height matches that subgraph’s number of layers.Source: §4.1 · p. 16
4.2 The LP
- The LP coordinates flow among light agents across layers and routes it within each layer, enforcing capacity constraints needed to control congestion during rounding.It also handles direct flow to terminals; its size and solution complexity are n^O(1/ε).Source: §4.2 · pp. 17, 19
4.3 The Rounding Algorithm
- The rounding algorithm routes to terminals, rounds flow within each subgraph, then cleans up congestion to construct the path sets P1 and P2.With high probability, each item and heavy agent belongs to O(h^2 log n) paths, and the number of paths leaving a light agent is O(h^2 log n); P1 paths are vertex-disjoint and P2 paths are internally vertex-disjoint, though they may share endpoints.Source: §4 · p. 15, §4.3 · pp. 20–21
- The preceding path set P′′ limits appearances of nonterminal vertices and paths starting at light agents to α′, then is converted into P2 so P1 and P2 satisfy D1–D4.If a light agent has a path originating there in P′′ ∪ P1, at least N_A/2 paths in P′′ terminate there.Source: §4.3 · p. 22
- Under the lemma’s assumptions, the resulting paths include ⌊N_A/2β⌋ paths terminating at each receiver, with each vertex used at most once as a first or intermediate vertex.The paths start at vertices in L′ ∪ S, where S is the specified set of starting vertices.Source: §4.3 · p. 22
- A flow network routes the required units from senders and items to receivers; scaling the induced flow by β makes it feasible, and integrality yields the desired paths.The induced flow has value at least the sum of N_A/2 over receivers and violates edge capacities by at most β.Source: §4.3 · p. 22
5 An ˜O (nǫ)-Approximation Algorithm
The algorithm repeatedly uses LP-based almost-feasible assignments to reduce the number of terminals, then combines the resulting paths and private items into an approximate allocation. It achieves polylogarithmic approximation in quasi-polynomial time, with a separate quasi-polynomial-time O(m^ε) guarantee for constant ε.
5.1 The Algorithm
- Each iteration builds a canonical instance, computes an almost-feasible solution, and updates the light agents, terminals, private items, and satisfying paths.Previously used items for light agents are made available again when solving the current iteration’s canonical instance.Source: §5 · p. 22, §5.1 · p. 23
- The algorithm runs h = 8/ε iterations, shrinking the terminal set by a factor of at least n^ε/(32h^2α) per iteration until it is empty.The final private-item assignment and flow-paths form an αh+1 = 2(h + 1)α-approximate solution.Source: §5.1 · p. 23
- The path construction combines internally disjoint paths so agents in L′ ∪ L′′ receive at least floor(NA/(αj + α)) terminating paths.The construction uses a flow combining paths from P2 and Qj; paths in P1 are rerouted to limit conflicts with Q∗.Source: §5.1 · p. 24
A Path Rerouting Lemma:
- The rerouting lemma limits path conflicts by rerouting P1 paths and removing intersecting paths from Q∗, while tracking agents with too few terminating paths as bad.Bad agents can trigger further bad agents; the process continues until none remain, and their number is bounded by 2|Tj|/β.Source: §5.1 · p. 24, A Path Rerouting Lemma · p. 26
5.2 Approximation Factor and Running Time
- O(log^9 n)-approximation is achieved in n^O(log n / log log n) time by choosing ε = 8 log log n / log n.The general approximation factor is O(n^ε log n), and the LP-solving time is n^O(1/ε).Source: §5.2 · p. 27
5.3 A Quasi-Polynomial Time O(mǫ)-Approximation Algorithm
- For any constant ε > 0, a quasi-polynomial-time algorithm achieves an O(m^ε)-approximation.The section combines an O(1)-approximation for small m with the main n-based result for larger m.Source: §5.3 · p. 27
6 The 2-Restricted Max-Min Allocation problem
When each item is wanted by at most two agents, allocation is equivalent to orienting weighted graph edges to maximize minimum weighted in-degree. The paper gives a near-factor-two approximation for this case and proves a matching factor-two hardness threshold for the uniform version.
6 The 2-Restricted Max-Min Allocation problem
- A 2-restricted instance maps to a graph whose vertices are agents and whose item-edges carry one utility weight for each endpoint.Allocating an item to an agent corresponds to orienting its edge toward that agent; the objective is to maximize minimum weighted in-degree.Source: §6 · p. 28
6.1 Approximation Algorithm for Non-Uniform Graph Balancing
- The approximation algorithm guesses OPT, uses a configuration LP, and focuses on the subgraph of fractionally allocated items for the final orientation step.Items already allocated integrally are kept assigned, while the remaining agents in H need at least MA/2 utility from the fractional items.Source: §6.1 · pp. 28–29
- A (2 + ε)-approximation is obtained for non-uniform 2-restricted allocation by orienting the graph of fractionally allocated items and combining it with integral assignments.The orientation guarantees each agent in H at least MA/2 utility from those items.Source: §6.1 · pp. 29–30
6.2 Hardness of Approximation for Uniform Graph Balancing
- Uniform graph balancing is NP-hard to approximate within any factor 2 − δ, for δ > 0.Because uniform graph balancing and uniform 2-restricted allocation are equivalent, the same hardness applies to the allocation problem.Source: §6.2 · p. 31
A Proof of Lemma 6
The proof uses a path-prefix decomposition to reduce an arbitrary collection of paths to components with tightly controlled intersections. Applying that decomposition to the two path collections rules out canonical cycles, leaving single paths or two-prefix components.
A Proof of Lemma 6
- A canonical spider has multiple path legs sharing one head, with no other vertex appearing on more than one leg.The shared vertex is the head; the paths are its legs.Source: A Proof of Lemma 6 · p. 33
- A canonical cycle requires an odd number of paths whose intersections follow the specified consecutive-path pattern.Each path has a distinguished endpoint unique to that path, with restricted intersections at its other endpoints.Source: A Proof of Lemma 6 · p. 33
- The path-prefix theorem decomposes components into canonical spiders, canonical cycles, or a single unchanged prefix in polynomial time.The paths have distinguished endpoints that do not occur on other paths in the collection.Source: A Proof of Lemma 6 · p. 33
- For P1 ∪ P2, a canonical cycle is impossible, so each component is either one full prefix or two prefixes forming a canonical spider.The proof excludes cycles because a canonical cycle has an odd number of paths with every consecutive pair intersecting.Source: A Proof of Lemma 6 · p. 33
B The Integrality Gap of the LP
The LP admits a constructed instance with a fractional solution that 1-satisfies every agent, although every integral solution leaves some agent with utility at most 1. The algorithm uses path decomposition and another iteration to identify its constructed optimum M as infeasible.
B The Integrality Gap of the LP
- Each gadget contains M light agents with M private light items apiece, plus heavy agents and items that route flow toward a shared light agent.The construction makes M copies and adds a terminal heavy agent connected to each copy’s shared light agent.Source: B The Integrality Gap of the LP · p. 34
- The M-copy gadget has fractional LP value M, while every integral solution gives some agent utility at most 1, yielding a gap of M = Ω(√m).The construction has m = O(M^2) agents.Source: B The Integrality Gap of the LP · p. 34
- After path decomposition, the algorithm discards specified light agents and, in the second iteration, declares optimum M infeasible for the resulting instance.The decomposition identifies L*1 as a bad light agent.Source: B The Integrality Gap of the LP · p. 35