Submodular Max-Min Allocation under Identical Valuations
Kimon Boehmer · 2026
Read Submodular Max-Min Allocation under Identical Valuations by Kimon Boehmer (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-12417.txt.
Introduction
Kimon Boehmer studies max-min allocation when all players share the same valuation function. Items must be divided to maximize the least-satisfied player's share. Valuations are monotone and submodular, with diminishing returns from extra items. His greedy algorithm reaches a 0.4 approximation, beating the previous factor near 0.37. He also gives the first constant upper bound on the configuration LP integrality gap. The result extends to allocations constrained by k matroids, with an estimation method whose guarantee scales with k.
Catalog record
| CREATOR | Kimon Boehmer |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58656 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.12417
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Submodular Max-Min Allocation under Identical Valuations Kimon Boehmer Abstract In the problem of Submodular Max-Min Allocation , we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4 0.4 -approximation, improving the previously best factor of 10 27 ≈ 0.37 \frac{10}{27}\approx 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players’ allocations must be independent in k k given matroids, we derive a 𝒪 ( k ) \mathcal{O}(k) -estimation algorithm for max-min allocation subject to k k matroid constraints under identical valuations. DIENS, École normale supérieure, PSL University, Paris, France and LIP, ENS Lyon, France and https://www.kimonboehmer.net [email protected] {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10003752.10003809.10003716.10011141.10010040¡/concept_id¿ ¡concept_desc¿Theory of computation Submodular optimization and polymatroids¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10003716.10011138.10010041¡/concept_id¿ ¡concept_desc¿Theory of computation Linear programming¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10003636.10003810¡/concept_id¿ ¡concept_desc¿Theory of computation Packing and covering problems¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ I want to thank Chien-Chung Huang for introducing me to the topic and for many helpful dicussions. Also, I thank the anonymous reviewers for their valuable suggestions. ccs Theory of computation Submodular optimization and polymatroids ccs Theory of computation Linear programming ccs Theory of computation Packing and covering problems keywords Submodularity, Approximation algorithms, Allocation, Configuration LP † † runningauthor: K. Boehmer † † copyright: Kimon Boehmer † † editors: Pierre Fraigniaud † † event-title: 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) † † event-shorttitle: SWAT 2026 † † event-acronym: SWAT † † year: 2026 † † event-date: June 17–19, 2026 † † event-location: Copenhagen, Denmark † † series-volume: 370 † † articleno: 4 1 General context Item allocation is a fundamental problem in combinatorial optimization. Its task consists of distributing a set of items to a set of players , each equipped with a valuation function over subsets of items, with the goal of optimizing a specific objective function. The most well-studied objective functions are max-sum , i.e. maximizing the average satisfaction across all players, and max-min , maximizing the satisfaction of the least satisfied player. This work focuses on the latter objective function. Applications of max-min allocation range from assigning classrooms to charter schools [ 19 ] to sensor placement and scheduling [ 18 ] . Usually, research focuses on restricted classes of valuation functions that are both expressive and computationally tractable. For example, a common assumption is that each player has an additive valuation function; that is, each item is associated with a certain weight, and the satisfaction of a player is the sum of the weights of the received items. Another important and more general class of valuation functions are submodular functions; besides their useful algorithmic properties, they naturally model the law of diminishing returns in economics. This makes them especially interesting in the context of allocation. In this work, we will restrict our attention to the case where all players share the same submodular valuation function. It is interesting to note that the strongest hardness results of approximating submodular max-min allocation to a factor of 1-\frac{1}{e} already hold even for identical valuations [ 17 , 21 ] . 1.1 Our results We design a simple greedy algorithm, which we call Truncated Max-Sum Greedy , that achieves a 0.4 -approximation for identical submodular valuations, improving the previously best-known factor of \frac{10}{27}\approx 0.37 by Uziahu and Feige [ 28 ] . Essentially, given a fixed threshold \alpha , our algorithm greedily builds an allocation while ignoring players who already have items of value \alpha\cdot{\sf{OPT}} . Our main result is the following: Theorem 1 . There is a \frac{2}{5} -approximation for submodular max-min allocation under identical valuations. While showing a guarantee of \frac{1}{3} is rather straightforward, the improvement to \frac{2}{5} uses some graph-theoretic tools such as Hall’s theorem and certain arguments about the digraph of reallocations needed to transform the greedy solution into an optimal solution. Our algorithm also provides guarantees in more general settings. As an example, we consider the problem of submodular max-min allocation under identical valuations with an additional global cardinality constraint : The objective remains the same, but we are allowed to use at most k items in total. We show the following: Proposition 2 . There is a \frac{1}{3} -approximation for submodular max-min allocation under identical valuations with a global cardinality constraint. Furthermore, we study the integrality gap of the configuration LP for max-min allocation, an important LP relaxation for max-min allocation. We bound the integrality gap of the configuration LP by transforming certain primal integral solutions of the configuration LP to satisfying assignments of a dual formulation of this LP. Unlike to similar approaches when rounding configuration LPs [ 25 ] , our analysis only uses the fact that the primal integral solution is at most {\sf{OPT}} . As a result, our proof does not provide an algorithm (not even a non-trivial exponential one) for constructing an integral solution that demonstrates the integrality gap. Using this technique, we give the first constant upper bound on the integrality gap of the configuration LP for identical submodular valuations. Theorem 3 . The integrality gap of the configuration LP with identical submodular valuations is at most 3 . Additionally, we give a lower bound on this integrality gap. Proposition 4 . The integrality gap of the configuration LP with identical submodular valuations is at least 4/3 , even with 6 items and 3 players. We believe that the technique of theorem 3 can be used to show constant integrality gaps for submodular max-min allocation in more general settings. As an example, we also consider the case where we are given k matroids on the items and the sets that players receive must all be independent in all matroids. For this case, we also give a constant upper bound on the integrality gap, independent of k . Theorem 5 . The integrality gap of the configuration LP with identical submodular valuations and any number of matroid constraints is at most 5 . Accounting for the loss incurred when solving the separation oracle of the dual LP, this yields a \mathcal{O}(k) -estimation algorithm for max-min allocation subject to k matroid constraints. 1.2 Related work Additive valuations. Additivity is one of the simplest assumptions on the valuation functions of the players. In the general version where players may have non-identical additive valuation functions, the state-of-the-art algorithm by Chakrabarty, Chuzhoy and Khanna [ 7 ] achieves an approximation factor of \mathcal{O}(n^{\varepsilon}) . Interestingly, the best-known lower bound, shown by Bezáková and Dani [ 6 ] , only rules out a factor better than 2 . A well-studied special case is the so-called restricted assignment case, where players have identical valuations, but a bipartite graph between items and