alphaFeedback

WorksComputer Science

Almost-MMS allocations with small agent redundancy

AI contributions
  • OpenAI’s ChatGPT-6.1 Sol
View details

Abstract

For a fixed ε≥0ε\ge 0, let ρε,nρ_{ε, n} be the maximum value of ρnρ_n such that, in every allocation instance with mm indivisible goods and (1+ε)n(1 + ε)n agents, there is a subset of nn agents with the following property. The allocation instance restricted to only this subset of nn agents has an allocation that gives each agent at least ρnρ_n-fraction of her nn-maximin share (MMS). When ε>0ε> 0 we refer to εnεn as the agent redundancy. The case ε=0ε= 0 is the standard setting without agent redundancy, and we use ρ0,nρ_{0,n} and ρnρ_n interchangeably. For allocation instances with additive valuations, % agents, it is known that 79≤ρn<1−Ω(1log⁡2n)\frac{7}{9} \le ρ_n < 1-Ω(\frac{1}{\log^2 n}) for every n≥2n \ge 2 (with stronger lower bounds for small nn). It is an open question whether ρnρ_n tends to~1 as nn grows. We show that with agent redundancy, the answer to this question is positive. That is, for every ε>0ε> 0, ρε,nρ_{ε, n} tends to~1 as nn grows. A straightforward corollary of this result is that for every c>0c > 0, if the number of items satisfies m≤(2−c)nm \le (2 - c)n, then the answer is positive also for ρnρ_n (with no agent redundancy). Adapting our techniques to a related setting, we also improve a recent result of Ezra and Garbuz, and show that without agent redundancy, there always exists an allocation that gives n−O(log⁡2n)n - O(\log^2 n) agents their full MMS.

Introduction

We consider fair allocations of mm indivisible goods to nn agents. Let MM denote the set of mm items to allocate, and let the set of agents be N:=[n]N := [n]. Every agent i∈Ni \in N has a valuation function viv_i defined on the subsets of MM. We assume that viv_i satisfies vi(∅)=0v_i(\varnothing)=0, and for every S1⊆S2S_1 \subseteq S_2 it holds vi(S1)≤vi(S2)v_i(S_1) \le v_i(S_2), i.e. viv_i is monotone and non-decreasing. In addition, we assume that every viv_i is additive: for every S⊆MS \subseteq M it holds vi(S)=∑e∈Svi(e)v_i(S)=\sum_{e \in S}v_i(e).

An allocation of items MM to agents NN is a partition (P1,…,Pn)(P_1,\ldots,P_n) of MM into nn disjoint sets, where agent ii “receives” the set PiP_i. We would like this allocation to be fair, for a certain definition of fairness. In this work, we will focus on a share-based notion of fairness called the maximin share [9], or MMS for short.

Definition 1.1. Let Pn\mathcal{P}_n be the set of all partitions (P1,…,Pn)(P_1,\ldots,P_n) of items MM into nn disjoint sets. For an agent ii with valuation viv_i, her maximin share is

MMS⁡(M,vi,n)=max⁡(P1,…,Pn)∈Pnmin⁡j∈[n]vi(Pj).\operatorname{MMS}(M,v_i,n)=\max_{(P_1,\ldots,P_n)\in\mathcal{P}_n}\min_{j\in[n]}v_i(P_j).

We will use MMS⁡(n)\operatorname{MMS}(n) to denote the MMS-value with respect to partitions of MM into nn sets.

A partition (A1,…,An)(A_1,\ldots,A_n) of MM is called an MMS-allocation if for every agent i∈Ni \in N it holds vi(Ai)≥MMS⁡(M,vi,n)v_i(A_i) \ge\operatorname{MMS}(M,v_i,n). That is, each ii values the bundle AiA_i given to her at least as high as her MMS. We will also consider approximate allocations: for a value ρ∈(0,1]\rho\in(0,1], we say that allocation (A1,…,An)(A_1,\ldots,A_n) is an ρ\rho-MMS allocation, if for every agent i∈Ni \in N it holds vi(Ai)≥ρ⋅MMS⁡(M,vi,n)v_i(A_i) \ge\rho\cdot\operatorname{MMS}(M,v_i,n). In this work, we will focus on the existence of exact / approximate MMS allocations for additive agents, in two closely related settings.

