Paper deep dive
Improving the Bounds on Approximating Weighted Maximin Share for Chores
Trung Thanh Nguyen, Khaled Elbassioni, Jörg Rothe
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 $\alpha$-weighted-maximin-share (WMMS) fair if the cost incurred by each agent is at most $\alpha$ 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]$.
Tags
Links
- Source: https://arxiv.org/abs/2610.15520v1
- Canonical: https://arxiv.org/abs/2610.15520v1
Trouble viewing inline? Open PDF directly →
Full Text
61,210 characters extracted from source content.
Expand or collapse full text
Improving the Bounds on Approximating Weighted Maximin Share for Chores Trung Thanh Nguyen †thanks: Faculty of Data Science and Artificial Intelligence, National Economics University, Hanoi 11616, Vietnam Khaled Elbassioni †thanks: Khalifa University of Science and Technology, Abu Dhabi 127788, UAE Jörg Rothe †thanks: Institut für Informatik, MNF, Heinrich-Heine-Universität Düsseldorf, 40225, Düsseldorf, Germany October 11, 2026 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.1242345284.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.124244.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][2,12] established by Li et al. [20] to [e,4.12424][e,4.12424]. Keywords. Fair division; indivisible chores; weighted maximin share; approximation algorithms; linear programming; scheduling. 1 Introduction Fair division is a fundamental problem in economics, mathematics, and computer science, concerned with allocating resources or responsibilities among agents in a manner that is perceived as equitable [19, 9, 3]. It arises naturally in a wide range of applications, including the allocation of public resources, the distribution of household duties, workload assignment, and the sharing of undesirable tasks [15]. A central challenge is to formalize fairness when agents have heterogeneous preferences or costs. Several influential fairness criteria have been proposed to address this challenge. Envy-freeness (EF) requires that no agent prefer another agent’s allocation to her own [27], while its relaxations, envy-freeness up to one item (EF1) [21, 10] and envy-freeness up to any item (EFX), accommodate the indivisibility of items by allowing envy to be eliminated through the removal of an appropriate item [11]. Proportionality requires that each agent receive a share commensurate with an equal division of the total value or cost [24]. Another prominent notion is the maximin share (MMS), which provides an agent with a fairness benchmark based on what she could guarantee herself by partitioning the items into bundles and receiving the least favorable bundle [10]. These criteria capture different aspects of fairness and have motivated extensive research on the existence, computation, and approximation of fair allocations, particularly when items are indivisible and exact fairness guarantees may be unattainable. The classical maximin-share criterion implicitly assumes that all agents have equal entitlements. In many applications, however, agents may have different rights, obligations, or capacities, making equal treatment inappropriate. The weighted maximin share (WMMS) extends the MMS benchmark to settings in which agents are assigned positive weights representing their relative entitlements or responsibilities [12]. Informally, in the allocation of indivisible chores, an agent evaluates her weighted maximin share by considering how she would partition all chores among agents with different weights, anticipating that she might receive the bundle that is most costly relative to its recipient’s weight. This benchmark reflects both the agent’s subjective costs and the asymmetry in agents’ entitlements. When all weights are equal, WMMS reduces to the classical MMS notion. It is also closely related to weighted proportionality [26], which assigns each agent a target cost proportional to her weight, and to weighted variants of envy-freeness. Unlike proportionality, however, WMMS explicitly accounts for indivisibility and the combinatorial structure of the chores. Moreover, while envy-freeness compares an agent’s allocation with those of other agents, WMMS provides an individual fairness guarantee defined independently of the allocation ultimately chosen. The study of WMMS is particularly well motivated by practical settings in which undesirable tasks must be distributed among participants with unequal responsibilities. For example, in workplace scheduling, employees may have different contractual workloads, working hours, or capacities, so that assigning everyone the same amount of work would not necessarily constitute a fair outcome. Similarly, the distribution of teaching duties among faculty members may need to account for differences in appointments, administrative responsibilities, or teaching commitments. Other examples include assigning maintenance tasks among organizations with different resource capacities, distributing computational jobs among heterogeneous participants, and allocating household chores among individuals with different agreed-upon responsibilities. In such settings, indivisibility is often unavoidable: a task, shift, or assignment may have to be allocated in its entirety to a single participant. Furthermore, agents may experience different costs for performing the same task. WMMS offers a natural framework for incorporating these heterogeneous costs and unequal entitlements into a common fairness benchmark. Beyond the existence of fair allocations, their efficient computation is a central concern. Even when an allocation satisfying a desired fairness criterion is guaranteed to exist, finding such an allocation may be computationally intractable. In particular, the indivisibility of chores and the heterogeneity of agents’ costs create combinatorial difficulties, while unequal weights introduce additional challenges in balancing individual fairness guarantees. These obstacles motivate the study of approximate WMMS allocations, in which each agent’s incurred cost is allowed to exceed her WMMS benchmark by a bounded multiplicative factor. The objective is to determine the smallest approximation factor that can be guaranteed for every instance and, equally importantly, the best factor achievable by a polynomial-time algorithm [12, 5, 6, 7, 28, 20, 22]. These two questions are conceptually distinct: an existential guarantee establishes the intrinsic limits of fairness, whereas an efficient algorithm determines whether such guarantees can be realized in large-scale applications. Complementary impossibility results, obtained by constructing instances for which no allocation achieves a better approximation factor, help identify the fundamental barriers imposed by indivisibility and unequal entitlements. Narrowing the gap between achievable approximation guarantees and impossibility bounds is thus a central objective in the algorithmic study of weighted fair division of chores. This paper aims to narrows both sides of that gap. The upper-bound proof does not round the weights or the item costs to a geometric grid, and it does not require a common ordering of the original valuation rows. The lower-bound construction, in contrast, is deliberately structured: its rows have one common ordering, all item costs are positive, and its number of chores equals its number of agents. 2 Related work and Our Contribution 2.1 Related work Despite the recent surge of research on MMS allocations of indivisible goods and chores (see, e.g., [18, 4, 8, 14, 3, 16, 2, 13, 1]), relatively little is known about the weighted setting, in which agents have unequal entitlements or weights [25]. Weighted MMS for goods. Farhadi et al. [12] were the first to study the notion of weighted maximin share (WMMS). For goods, they constructed an instance showing that no allocation can guarantee better than an n-approximation to WMMS. They complemented this impossibility result with a simple ordinal algorithm achieving a matching n-approximation guarantee; namely, every agent receives a bundle whose value is at least 1/n1/n of her WMMS. Weighted MMS for chores. It is not immediate whether results for goods in one setting carry over to the other [7]. Aziz, Chan, and Li [5] established the existence of an n-approximate WMMS allocation and exhibited a lower bound of 4/34/3. They also introduced the notion of optimal WMMS, which benchmarks an algorithm against the smallest common relaxation factor for which an allocation exists on the given instance. An approximation guarantee for this instance-dependent benchmark is conceptually different from a universal upper bound on the relaxation factor itself. Wang, Li, and Lu [28] obtained an O(logn)O( n) approximation guarantee and determined the exact worst-case ratio for two agents as (1+3)/2(1+ 3)/2. More recently, Li, Wang, and Xing [20] proved an upper bound of 1212 together with an asymptotic lower bound of 22, which constitute the most immediate benchmarks for our results. Independently, Seddighin and Seddighin [22] established a constant-factor guarantee of 2020. Work Existence upper bound Universal lower bound Aziz–Chan–Li [5] n 4/3≈1.3334/3≈ 1.333 Wang–Li–Lu [28] O(logn)O( n) (1+3)/2≈1.366(1+ 3)/2≈ 1.366 Li–Wang–Xing [20] 1212 22 Seddighin–Seddighin [22] 2020 — This work 4.124234528 4.124234528 ≈2.71828 e≈ 2.71828 Table 1: Results for approximating WMMS allocations with chores. 2.2 Our contribution We studied the allocation of indivisible chores among agents with arbitrary positive weights and additive nonnegative costs. Our contribution are as followss. 1. We prove that every instance admits a 4.1242345284.124234528-WMMS allocation, and that a 4.124244.12424-WMMS allocation can be computed in polynomial time for rational input. The upper bound follows from a lossless row-wise packing normalization, a restricted fractional assignment problem, and a continuum of dual-price inequalities. Integrating these inequalities cancels their scale-dependent correction terms; assignment rounding then incurs only the largest supported chore cost. 2. In the opposite direction, we construct strictly positive, identically ordered instances whose optimal WMMS factors converge to e. The construction uses geometrically growing groups, nested costs, and integral row-wise packing certificates. It establishes an unconditional existential lower bound, not an NPNP-hardness-of-approximation result. Together, the results place the optimal universal existence factor between e and 4.1242345284.124234528. 3 Preliminaries A problem instance of fair allocation is I=(,ℳ,w,v)I=(N,M,w,v), where =[n]N=[n] is the set of n agents, ℳ=[m]M=[m] is the set of m indivisible chores (or items); each agent is associated with a positive weight wiw_i, and an additive cost functions vi:ℳ→ℚ≥0v_i:M _≥ 0. For any subset X⊆ℳX , vi(X)=∑h∈Xvihv_i(X)= _h∈ Xv_ih, where vihv_ih denotes the cost of chore h for the agent i. Unless stated otherwise, we assume ∑i∈wi=1 _i w_i=1, and denote w∗:=maxj∈wjw_*:= _j w_j as the maximum weight among agents. An integral allocation (or assignment) is a complete partition A=(Ai)i∈A=(A_i)_i of ℳM into n disjoint subsets. We may use a vector =(xih)i∈,h∈ℳx=(x_ih)_i ,h to present a fractional allocation, where xih∈ℚ≥0x_ih _≥ 0 is the fraction of the chore h assigned to agent i, such that ∑i∈xih=1 _i x_ih=1 for every chore h∈ℳh . Definition 3.1 (Weighted maximin share (WMMS)). The weighted maximin share of an agent i is defined as μi=WMMSi=wimin(A1,…,An)maxj∈vi(Aj)wj, _i=WMMS_i=w_i _(A_1,…,A_n) _j v_i(A_j)w_j, (1) where the minimum ranges over complete integral partitions A. The agent evaluates every bundle using her own costs, but each bundle is compared with its designated recipient’s weight. Computing the weighted maximin share WMMSiWMMS_i is known to be NPNP-hard but can be well approximated [17]. In fact, computing WMMSiWMMS_i is exactly equivalent to the minimum makespan problem on uniform machines and thus can be approximated in polynomial time to within any factor of 1+δ1+δ, for any fixed δ∈(0,1)δ∈(0,1). The defining minimum (1) is attained because the instance I has finitely many O(nm)O(n^m) integral partitions. An allocation in which every agent incurs a cost no greater than her weighted maximin share (WMMS) does not always exist, even in the unweighted setting. This motivates the study of approximate WMMS allocations, which relax the fairness requirement by allowing each agent’s cost to exceed her WMMS by a bounded multiplicative factor. Definition 3.2 (Approximate α-WMMSWMMS). For α≥1,α≥ 1, an allocation A is α-WMMS if vi(Ai)≤αμiv_i(A_i)≤α _i for every agent i∈i . The value of α may depend on the size of the problem instance. We may assume that vi(ℳ)>0v_i(M)>0 for every agent i. Indeed, if vi(ℳ)=0v_i(M)=0 for some agent i, assigning all chores to this agent and leaving the other agents with empty bundles yields an exact WMMS allocation. Our goal is to determine the smallest constant α≥1α≥ 1 such that every instance admits an α-WMMS allocation. To this end, we establish several useful properties of the normalized cost functions, which will serve as key ingredients in deriving a universal approximation guarantee. Lemma 3.3 (Normalized cost function). Suppose every μi>0 _i>0, and define the additive cost function cic_i with cih=wivih/μic_ih=w_iv_ih/ _i. Then, for each i there is an integral assignment (Bji)j∈(B_j^i)_j such that ci(Bji)≤wj,(j∈).c_i(B_j^i)≤ w_j, (j ). (2) We call (Bji)j∈(B^i_j)_j the row-i packing. In particular, ci(ℳ)≤1c_i(M)≤ 1 and cih≤w∗c_ih≤ w_* for every chore h and agent i. An integral assignment with ci(Ai)≤Cwic_i(A_i)≤ Cw_i for every i gives a C-WMMSWMMS allocation for the original instance. Proof. Take a WMMS-defining partition in row i and multiply its inequalities by wi/μiw_i/ _i. Summing the resulting inequalities gives the total-cost bound; each item lies in a bin of capacity at most w∗w_*. Finally, vi(Ai)=(μi/wi)ci(Ai)≤Cμiv_i(A_i)=( _i/w_i)c_i(A_i)≤ C _i. ∎ The upper-bound proof works for any nonnegative matrix satisfying Equation 2, even if its normalized costs are strictly smaller than its weights. We refer to this hypothesis as the packing promise. It is stronger than the scalar inequalities ci(ℳ)≤1c_i(M)≤ 1, since the witnesses are whole-item packings. The proof uses their existence, not a common partition or an ordering shared across rows. If μi=0 _i=0 for some agent, every item costs zero to her. Indeed, a zero makespan with positive bin weights permits no positive-cost item. Assigning all chores to that agent solves the instance. Empty chore sets and the one-agent case are likewise immediate. We may therefore assume positive costs and a nonempty chore set whenever ratios are used. 4 A universal 4.124234528 upper bound We first introduce a function α:Ω⊆ℝ2→ℝ>0α: ^2 _>0, where Ω=(ρ,r)∈ℝ2:1<ρ<r =\(ρ,r) ^2~:~1<ρ<r\, and α(ρ,r)=ρ+1+ln(r/ρ)(1+lnρ)/ρ−1/r.α(ρ,r)=ρ+ 1+ (r/ρ)(1+ ρ)/ρ-1/r. (3) Let α⋆=min(ρ,r)∈Ωα(ρ,r). _ = _(ρ,r)∈ α(ρ,r). Lemma 4.1. α⋆=4.124234527128370976… _ =4.124234527128370976… Our main result is stated as follows. Theorem 4.2 (Universal upper bound). Every finite additive nonnegative chore instance with positive weights admits an α(ρ,r)α(ρ,r)-WMMS allocation for every r>ρ>1r>ρ>1. In particular, for every fixed ε>0 >0, an (α⋆+ε)( _ + )-WMMS allocation can be computed in polynomial time. Explicit rational parameters give a polynomial-time 4.124244.12424 guarantee. An overview of the Algorithm Suppose that the cost functions are normalized so that they admit an integral packing into bins whose capacities correspond to the agents’ weights. We introduce an eligibility threshold ρ>1ρ>1 and restrict assignments to agent–chore pairs whose normalized costs do not exceed ρ times the corresponding agent’s weight. On these eligible pairs, we formulate a fractional assignment linear program that minimizes the maximum normalized load across agents. By linear programming duality, its feasibility reduces to establishing an inequality between the total prices of chores and the weighted sum of dual multipliers. Using the row-wise packing property, we show that suitably capped dual prices can be packed into appropriately scaled capacities, yielding a family of inequalities across different thresholds. We further develop a multiscale analysis that combines these inequalities while retaining their scale-dependent correction terms. By integrating over a continuum of scales and carefully combining the resulting inequalities, the correction terms cancel, leading to an improved bound on the fractional assignment loads. We then apply assignment rounding, which increases each agent’s normalized load by at most the eligibility threshold ρ. Finally, optimizing the parameters yields a universal 4.1242345284.124234528-WMMS existence guarantee and a polynomial-time 4.124244.12424-WMMS approximation algorithm for rational inputs. The main steps are identified by Algorithm 1. Its correctness and thus the proof of Theorem 4.2 is presented in the following sections. Algorithm 1 A polynomial-time 4.124244.12424-WMMS allocation algorithm 1: Agents N, chores ℳM, positive weights (wi)i∈(w_i)_i with ∑i∈wi=1 _i w_i=1, additive costs (vi)i∈(v_i)_i 2: An allocation A=(Ai)i∈A=(A_i)_i satisfying vi(Ai)≤4.12424⋅WMMSiv_i(A_i)≤ 4.12424·WMMS_i for all i 3: Set δ←10−6δ← 10^-6, ρ←689/625ρ← 689/625, and β←604367/200000β← 604367/200000. 4: if vi(ℳ)=0v_i(M)=0 for some agent i then 5: Assign all chores to agent i. 6: return the resulting allocation. 7: Phase I: Approximate the WMMS benchmarks 8: for each agent i∈i do 9: Apply the (1+δ)(1+δ)-PTAS for makespan minimization on uniformly related machines, using job sizes vihv_ih and machine speeds wjw_j. 10: Let T^i T_i be the makespan of the returned schedule. 11: Set μ^i←wiT^i μ_i← w_i T_i. ⊳ μi≤μ^i≤(1+δ)μi _i≤ μ_i≤(1+δ) _i 12: Phase I: Normalize costs and select eligible edges 13: for each agent i∈i and chore h∈ℳh do 14: Set cih←wivihμ^ic_ih← w_iv_ih μ_i. 15: Define Eρ←(i,h)∈×ℳ:cih≤ρwi.E_ρ←\(i,h) ×M:c_ih≤ρ w_i\. 16: Phase I: Compute a fractional assignment 17: Find a feasible solution (xih)(i,h)∈Eρ(x_ih)_(i,h)∈ E_ρ to the following linear program: ∑i:(i,h)∈Eρxih=1,∀h∈ℳ,∑h:(i,h)∈Eρcihxih≤βwi,∀i∈,xih≥0,∀(i,h)∈Eρ. array[]l _i:(i,h)∈ E_ρx_ih=1,&∀ h ,\\[5.69054pt] _h:(i,h)∈ E_ρc_ihx_ih≤β w_i,&∀ i ,\\[5.69054pt] x_ih≥ 0,&∀(i,h)∈ E_ρ. array 18: 19: Phase IV: Round the fractional assignment 20: for each agent i∈i do 21: Sort chores with xih>0x_ih>0 in nonincreasing order of cihc_ih. 22: Let qi←⌈∑h∈ℳxih⌉q_i← _h x_ih . 23: Create qiq_i slots of unit capacity. 24: Place fractional chore masses xihx_ih consecutively into these slots, following the sorted order. 25: Construct a bipartite graph ℋH between chores and slots, connecting a chore to each slot containing a positive fraction of it. 26: Find a matching in ℋH covering every chore. 27: for each chore h∈ℳh do 28: Assign h to the agent owning its matched slot. 29: return the resulting integral allocation A=(Ai)i∈A=(A_i)_i . 4.1 Establishing the existence of the α-WMMS allocation 4.1.1 The dual-price formulation Let cic_i be the normalized cost function of agent i defined as in Lemma 3.3. An edge (i,h)(i,h) is called eligible if ci(h)≤ρwic_i(h)≤ρ w_i. Fix (ρ,r)∈Ω(ρ,r)∈ , and let Eρ=(i,h)∈×ℳ:cih≤ρwi,E_ρ=\(i,h) ×M:c_ih≤ρ w_i\, and consider the following restricted assignment LP (depending on a given value β>0β>0), which assigns a (fractional) variable to each eligible pair in EρE_ρ. ∑i:(i,h)∈Eρxih=1,∀h∈ℳ,∑h:(i,h)∈Eρcihxih≤βwi,∀i∈,xih≥0,∀(i,h)∈Eρ. array[]l _i:(i,h)∈ E_ρx_ih=1,&∀ h ,\\[5.69054pt] _h:(i,h)∈ E_ρc_ihx_ih≤β w_i,&∀ i ,\\[5.69054pt] x_ih≥ 0,&∀(i,h)∈ E_ρ. array It is observed that there is at least one eligible recipient for every chore. To see this, choose an agent a of maximum weight, so wa=w∗w_a=w_*. By Equation 2, every chore belongs to some bundle in row a’s witnessing partition and therefore cah≤wj≤w∗=wa<ρwa.c_ah≤ w_j≤ w_*=w_a<ρ w_a. Consequently (a,h)∈Eρ(a,h)∈ E_ρ for every h. This elementary observation ensures that the covering constraints themselves are not infeasible merely because some chore has no eligible recipient. We first show the feasibility of LP. Rather than explicitly constructing a feasible fractional assignment =(xih)x=(x_ih), we establish its existence through linear programming duality. Specifically, by Farkas’ lemma, the fractional assignment LP is feasible if and only if no dual certificate of infeasibility exists. Consequently, it suffices to show that every admissible dual solution satisfies some inequality, as formalized in the following lemma. Lemma 4.3 (Dual feasibility criterion). For a given β≥0β≥ 0, the LP is feasible if and only if every choice λi≥0 _i≥ 0 and ph≥0p_h≥ 0 satisfying ph≤λicih,for (i,h)∈Eρ,p_h≤ _ic_ih, (i,h)∈ E_ρ, (4) obeys P≤βW,whereP=∑hph,W=∑iλiwi.P≤β W, P= _hp_h, W= _i _iw_i. (5) Proof. Necessity. Suppose LP has a feasible solution x. Multiply ph≤λicihp_h≤ _ic_ih by xih≥0x_ih≥ 0, and sum over eligible edges: ∑hph=∑hph∑i:(i,h)∈Eρxih≤∑iλi∑h:(i,h)∈Eρcihxih≤∑iλiβwi=βW. _hp_h= _hp_h _i:(i,h)∈ E_ρx_ih≤ _i _i _h:(i,h)∈ E_ρc_ihx_ih≤ _i _iβ w_i=β W. The first equality uses coverage, while the last inequality uses the load constraints and the nonnegativity of the multipliers. Sufficiency. Consider the following always-feasible auxiliary linear program, with a nonnegative load parameter z: minimizezsubject to∑i:(i,h)∈Eρxih=1(h∈ℳ),∑hcihxih≤zwi(i∈),≥0,z≥0. array[]lminimize&z\\ subject to& _i:(i,h)∈ E_ρx_ih=1 (h ),\\ & _hc_ihx_ih≤ zw_i (i ),\\ &x≥ 0, z≥ 0. array It is feasible because each chore has an eligible edge, and sufficiently large z covers the resulting finite loads. Its optimum z∗z^* is finite. The dual can be written as maximize∑hphsubject toph≤λicih,(i,h)∈Eρ,∑iλiwi≤1,λi≥0, array[]lmaximize& _hp_h\\ subject to&p_h≤ _ic_ih, ~~(i,h)∈ E_ρ,\\ & _i _iw_i≤ 1, _i≥ 0, array where initially the equality-constraint multipliers php_h are unrestricted in sign. Because all costs and λi _i are nonnegative, replacing a negative php_h by zero preserves the dual constraints and cannot decrease its objective. We may therefore restrict attention to ph≥0p_h≥ 0. If every feasible price/multiplier pair satisfies P≤βWP≤β W, every dual solution with W≤1W≤ 1 has P≤βP≤β. Linear-programming strong duality implies z∗≤βz^*≤β. An optimal solution at z∗z^* is then feasible to LP with the prescribed budget β. The argument also covers the degenerate cases P=W=0P=W=0 and zero multipliers.∎ Fix an arbitrary feasible dual pair (λ=(λi)i,p=(ph)h)(λ=( _i)_i,p=(p_h)_h) satisfying (4). By Lemma 4.3, to establish the feasibility of the fractional assignment LP, we aim to derive an upper bound on the total dual price P=∑hphP= _hp_h in terms of the weighted sum W=∑iλiwiW= _i _iw_i of the dual multipliers. Rather than analyzing the individual prices directly, we examine their distribution above different thresholds. The motivation is that chores with sufficiently large prices, after appropriate capping, can only be accommodated by bins with sufficiently large capacities in the WMMS witnessing partitions. By expressing the total capped prices through upper-tail functions (Lemma 4.5), we can translate these packing restrictions into inequalities involving the dual variables (Lemma 4.7). These inequalities will subsequently be integrated over a continuum of scales to establish the desired bound P≤βWP≤β W (Theorem 4.8), thereby proving the feasibility of the fractional assignment LP. 4.1.2 Represent the dual prices by their upper tails Definition 4.4 (Upper-tail functions). For z≥0z≥ 0, define D(z)=|h:ph>z|D(z)=|\h:p_h>z\|, and E(z)=∑h(ph−z)+E(z)= _h(p_h-z)^+, where x+=maxx,0x^+= \x,0\, respectively the number of chores whose prices exceed the threshold z and the total excess of these prices above z. In particular, E(0)=P,E(z)=0if z≥pmax:=maxh∈ℳph.E(0)=P, E(z)=0 z≥ p_ := _h p_h. (6) Lemma 4.5 (Upper-tail identities). For all x,y≥0x,y≥ 0, with oriented integration if x>yx>y, E(x)−E(y)=∫xyD(z)z.E(x)-E(y)= _x^yD(z)\,dz. (7) In particular, E(z)=∫z∞D(u)uE(z)= _z^∞D(u)\,du. For 0≤b<c0≤ b<c one also has ∑h:ph>bminph,c=E(b)−E(c)+bD(b). _h:p_h>b \p_h,c\=E(b)-E(c)+bD(b). (8) Proof. For a fixed chore h, the indicator ph>z1_\p_h>z\ is equal to 11 on [0,ph)[0,p_h) and 00 beyond php_h. Hence ∫xyph>zdz=(ph−x)+−(ph−y)+. _x^y1_\p_h>z\\,dz=(p_h-x)_+-(p_h-y)_+. Summing over the finitely many chores proves (7). The representation E(z)=∫z∞D(u)uE(z)= _z^∞D(u)\,du follows by taking y≥pmaxy≥ p_ . To prove (8), consider a chore with ph>bp_h>b. If ph≤cp_h≤ c, then (ph−b)+−(ph−c)++b=(ph−b)+b=ph.(p_h-b)_+-(p_h-c)_++b=(p_h-b)+b=p_h. If ph>cp_h>c, then the same expression equals (ph−b)−(ph−c)+b=c(p_h-b)-(p_h-c)+b=c. Thus in either case minph,c=(ph−b)+−(ph−c)++b. \p_h,c\=(p_h-b)_+-(p_h-c)_++b. For ph≤bp_h≤ b both the first two positive-part terms vanish, so summing the displayed equality only over ph>bp_h>b yields E(b)−E(c)+bD(b)E(b)-E(c)+bD(b). ∎ 4.1.3 Threshold profiles of dual multipliers and weights For t>0t>0, define ω(t)=maxwi:λi≤t,R(t)=∑i:λi>twi,ω(t)= \w_i: _i≤ t\, R(t)= _i: _i>tw_i, (9) where the maximum of an empty set is defined to be zero. In other words, ω(t)ω(t) denotes the largest weight among agents whose dual multipliers are at most t, while R(t)R(t) represents the total weight of agents whose dual multipliers exceed t. Clearly, ω(t)ω(t) is nondecreasing and R(t)R(t) is nonincreasing in t. Moreover, these functions satisfy ∑i:wi>ω(t)wi≤R(t)and∫0∞R(t)dt=∑iλiwi=W. _i:w_i>ω(t)w_i≤ R(t) _0^∞R(t)\,\,dt= _i _iw_i=W. (10) Indeed, wj>ω(t)w_j>ω(t) implies λj>t _j>t; the integral identity follows by integrating the indicators t<λi1_\t< _i\. Lemma 4.6 (Capped prices admit integral packings). For any u>0u>0 such that ω(u)>0ω(u)>0, the capped sizes of the indivisible chores zh(u)=minph,ρuω(u)z_h(u)= \p_h,ρ uω(u)\ can be packed into bins of capacities uw1,…,uwnuw_1,…,uw_n. Proof. Choose agent a with wa=ω(u)w_a=ω(u) and λa≤u _a≤ u. If (a,h)(a,h) is eligible, then ph≤λacah≤ucahp_h≤ _ac_ah≤ uc_ah. Otherwise, ucah>ρuwauc_ah>ρ uw_a. Thus zh(u)≤ucahz_h(u)≤ uc_ah for all chores, including those not eligible for agent a. Take a complete integral partition witnessing Equation 2 for row-a partition. In its jjth bundle, ∑h∈Bjazh(u)≤u∑h∈Bjacah≤uwj. _h∈ B_j^az_h(u)≤ u _h∈ B_j^ac_ah≤ uw_j. The same partition therefore packs all capped prices integrally. ∎ 4.1.4 Turn the packing into a pointwise price inequality For every scale q>0q>0, denote Fq(t)=E(qtω(t)),Nq(t)=qtω(t)D(qtω(t)),J(q)=∫0∞Nq(t)dt.F_q(t)=E(qtω(t)), N_q(t)=qtω(t)D(qtω(t)), J(q)= _0^∞N_q(t) \,dtt. (11) Note that J(q)J(q) is finite and nonnegative. It aggregates the threshold contributions of expensive chores over all dual-multiplier thresholds t>0t>0, for a fixed scale q. In addition, near zero, Nq(t)≤qmw∗tN_q(t)≤ qmw_*t, and for sufficiently large t, ω(t)=w∗ω(t)=w_* and Nq(t)=0N_q(t)=0. The estimates are uniform on compact positive scale intervals. Also, Fq(t)→PF_q(t)→ P as t↓0t 0, and Fq(t)=0F_q(t)=0 eventually. Thus compact scale integrations below are justified by nonnegativity or absolute integrability. Lemma 4.7 (All-scale inequality). For every s≥1s≥ 1, Plns+J(s)−∫ρsJ(q)qq≤sW.P s+J(s)- _ρ^s J(q)q\,dq≤ sW. (12) The integral has its usual orientation when s<ρs<ρ. Proof. We first show the pointwise inequality Fs(t)−Fρ(st)+Ns(t)≤stR(t).F_s(t)-F_ρ(st)+N_s(t)≤ stR(t). (13) Put u=stu=st. If ω(u)=0ω(u)=0, both relevant profiles are zero and the left side is zero. Otherwise use Lemma 4.6 at u. Every item with ph>uω(t)p_h>uω(t) has capped size strictly greater than uω(t)uω(t), because ρuω(u)>uω(t).ρ uω(u)>uω(t). Here ω(u)≥ω(t)ω(u)≥ω(t), s≥1s≥ 1, and ρ>1ρ>1. Therefore these items occupy only bins with wj>ω(t)w_j>ω(t). Their total available capacity is at most uR(t)uR(t) by Equation 10. The sum of their capped sizes equals ∑h:ph>uω(t)minph,ρuω(u) _h:p_h>uω(t) \p_h,ρ uω(u)\ =E(uω(t))−E(ρuω(u))+uω(t)D(uω(t)) =E(uω(t))-E(ρ uω(u))+uω(t)D(uω(t)) =Fs(t)−Fρ(st)+Ns(t). =F_s(t)-F_ρ(st)+N_s(t). This also handles ω(t)=0<ω(u)ω(t)=0<ω(u): every selected positive item uses a positive-capacity bin. Integrate Equation 13 against dt/t\,dt/t. Logarithmic telescoping gives ∫0∞(Fρ(t)−Fρ(st))dt=Plns. _0^∞ (F_ρ(t)-F_ρ(st) ) \,dtt=P s. (14) For s>1s>1, integration from ε to T and substitution in the second term give the integral of Fρ(t)/tF_ρ(t)/t over [ε,sε][ ,s ] minus its integral over [T,sT][T,sT]. The endpoint values give the identity. The case s=1s=1 is immediate. Furthermore, E(x)−E(y)=∫xyD(z)zE(x)-E(y)= _x^yD(z)\,dz implies ∫0∞(Fs(t)−Fρ(t))dt=−∫ρsJ(q)qdq. _0^∞ (F_s(t)-F_ρ(t) ) \,dtt=- _ρ^s J(q)q\,dq. (15) Use z=qtω(t)z=qtω(t) and interchange the compact scale integral with the t-integral. Combining Equations 14 and 15, the definition of J(s)J(s), and Equation 10 proves Equation 12. ∎ 4.1.5 Cancellation of the correction terms Theorem 4.8 (Multiscale fractional bound). The assignment system LP is feasible with β=β(ρ,r)=1+ln(r/ρ)(1+lnρ)/ρ−1/r.β=β(ρ,r)= 1+ (r/ρ)(1+ ρ)/ρ-1/r. (16) Proof. Let Q(s)=∫ρsJ(q)qq.Q(s)= _ρ^s J(q)q\,dq. Then Q(ρ)=0Q(ρ)=0 and Q′(s)=J(s)/sQ (s)=J(s)/s almost everywhere. Divide Equation 12 by s2s^2, integrate from ρ to r, and add Equation 12 at s=rs=r, divided by r. The correction integral is ∫ρrJ(s)−Q(s)s2s=∫ρr(Q(s)s)′s=Q(r)r. _ρ^r J(s)-Q(s)s^2\,ds= _ρ^r ( Q(s)s ) \,ds= Q(r)r. Adding the endpoint cancels Q(r)Q(r) and leaves J(r)/rJ(r)/r. Also, ∫ρrlns2s+lnr=1+lnρ−1r,∫ρrds+1=1+ln(r/ρ). _ρ^r ss^2\,ds+ rr= 1+ ρ- 1r, _ρ^r \,dss+1=1+ (r/ρ). Consequently, P(1+lnρ−1r)+J(r)r≤W(1+lnrρ).P ( 1+ ρ- 1r )+ J(r)r≤ W (1+ rρ ). (17) The coefficient of P is positive because r>ρ>1r>ρ>1. Discard the nonnegative endpoint term and apply Lemma 4.3 with α=α(ρ,r)α=α(ρ,r) given by Equation 16. Hence, the assignment system LP is feasible and the proof is completed. ∎ 4.2 Computing an (α+ϵ)(α+ε)-WMMS allocation We make use of the standard matching argument, which is included here to make the additive error precise. Lemma 4.9 (Additive assignment rounding [23]). Suppose a fractional assignment x covers each chore exactly once, the fractional cost of agent i is at most LiL_i, and every edge with xih>0x_ih>0 has cost at most bib_i. One can compute in polynomial time an integral assignment using only supported edges with the (integral) cost of agent i is at most Li+biL_i+b_i, simultaneously for all agents. Proof. Fix an agent i. List the chores with xih>0x_ih>0 in nonincreasing order of cost ci(h)c_i(h). Regard xihx_ih as an item mass, and lay these masses consecutively into slots of mass at most one. If a mass crosses a slot boundary, split that fractional mass between the adjacent slots. Every slot is full, except possibly the last. Denote the slots of agent i by (i,1),…,(i,qi)(i,1),…,(i,q_i); an agent with no positive fractional mass has no slots. Construct a bipartite graph ℋH with chores on the left and all the slots on the right. Join chore h to slot (i,k)(i,k) precisely when a positive portion of its fractional mass was placed there. Each chore has total fractional mass one over its incident slots, and each slot has total incident fractional mass at most one. This is a fractional matching saturating every chore. The integrality of bipartite matching (equivalently, a max-flow integrality theorem) therefore gives an integral matching saturating every chore. Assign a chore to the owner of its matched slot. Every chore is assigned once, and only supported assignment edges are used. It remains to bound the load of one agent. The cost of the item matched to her first slot, if any, is at most bib_i. Suppose a chore h is matched to slot (i,k)(i,k) with k≥2k≥ 2. Because the fractional pieces were ordered by decreasing cost, every positive fractional piece in the preceding slot (i,k−1)(i,k-1) has cost at least cihc_ih. That preceding slot is full, of total mass one. Its fractional cost is therefore at least cihc_ih. Different matched slots k≥2k≥ 2 charge to different preceding slots k−1k-1, and none of these charges exceeds the corresponding preceding slot’s fractional cost. Summing their charges is at most the total original fractional load of agent i, hence at most LiL_i. Adding the possible first-slot item gives integral load at most Li+biL_i+b_i. The argument holds simultaneously for every agent because the one matching assigns all items consistently. Finally, the slot graph has polynomial size, and bipartite matching is polynomial time. This completes the proof. ∎ Apply Lemma 4.9 with Li=α(ρ,r)wiL_i=α(ρ,r)w_i and bi=ρwib_i=ρ w_i. Then ci(Ai)≤(β(ρ,r)+ρ)wi=α(ρ,r)wi.c_i(A_i)≤ (β(ρ,r)+ρ )w_i=α(ρ,r)w_i. Lemma 3.3 proves the existential part of Theorem 4.2. The main upper-bound theorem thus holds directly on the original matrix: no identical-ordering reduction or weight discretization is needed. For rational original input, use the related-machine scheduling scheme [17] separately for each row. Job h has size vi(h)v_i(h) and machine j has speed wjw_j. If the returned feasible makespan is τ^i τ_i, then μ^i=wiτ^i μ_i=w_i τ_i satisfies μi≤μ^i≤(1+δ)μi _i≤ μ_i≤(1+δ) _i (18) for any fixed δ>0δ>0. Normalize instead by c^i(h)=wivi(h)/μ^i c_i(h)=w_iv_i(h)/ μ_i. The returned schedules themselves witness Equation 2. Consequently, Theorem 4.8 applies without knowing exact WMMS. Choose rational ρ,rρ,r and a rational β^>β(ρ,r) β>β(ρ,r). Solve LP for c c with budget β^wi βw_i, then round. The original cost is at most (β^+ρ)μ^i≤(β^+ρ)(1+δ)μi.( β+ρ) μ_i≤( β+ρ)(1+δ) _i. (19) There are at most nmnm assignment variables and n+mn+m main constraints. The WMMS approximation is polynomial time for fixed precision; solving the rational LP and finding the matching are polynomial-time operations. Nearby rational parameters and sufficiently small fixed errors prove the (α⋆+ε)( _ + ) assertion. For an explicit guarantee, take ρ=689625,r=151095000,β^=604367200000,δ=10−6.ρ= 689625, r= 151095000, β= 604367200000, δ=10^-6. (20) Exact logarithm enclosures establish α(ρ,r)<α^α(ρ,r)< α. Moreover, (β^+ρ)(1+δ)=824847824847200000000000=4.124239124235<4.12424.( β+ρ)(1+δ)= 824847824847200000000000=4.124239124235<4.12424. (21) This finishes the algorithmic part of Theorem 4.2. 5 An existential lower bound of e For a problem instance I with positive weighted maximin shares, define γ(I)=min(A1,…,An)maxi∈vi(Ai)μi,Γ=supIγ(I).γ(I)= _(A_1,…,A_n) _i v_i(A_i) _i, = _Iγ(I). Basically, Γ is the optimal universal existence factor, rather than an approximation ratio relative to the best allocation of a fixed instance. Our main result is as follows. Theorem 5.1 (Existential lower bound). For any fixed ϵ∈(0,e−1)ε∈(0,e-1), there is an instance which does not admit an (e−ϵ)(e-ε)-WMMS allocation, where e≈2,71828e≈ 2,71828. To get the result, we show a construction of an explicit instance as in the theorem below. Theorem 5.2. For every integer t≥4t≥ 4 and K≥t+1K≥ t+1, there is an explicit instance It,KI_t,K with 2K−12^K-1 agents and 2K−12^K-1 chores such that (1+1t)t−3K+t−1≤γ(It,K)≤(1+1t)t−1. (1+ 1t )^t-3 KK+t-1\ ≤\ γ(I_t,K)\ ≤\ (1+ 1t )^t-1. (22) All costs are strictly positive, additive, and identically ordered. By taking K=t2K=t^2, both endpoints of Equation 22 converge to e: (1+1t)t−3t2t2+t−1⟶e,(1+1t)t−1⟶e. (1+ 1t )^t-3 t^2t^2+t-1 e, (1+ 1t )^t-1 e. Hence, for every 0<ε<e−10< <e-1, a sufficiently large finite t therefore gives an instance admitting no (e−ε)(e- )-WMMS allocation. This gives Theorem 5.1. It therefore suffices to prove Theorem Theorem 5.2. An overview of the instance construction. To establish our lower bound, we construct a family of weighted chore-allocation instances with a layered structure, consisting of K groups of agents and K corresponding blocks of chores, where both the number of agents and the number of chores in layer i equal 2i−12^i-1. The agents are assigned carefully chosen geometrically structured weights, while their additive cost functions follow a nested pattern in which all agents agree on the ordering of chores and every chore has strictly positive cost. The key feature of the construction is that each agent’s weighted maximin share can be bounded from above by explicitly constructing an integral packing of the chores into bins whose capacities correspond to the agents’ weights. These benchmark bounds force agents, under a sufficiently small approximation factor, to receive chores only from certain later layers, allowing us to derive a contradiction by comparing the total cost of any allocation with the sum of the permitted WMMS budgets. By appropriately choosing the parameters and letting the number of layers grow, we show that the resulting lower bound converges to e, thereby proving that no universal WMMS approximation factor smaller than e is possible. 5.1 Agent groups, weights, and additive costs Fix integers t≥4t≥ 4 and K≥t+1K≥ t+1. Let g=1+1/t,q=gt−3,χ=gt−1.g=1+1/t, q=g^t-3, χ=g^t-1. (23) We construct an instance It,KI_t,K with 2K−12^K-1 agents and an equal number of chores such that qK+t−1≤γ(It,K)≤χ.q KK+t-1≤γ(I_t,K)≤χ. Agents and Weights There are K groups G1,…,GKG_1,…,G_K, with ni=2i−1n_i=2^i-1 agents each (i∈1,…,Ki∈\1,…,K\). We refer to G1G_1, which consists of a single agent, as the root group, and its unique agent as the root agent. The remaining groups G2,…,GKG_2,…,G_K are called nonroot groups, and their members are referred to as nonroot agents. This terminology distinguishes the first group from the others, as we will see later on, the root agent will value every chore at its assigned price, whereas a nonroot agent may value chores from her own or earlier blocks differently. Every agent in GiG_i has the same unnormalized individual weight w1=t,wi=gi−2ni,(i≥2).w_1=t, w_i= g^i-2n_i, (i≥ 2). (24) Let Wi=niwiW_i=n_iw_i. Then W1=t,Wi=gi−2(i≥2),Rj−1:=∑a<jWa=tgj−2,∑a<jna=nj−1.W_1=t, W_i=g^i-2\ (i≥ 2), R_j-1:= _a<jW_a=tg^j-2, _a<jn_a=n_j-1. (25) The last two identities hold for j≥2j≥ 2. Individual weights decrease strictly: w2=1/2<tw_2=1/2<t and wi+1/wi=g/2<1w_i+1/w_i=g/2<1. Total weight is tgK−1tg^K-1; a common normalization does not change WMMS. Chores and Costs Partition the chores into blocks M1,…,MKM_1,…,M_K, with |Mj|=nj|M_j|=n_j. For an item h∈Mjh∈ M_j, every agent in group GiG_i has cost vi(h)=1maxni,nj=1/ni,j≤i,1/nj,j>i.v_i(h)= 1 \n_i,n_j\= cases1/n_i,&j≤ i,\\ 1/n_j,&j>i. cases (26) The costs are additive, strictly positive, and nonincreasing in the same block order. Recipient group M1M_1 M2M_2 M3M_3 M4M_4 G1G_1 11 1/21/2 1/41/4 1/81/8 G2G_2 1/21/2 1/21/2 1/41/4 1/81/8 G3G_3 1/41/4 1/41/4 1/41/4 1/81/8 G4G_4 1/81/8 1/81/8 1/81/8 1/81/8 Table 2: Per-item costs in the first four blocks of the lower-bound family. Block MjM_j contains 2j−12^j-1 items. The plateau in row i covers its own and all earlier blocks. 5.2 Upper bounds on WMMS To derive a lower bound on the approximation factor, we need upper bounds on the WMMS benchmarks: the smaller the benchmarks, the less cost any successful allocation is allowed to give to an agent. Before doing that, we need to present two elementary packing lemmas. Lemma 5.3 (Geometric capacity inequality). For every integer ℓ≥0 ≥ 0, tgℓ≥q(ℓ+3).tg ≥ q( +3). (27) In particular, q≤t/3q≤ t/3. Proof. Set fℓ=tgℓ/(ℓ+3)f_ =tg /( +3). Then fℓ+1fℓ=(t+1)(ℓ+3)t(ℓ+4). f_ +1f_ = (t+1)( +3)t( +4). The numerator minus the denominator is ℓ+3−t +3-t. The sequence decreases up to index t−3t-3, has equal values at t−3t-3 and t−2t-2, and then increases. Its minimum is ft−3=gt−3=qf_t-3=g^t-3=q. The last assertion is the case ℓ=0 =0. ∎ If a collection of chores has total cost below the sum of bin capacities, integral packing need not follow: each bin might have unused space too small for the next whole chore. The following standard reserve compensates for this loss. Lemma 5.4 (Integral packing of one equal-sized batch). Suppose b bins have total capacity C and already assigned load L, with no bin overloaded. A batch of m items, each of size η>0η>0, can be packed integrally into these bins whenever C≥L+mη+bη.C≥ L+mη+bη. (28) Proof. Place each new item in any bin with residual capacity at least η. If placement fails after s<ms<m items, every bin has residual capacity less than η, hence their total residual capacity is less than bηbη. But Equation 28 gives residual capacity at least (m−s+b)η>bη(m-s+b)η>bη, a contradiction. ∎ We are now ready to prove upper bounds on WMMS of agents. Lemma 5.5 (WMMS bounds). Consider the constructed instance It,KI_t,K. Denote by μi _i the WMMS of agents in group GiG_i. It holds that μ1≤tq,andμi≤1qni(2≤i≤K). _1≤ tq, _i≤ 1qn_i (2≤ i≤ K). (29) Proof. We construct separate whole-item packings for each valuation row into the actual agent bins, whose capacities are the weights in Equation 24. Fix group i≥2i≥ 2 and scale its costs by ai=qWia_i=qW_i. All 2ni−12n_i-1 items in the first i blocks have scaled size ai/nia_i/n_i. Pack this initial batch using only groups strictly before i. Then process successive blocks MjM_j using only groups strictly before j, while j<i+t−3j<i+t-3 and j≤Kj≤ K. At stage j=i+ℓj=i+ , the cumulative scaled load is Cj=ai(ℓ+2−1ni).C_j=a_i ( +2- 1n_i ). There are nj−1n_j-1 available bins, and the current item size is ai/nja_i/n_j; for j=ij=i, the current batch is the entire initial prefix. By Equations 25 and 27, Rj−1=tWigℓ≥ai(ℓ+3)>ai(ℓ+2−1ni)+(nj−1)ainj=Cj+(nj−1)ainj. R_j-1=tW_ig ≥ a_i( +3)>a_i ( +2- 1n_i )+(n_j-1) a_in_j=C_j+(n_j-1) a_in_j. All earlier assignments lie in the currently available bins. Lemma 5.4 therefore completes each stage integrally, by induction. For every remaining block j≥i+t−3j≥ i+t-3, we have Wj=Wigj−i≥qWi=aiW_j=W_ig^j-i≥ qW_i=a_i. Give one item of MjM_j to each of the njn_j bins in GjG_j; it has scaled size ai/nj≤wja_i/n_j≤ w_j. Those bins are fresh, since earlier stages used only groups preceding their current block. If the cutoff exceeds K, the greedy stages already complete the whole instance. Thus aivia_iv_i packs inside the weights, and μi≤wiai=1qni. _i≤ w_ia_i= 1qn_i. For the root group 11, scale its cost by q. Put the first item, of scaled size q≤t/3q≤ t/3, in the sole root bin of capacity t. Process blocks MjM_j for 2≤j≤t−22≤ j≤ t-2 using groups strictly before j. At stage j, cumulative scaled load is qjqj, item size is q/njq/n_j, and there are nj−1n_j-1 available bins. By Equation 27 with ℓ=j−2 =j-2, Rj−1=tgj−2≥q(j+1)>qj+(nj−1)q/nj.R_j-1=tg^j-2≥ q(j+1)>qj+(n_j-1)q/n_j. Apply Lemma 5.4. For j≥t−1j≥ t-1, Wj=gj−2≥qW_j=g^j-2≥ q, so block MjM_j fits one item per bin in its own fresh group. This packs qv1qv_1 within the weights and gives μ1≤t/q _1≤ t/q. ∎ 5.3 Proof of Theorem 5.2 We establish both lower and upper bounds on the optimal WMMS approximation factor γ(It,K)γ(I_t,K) for the instance It,KI_t,K. Lower bound Give each item of block MjM_j price ph=1/njp_h=1/n_j. Total price is K. Consider an arbitrary allocation and let α be its maximum WMMS ratio. If α≥qα≥ q, the desired lower bound is immediate. Suppose α<qα<q. For every nonroot group i≥2i≥ 2, an item from its own or an earlier block costs 1/ni1/n_i, whereas αμi≤αqni<1ni.α _i≤ αqn_i< 1n_i. Such an assignment is impossible. Hence every item received by a nonroot agent comes from a later block and has recipient cost equal to its price. The root also values every item at its price. Therefore the allocation’s total recipient cost is exactly K. By Lemma 5.5, K≤α∑i=1Kniμi≤αq(t+K−1).K≤α _i=1^Kn_i _i≤ αq(t+K-1). It follows that γ(It,K)≥qK+t−1.γ(I_t,K)≥ q KK+t-1. (30) The derivation does not restrict how individual chores are distributed within or across blocks. Every forbidden edge was ruled out using the actual WMMS requirement. Upper bound We first derive lower bounds on the WMMS of the agents who receive chores in the allocation constructed to prove the lower bound on γ(It,K)γ(I_t,K). Lemma 5.6. For χ=gt−1χ=g^t-1, μ1≥t/χ,μi≥1/(χni)(2≤i≤K−t+1). _1≥ t/χ, _i≥ 1/(χ n_i) (2≤ i≤ K-t+1). Proof. For root group, suppose its makespan τ<1/χτ<1/χ and consider the first j=t+1j=t+1 blocks. Every one of these items costs at least 1/nj1/n_j. Every bin in group j or later has capacity at most τwj=τχ/nj<1/njτ w_j=τχ/n_j<1/n_j, since individual weights decrease. Thus all selected items must use earlier bins, of total capacity τRj−1=τtχ<tτ R_j-1=τ tχ<t. Their total cost is t+1t+1, a contradiction. Hence μ1=tτ≥t/χ _1=tτ≥ t/χ. For nonroot group i≥2i≥ 2, put j=i+t−1≤Kj=i+t-1≤ K. If τ<1/(χWi)τ<1/(χ W_i), no item in the first j blocks fits in group j or later, because each costs at least 1/nj1/n_j while τwj=τχWi/nj<1/njτ w_j=τχ W_i/n_j<1/n_j. Earlier capacity is τRj−1=τtχWi<tτ R_j-1=τ tχ W_i<t. But the selected row-i cost is 2−1/ni+j−i=t+1−1/ni>t2-1/n_i+j-i=t+1-1/n_i>t. Thus τ≥1/(χWi)τ≥ 1/(χ W_i), and μi=wiτ≥1/(χni) _i=w_iτ≥ 1/(χ n_i). ∎ Give the first t blocks to the root. Its load is t≤χμ1t≤χ _1. For each 2≤i≤K−t+12≤ i≤ K-t+1, give block Mi+t−1M_i+t-1 to group GiG_i, with exactly 2t−12^t-1 items per agent. This is integral because ni+t−1=2t−1nin_i+t-1=2^t-1n_i. Each recipient’s cost is 1/ni≤χμi1/n_i≤χ _i. The last t−1t-1 groups receive nothing. All chores are allocated, proving γ(It,K)≤χ=gt−1.γ(I_t,K)≤χ=g^t-1. Together with Equation 30, this proves Equation 22 and thus Theorem 5.2. 6 Conclusion We studied the allocation of indivisible chores among agents with arbitrary positive weights and additive nonnegative costs, with the goal of guaranteeing each agent a bounded multiple of her weighted maximin share. We showed that every instance admits an α⋆ _ -WMMS allocation with α⋆<4.124234528 _ <4.124234528, and that a 4.124244.12424-WMMS allocation can be computed in polynomial time for rational inputs. The upper bound requires neither rounding of weights or costs nor a common ordering of the agents’ cost functions; it relies only on the existence of a row-wise integral packing for each agent. On the lower-bound side, we constructed instances with strictly positive, identically ordered costs whose optimal WMMS factors converge to e. Together, these results narrow the previously best-known gap of [2,12][2,12] to [e, 4.124234528][e,\,4.124234528]. Closing the remaining gap is the main open problem, and our analysis indicates where progress might come from. On the upper-bound side, the guarantee α(ρ,r)=ρ+β(ρ,r)α(ρ,r)=ρ+β(ρ,r) consists of two separate losses: the fractional bound β(ρ,r)≈3.0218β(ρ,r)≈ 3.0218 obtained from the multiscale dual-price inequalities, and an additive loss of ρ≈1.1024ρ≈ 1.1024 incurred by rounding, which charges one eligible chore per agent. The two parts are optimized jointly through the eligibility threshold ρ, but they are analyzed independently. An improvement could come from stronger packing inequalities than the capped-price inequalities of Lemma 4.6, from a rounding procedure that exploits the structure of the WMMS packings rather than only the fractional loads and the largest supported costs, or from treating large and small chores jointly. We leave open whether either loss is unavoidable for approaches of this type. On the lower-bound side, our obstruction combines two ingredients: individually infeasible agent–chore pairs and a linear comparison between the total price of the chores and the sum of the permitted budgets. As shown in Section 5, the constructed family itself admits allocations whose factors converge to e, so this construction cannot yield a stronger bound. Improving on e will therefore require instances with a different structure, and possibly an argument that captures integrality obstructions beyond price-versus-budget counting. It also remains open whether the identically ordered case, to which our lower-bound instances belong, is as hard as the general case. Use of generative AI. The authors used GenAI iteratively to refine and improve an initial draft of this paper. The authors have verified all proofs and accept full responsibility for the accuracy and correctness of the results presented in the paper. References [1] H. Akrami, J. Garg, E. Sharma, and S. Taki (2023) Simplification and improvement of MMS approximation. In Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), Cited by: §2.1. [2] H. Akrami and J. Garg (2024) Breaking the 3/43/4 barrier for approximate maximin share. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), p. 74–91. Cited by: §2.1. [3] G. Amanatidis, H. Aziz, G. Birmpas, A. Filos-Ratsikas, B. Li, H. Moulin, A. A. Voudouris, and X. Wu (2023) Fair division of indivisible goods: recent progress and open questions. Artificial Intelligence 322, p. 103965. Cited by: §1, §2.1. [4] G. Amanatidis, E. Markakis, A. Nikzad, and A. Saberi (2017) Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms 13 (4), p. 52:1–52:28. Cited by: §2.1. [5] H. Aziz, H. Chan, and B. Li (2019) Weighted maxmin fair share allocation of indivisible chores. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), p. 46–52. External Links: Document Cited by: §1, §2.1, Table 1. [6] H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh (2017) Algorithms for max-min share fair allocation of indivisible chores. In Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), p. 335–341. Cited by: §1. [7] H. Aziz (2016) Computational social choice: some current and new directions. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), p. 4054–4057. Cited by: §1, §2.1. [8] S. Barman and S. K. Krishnamurthy (2017) Approximation algorithms for maximin fair division. In Proceedings of the 18th ACM Conference on Economics and Computation (EC), p. 647–664. Cited by: §2.1. [9] S. Bouveret, Y. Chevaleyre, and N. Maudet (2016) Fair allocation of indivisible goods. In Handbook of Computational Social Choice, F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia (Eds.), p. 284–310. Cited by: §1. [10] E. Budish (2011) The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119 (6), p. 1061–1103. Cited by: §1. [11] I. Caragiannis, D. Kurokawa, H. Moulin, A. Procaccia, N. Shah, and J. Wang (2016) The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation, p. 305–322. Cited by: §1. [12] A. Farhadi, M. Ghodsi, M. T. Hajiaghayi, S. Lahaie, D. M. Pennock, M. Seddighin, S. Seddighin, and H. Yami (2019) Fair allocation of indivisible goods to asymmetric agents. Journal of Artificial Intelligence Research 64, p. 1–20. External Links: Document Cited by: §1, §1, §2.1. [13] J. Garg and S. Taki (2021) An improved approximation algorithm for maximin shares. Artificial Intelligence. Cited by: §2.1. [14] M. Ghodsi, M. T. Hajiaghayi, M. Seddighin, S. Seddighin, and H. Yami (2018) Fair allocation of indivisible goods: improvements and generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC), Cited by: §2.1. [15] J. R. Goldman and A. D. Procaccia (2014) Spliddit: unleashing fair division algorithms. ACM SIGecom Exchanges 13 (2), p. 41–46. Cited by: §1. [16] H. Guo, W. Li, and B. Deng (2023) A survey on fair allocation of chores. Mathematics 11 (16), p. 3616. Cited by: §2.1. [17] D. S. Hochbaum and D. B. Shmoys (1988) A polynomial approximation scheme for scheduling on uniform processors: using the dual approximation approach. SIAM Journal on Computing 17 (3), p. 539–551. External Links: Document Cited by: §3, §4.2. [18] D. Kurokawa, A. D. Procaccia, and J. Wang (2018) Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM 65 (2), p. 8:1–8:27. Cited by: §2.1. [19] J. Lang and J. Rothe (2015) Fair division of indivisible goods. In Economics and Computation. An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division, J. Rothe (Ed.), Springer Texts in Business and Economics, p. 493–550. Cited by: §1. [20] B. Li, F. Wang, and S. Xing (2026) Constant weighted maximin share approximations for chores. In Proceedings of the 24th ACM Conference on Economics and Computation (EC), Note: To appear External Links: Link Cited by: §1, §2.1, Table 1, Abstract. [21] R. J. Lipton, E. Markakis, E. Mossel, and A. Saberi (2004) On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, p. 125–131. Cited by: §1. [22] M. Seddighin and S. Seddighin (2025) Fair assignment of indivisible chores to asymmetric agents. arXiv. Note: https://arxiv.org/abs/2510.10698 Cited by: §1, §2.1, Table 1. [23] D. B. Shmoys and É. Tardos (1993) An approximation algorithm for the generalized assignment problem. Mathematical Programming 62, p. 461–474. External Links: Document Cited by: Lemma 4.9. [24] H. Steinhaus (1948) The problem of fair division. Econometrica 16 (1), p. 101–104. Cited by: §1. [25] W. Suksompong (2025) Weighted fair division of indivisible items: a review. Information Processing Letters 187, p. 106519. External Links: Document Cited by: §2.1. [26] W. Suksompong (2025) Weighted fair division of indivisible items: a review. Information Processing Letters 187, p. 106519. Cited by: §1. [27] H. R. Varian (1974) Equity, envy, and efficiency. Journal of Economic Theory 9, p. 63–91. Cited by: §1. [28] F. Wang, B. Li, and P. Lu (2024) Improved approximation of weighted MMS fairness for indivisible chores. In Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence (IJCAI), p. 3014–3022. Cited by: §1, §2.1, Table 1. 7 Appendix Proof of Lemma 4.1. Set x=r/ρ>1x=r/ρ>1 and ℓ=1+lnρ =1+ ρ. Then α(ρ,ρx)=ρ(1+x(1+lnx)ℓx−1).α(ρ,ρ x)=ρ (1+ x(1+ x) x-1 ). (31) For fixed 1<ρ<e1<ρ<e, the derivative of the fractional term in x has the sign of x(1+lnρ)−2−lnx.x(1+ ρ)-2- x. It vanishes at a unique x>1x>1. At that value, x(1+lnρ)=2+lnx,β(ρ,ρx)=ρx.x(1+ ρ)=2+ x, β(ρ,ρ x)=ρ x. Express ρ=exp((2+lnx)/x−1)ρ= ((2+ x)/x-1) and minimize the remaining one-variable expression (1+x)exp(2+lnx−1).(1+x) ( 2+ xx-1 ). Its unique interior minimizer satisfies x2=(1+x)(1+lnx).x^2=(1+x)(1+ x). (32) This gives the numerical parameter values ρ∗≈1.1024340960285306,r∗≈3.0218004310998404,α∗≈4.124234527128371. _*≈ 1.1024340960285306, r_*≈ 3.0218004310998404, _*≈ 4.124234527128371. The values of ρ∗ _* and r∗r_* are not required as exact inputs in the existence proof. ∎