Improving the Bounds on Approximating Weighted Maximin Share for Chores

Trung Thanh Nguyen; Khaled Elbassioni; Jörg Rothe

cs.GTOct 11, 2026

Improving the Bounds on Approximating Weighted Maximin Share for Chores

Authors: Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe

Organizations: Faculty of Data Science and Artificial Intelligence, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE · Institut für Informatik, MNF, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany

Abstract

We investigate the problem of allocating indivisible chores among agents with arbitrary positive weights and additive nonnegative cost functions. An allocation is said to be $α$ -weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $α$ times her weighted maximin share. We establish that every instance admits a $4.124234528$ -WMMS allocation. Moreover, for instances in which all weights and costs are rational numbers represented in binary, we give an algorithm that computes a $4.12424$ -WMMS allocation in time polynomial in the number of agents, the number of chores, and the total binary encoding length of the input. Complementing these upper bounds, we construct a family of instances with strictly positive, identically ordered costs for which the optimal WMMS approximation factors converge to $e$ . Together, our results substantially narrow the previously best-known gap of $[2,12]$ established by Li et al.~\cite{LWX26} to $[e,4.12424]$ .

Figures & tables

Work	Existence upper bound	Universal lower bound
Aziz–Chan–Li [ 5 ]	$n$	$4/3\approx 1.333$
Wang–Li–Lu [ 28 ]	$O(\log n)$	$(1+\sqrt{3})/2\approx 1.366$
Li–Wang–Xing [ 20 ]	$12$	$2$
Seddighin–Seddighin [ 22 ]	$20$	—
This work	$\boldsymbol{4.124234528}$	$\boldsymbol{e\approx 2.71828}$

Table 1: Results for approximating WMMS allocations with chores.

\begin{array}[]{ll}\displaystyle\sum_{i:(i,h)\in E_{\rho}}x_{ih}=1,&\forall h\in\mathcal{M},\\[5.69054pt] \displaystyle\sum_{h:(i,h)\in E_{\rho}}c_{ih}x_{ih}\leq\beta w_{i},&\forall i\in\mathcal{N},\\[5.69054pt] x_{ih}\geq 0,&\forall(i,h)\in E_{\rho}.\end{array}

Algorithm 1 A polynomial-time

4.12424

-WMMS allocation algorithm

Recipient group	$M_{1}$	$M_{2}$	$M_{3}$	$M_{4}$
$G_{1}$	$1$	$1/2$	$1/4$	$1/8$
$G_{2}$	$1/2$	$1/2$	$1/4$	$1/8$
$G_{3}$	$1/4$	$1/4$	$1/4$	$1/8$
$G_{4}$	$1/8$	$1/8$	$1/8$	$1/8$

Table 2: Per-item costs in the first four blocks of the lower-bound family. Block

M_{j}

contains

2^{j-1}

items. The plateau in row

i

covers its own and all earlier blocks.

Fair Resource Allocation

Fair resource allocation studies how to distribute scarce goods, services, and computing capacity equitably while accounting for efficiency and constraints.

See all 56 papers

Maximin Share Guarantees via Limited Cost-Sensitive Sharing
Feb 24, 2026Hana Salavcova, Martin Černý, Arpita BiswasFair Resource Allocation Multi-Agent Resource Allocation
Charles University, Prague, Czech Republic · Rutgers University, New Jersey, United States
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
Oct 4, 2026Thi Ngoc Anh Vu, Trung Thanh Nguyen, Khaled Elbassioni +1Submodular Optimization Social Choice Theory
Faculty of Computer Science, Phenikaa University, Hanoi 12116, Vietnam · DataOptLab, National Economics University, Hanoi 11616, Vietnam · Khalifa University of Science and Technology, Abu Dhabi 127788, UAE +1
Simultaneous Envy and Equitability Guarantees
Aug 26, 2026Hadi Hosseini, Shraddha Pathak, Lirong Xia +1Social Choice Theory Fair Resource Allocation
Penn State University · Rutgers University

Feb 24, 2026J/K move · Enter open · S save

Maximin Share Guarantees via Limited Cost-Sensitive Sharing

Hana Salavcova, Martin Černý, Arpita Biswas

Charles University, Prague, Czech Republic · Rutgers University, New Jersey, United States

Fair Resource Allocation Multi-Agent Resource Allocation Social Choice Theory

Open paper AskPDF arXiv

We study the problem of fairly allocating indivisible goods when limited sharing is allowed, that is, each good may be allocated to up to

k

agents, while incurring a cost for sharing. While classic maximin share (MMS) allocations may not exist in many instances, we demonstrate that allowing controlled sharing can restore fairness guarantees that are otherwise unattainable in certain scenarios. (1) Our first contribution shows that exact maximin share (MMS) allocations are guaranteed to exist whenever goods are allowed to be cost-sensitively shared among at least half of the agents and the number of agents is even; for odd numbers of agents, we obtain a slightly weaker MMS guarantee. (2) We further design a Shared Bag-Filling Algorithm that guarantees a

(1 - C)(k - 1)

-approximate MMS allocation, where

C

is the maximum cost of sharing a good. Notably, when

(1 - C)(k - 1) \geq 1

, our algorithm recovers an exact MMS allocation. (3) We additionally introduce the Sharing Maximin Share (SMMS) fairness notion, a natural extension of MMS to the

k

-sharing setting. (4) We show that SMMS allocations always exist under identical utilities and for instances with two agents. (5) We construct a counterexample to show the impossibility of the universal existence of an SMMS allocation. (6) Finally, we establish a connection between SMMS and constrained MMS (CMMS), yielding approximation guarantees for SMMS via existing CMMS results. These contributions provide deep theoretical insights for the problem of fair resource allocation when a limited sharing of resources are allowed in multi-agent environments.

Abstract

Fair Resource Allocation

Explore similar work

Maximin Share Guarantees via Limited Cost-Sensitive Sharing

Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations

Simultaneous Envy and Equitability Guarantees