Our results, put in context

Our results, put in context

There are known examples showing that with additive valuations, MMS allocations need not exist. The first such examples were given in [20]. Later examples gave explicit upper bounds on ρ\rho for ρ\rho-MMS allocations, with ρ≤3940\rho\le\frac{39}{40} when n=3n = 3 [16], and ρ≤2021\rho\le\frac{20}{21} when n=4n = 4 [13]. However, as nn grows, the known upper bounds on ρ\rho deteriorate and tend to 1. The motivating question for our current work is the following conjecture.

Conjecture 1. For every ρ<1\rho< 1, there exists some nρn_\rho such that every allocation instance with additive valuations and n≥nρn \ge n_\rho agents has has a ρ\rho-MMS allocation.

We currently do not have strong beliefs as to whether the conjecture is true. So far, attempts to refute the conjecture have not been successful. However, they did provide examples of allocation instances with successively stronger lower bounds on the possible value of nρn_\rho as a function of ρ\rho, or equivalently, allocation instances with no ρ\rho-MMS allocation, with successively stronger lower bounds on the slackness 1−ρ1-\rho as a function of nn. In [20] the slackness was exponentially small in 1/n1/n, in [16] it was improved to be polynomially small, and in [13] it was further improved to be polylogarithmically small. To refute the conjecture, the slackness needs to be a constant independent of nn.

A recurring feature in all the above negative examples is that they allow what we refer to as agent redundancy. That is, for each of them, for every nn and its corresponding ρn\rho_n, in these examples one can have d>nd > n agents (for some dd that depends on nn) in which no subset of nn agents has a ρn\rho_n-MMS(n)(n) allocation. In [20] and [16], dd is nearly 2n2n, whereas in [13] dd is even exponential in nn. All negative examples for approximate MMS allocations with large nn that are known to us either hold in a setting with agent redundancy, or can be adapted to such a setting without significant change in the value of ρn\rho_n.

Our main positive result proves Conjecture 1, but only in the setting with agent redundancy.

Theorem 1.1. For every ε>0\varepsilon> 0 and ρ<1\rho< 1, there exists some nε,ρn_{\varepsilon,\rho} such that every n≥nε,ρn \ge n_{\varepsilon,\rho}, in every allocation instance with additive valuations and d≥(1+ε)nd \ge(1+\varepsilon)n agents, there is a subset of nn agents that have a ρ\rho-MMS(n)(n) allocation.

Note that in Theorem 1.1, every agent ii that is selected gets value ρ⋅MMS⁡(M,vi,n)\rho\cdot\operatorname{MMS}(M,v_i,n), and not only ρ⋅MMS⁡(M,vi,d)\rho\cdot\operatorname{MMS}(M,v_i,d). As d≥nd \ge n, MMS⁡(M,vi,n)≥MMS⁡(M,vi,d)\operatorname{MMS}(M,v_i,n) \ge\operatorname{MMS}(M,v_i,d). Moreover, the ratio between the two might be unbounded, for every d>nd > n (including d=n+1d = n+1).

A straightforward corollary of Theorem 1.1 is that Conjecture 1 holds when the number of items mm is noticeably below 2n2n.

Corollary 1.1. For every ε>0\varepsilon> 0 and ρ<1\rho< 1, there is some nε,ρn_{\varepsilon,\rho} such that every allocation instance with additive valuations, n≥nε,ρn \ge n_{\varepsilon,\rho} agents and m≤(2−ε)nm \le(2-\varepsilon)n items has a ρ\rho-MMS allocation.

We note that for ρ=1\rho= 1, Corollary 1.1 was known to hold when m≤n+log⁡nm \le n+\log n [14], and known not to hold when m≥n+c⋅log⁡nm \ge n+c\cdot\log n for some sufficiently large constant cc [13].

A closely related topic is a so called 1-out-of-dd MMS for d>nd>n, also known as ordinal MMS, first introduced in [7] (though also considered earlier in [9] with d=n+1d=n+1). A partition (A1,…,An)(A_1,\ldots,A_n) of MM is called a 1-out-of-dd MMS allocation, if for every agent i∈Ni \in N it holds vi(Ai)≥MMS⁡(M,vi,d)v_i(A_i) \ge\operatorname{MMS}(M,v_i,d). In this setting, the main question is how large should dd be (as a function of nn) to guarantee that exact MMS(d)(d) allocations exist. A series of work leading to [AGST24] established an upper bound of d=4⌈n/3⌉d = 4\lceil n/3\rceil, while a recent result by [12] showed that only sublinear number of additional bundles is needed, with d=n+O(nlog⁡n)d=n+O(\sqrt{n\log n}).

We further reduce the required number of additional bundles to only polylogarithmic in nn.

Theorem 1.2. Any instance with nn agents admits an MMS(d)(d) allocation with d=n+O(log⁡2n)d = n+O(\log^2 n).

Our Theorem 1.2 proof uses essentially the same techniques as our proof for Theorem 1.1. We note that any results on 1-out-of-dd MMS allocations (i.e [12] or Theorem 1.2) have the following interpretation in the setting with agent redundancy, discussed earlier.

Corollary 1.2. For every ε>0\varepsilon> 0, there exists some nεn_{\varepsilon} such that for all n≥nεn \ge n_{\varepsilon}, in every allocation instance with additive valuations and d≥(1+ε)nd \ge(1+\varepsilon)n agents, every subset of nn agents has an MMS(dd) allocation.

In some aspects, Corollary 1.2 is stronger than Theorem 1.1: it applies to every subset of size nn and not just some subsets of size nn, and there is no need for ρ<1\rho< 1. However, the big advantage of Theorem 1.1 is that it refers to MMS(nn) whereas Corollary 1.2 refers to MMS(dd). This advantage allows us to infer Corollary 1.1.

Overview of our algorithm

Here we explain the main steps of our algorithm that proves Theorem 1.1, the proof of Theorem 1.2 is easier and requires only a few of the ideas of Theorem 1.1 (even though later we will first give a full proof of Theorem 1.2 and only then Theorem 1.1). In the description, we slightly change notation. The total number of agents is nn (this was dd in the theorem), and among them we wish to select nn agents (this was dd in the theorem), with d=(1−ε)nd=(1-\varepsilon)n. We let qq be the smallest integer satisfying ρ≤1−2q\rho\le1-\frac{2}{q}. Thus, achieving (1−2q)(1-\frac{2}{q})-MMS(dd) suffices.

We make the following assumptions, standard in designing approximate MMS allocations.

Assumption 1. Without loss of generality, in the setting of Theorem 1.1 we can assume that

  • for every agent i∈Ni \in N and item e∈Me \in M it holds vi(e)∈[0,1]v_i(e) \in[0,1];

  • for every i∈Ni \in N, dd-partition Bi:=(Bi,1,…,Bi,d)\mathcal{B}_i := (B_{i,1},\ldots,B_{i,d}) of MM witnessing MMS(M,vi,dM,v_i,d) satisfies

∀j∈[d]:vi(Bi,j)=1;\forall j \in[d] : v_i(B_{i,j}) = 1;

We refer to the bundles in this dd-partition as the MMS bundles of agent ii.

  • ([BL16]) items M={e1,…,em}M=\{e_1,\ldots,e_m\} are ordered so that for every agent i∈Ni \in N it holds that

vi(e1)≥vi(e2)≥…≥vi(em).v_i(e_1) \ge v_i(e_2) \ge\ldots\ge v_i(e_m).

Under Assumption 1, every selected agent should be given a value of at least 1−2/q1-2/q.

References

  1. [1]Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. Fair division of indivisible goods: Recent progress and open questions. *Artif. Intell.*, 322:103965, 2023.DOI
  2. [4]Haris Aziz, Bo Li, Hervé Moulin, and Xiaowei Wu. Algorithmic fair allocation of indivisible items: a survey and new questions. *SIGecom Exch.*, 20(1):24–40, November 2022.arxiv.org/abs/2202.08713
  3. [5]Moshe Babaioff, Tomer Ezra, and Uriel Feige. On best-of-both-worlds fair-share allocations. In *Proceedings of the 18th International Conference on Web and Internet Economics*, WINE’22, pages 237–255, Cham, 2022. Springer.DOI
  4. [7]Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. Competitive equilibrium with indivisible goods and generic budgets. *Mathematics of Operations Research*, 46(1):382–403, 2021.arxiv.org/abs/1703.08150
  5. [8]Steven J. Brams and Alan D. Taylor. *Fair Division: From Cake-Cutting to Dispute Resolution.* Cambridge University Press, 1996.
  6. [9]Eric Budish. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. *Journal of Political Economy*, 119(6):1061–1103, 2011.
  7. [10]David A. Cox, John Little, and Donal O’Shea. *Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra.* Undergraduate Texts in Mathematics. Springer, Cham, fourth edition, 2015.
  8. [11]Leonard Eugene Dickson. Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. American Journal of Mathematics, 35(4):413–422, 1913.DOI
  9. [12]Tomer Ezra and Tamar Garbuz. Fair share allocations for almost all agents, 2026.arxiv.org/abs/2609.33234
  10. [13]Tomer Ezra and Tamar Garbuz. Improved impossibility bounds for maximin share allocations, 2026.arxiv.org/abs/2609.15085
  11. [14]Uriel Feige. On mms allocations with few items, 2026.arxiv.org/abs/2610.06125
  12. [15]Uriel Feige and Alexey Norkin. Improved maximin fair allocation of indivisible items to three agents, 2022.arxiv.org/abs/2205.05363
  13. [16]Uriel Feige, Ariel Sapir, and Laliv Tauber. A tight negative example for MMS fair allocations. In Proceedings of the 17th International Conference on Web and Internet Economics, WINE’21, pages 355–372, Cham, 2021. Springer.arxiv.org/abs/2104.04977
  14. [17]Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Beyond additive valuations. Artif. Intell., 303(C), 2022.DOI
  15. [18]Xin Huang and Shengwei Zhou. An fptas for 7/9-approximation to maximin share allocations, 2025.arxiv.org/abs/2511.13056
  16. [19]Rucha Kulkarni, Ruta Mehta, and Setareh Taki. On the PTAS for maximin shares in an indivisible mixed manna. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5523–5530, 2021.
  17. [20]David Kurokawa, Ariel D. Procaccia, and Junxing Wang. Fair enough: Guaranteeing approximate maximin shares. J. ACM, 65(2), February 2018.
  18. [21]Benny Lehmann, Daniel J. Lehmann, and Noam Nisan. Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, 55(2):270–296, 2006.
  19. [22]Trung Thanh Nguyen and Jörg Rothe. Approximate pareto set for fair and efficient allocation: Few agent types or few resource types. In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pages 290–296. International Joint Conferences on Artificial Intelligence Organization, 7 2020. Main track.DOI
  20. [23]Shmuel Onn. Nonlinear Discrete Optimization: An Algorithmic Theory. Zurich Lectures in Advanced Mathematics. European Mathematical Society Publishing House, Zürich, 2010.

Paper details

vlnc:W_3nyhgtcw
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

  • Computer Science

OpenAI’s ChatGPT-6.1 Sol · View statement →

Looking for related papers…
Contents