Paper deep dive
Maximin Share Guarantees via Limited Cost-Sensitive Sharing
Hana Salavcova, Martin Černý, Arpita Biswas
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 7/20/2026, 2:32:11 PM
Summary
This paper investigates fair allocation of indivisible goods with limited, cost-sensitive sharing. It proves that exact Maximin Share (MMS) allocations exist when goods are shared among at least half the agents (for even agent counts) and introduces the Sharing Maximin Share (SMMS) notion. The authors present a Shared Bag-Filling Algorithm for approximate MMS and establish connections between SMMS and Constrained MMS (CMMS).
Entities (6)
Relation Signals (5)
SMMS → extends → MMS
confidence 95% · natural extension of MMS to the k-sharing setting
Shared Bag-Filling Algorithm → guarantees → approximate MMS allocation
confidence 95% · guarantees a (1 - C)(k - 1)-approximate MMS allocation
k-sharing → enables → exact MMS allocation
confidence 90% · 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
k-sharing → hascost → Cost of Sharing
confidence 90% · incurring a cost for sharing
SMMS → connectedto → CMMS
confidence 85% · establish a connection between SMMS and constrained MMS (CMMS)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2602.20541v3
- Canonical: https://arxiv.org/abs/2602.20541v3
Trouble viewing inline? Open PDF directly →
Full Text
66,054 characters extracted from source content.
Expand or collapse full text
ifaamas [AAMAS ’26]Proc. of the 25th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2026)May 25 – 29, 2026 Paphos, CyprusC. Amato, L. Dennis, V. Mascardi, J. Thangarajah (eds.) 2026 2026 13 University Republic University Republic University Jersey States Maximin Share Guarantees via Limited Cost-Sensitive Sharing Hana Salavcova salavcovah@gmail.com , Martin Černý cerny@kam.mff.cuni.cz and Arpita Biswas a.biswas@rutgers.edu Abstract. 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)(1-C)(k-1)-approximate MMS allocation, where C is the maximum cost of sharing a good. Notably, when (1−C)(k−1)≥1(1-C)(k-1)≥ 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. Key words and phrases: fair allocation; maximin share; shared resources; cost of sharing; fair division doi: LGSS5881 1. Introduction The theory of fair allocation of indivisible items has been receiving significant attention, driven both by theoretical interest and by a wide range of practical applications walshfair; Aziz2022; Amanatidis2023. A substantial body of work has explored various generalizations, relaxations, and constraints that arise in real-world allocation problems. For instance, several studies have addressed settings where not all items must be allocated, leading to models where certain fairness guarantees exist, which is otherwise unattainable Caragiannis2019; Chaudhury2021b; Chaudhury2021; Berger2022. These extensions reflect a growing recognition of the need for fair allocation settings and methods that are both flexible and applicable to complex, structured domains. One of the most prominent fairness notions in the area of fair division of indivisible goods is maximin share (MMS) fairness, where each agent is guaranteed a bundle at least as much as their maximin share value. Informally, an agent’s maximin share value represents the maximum utility they can guarantee themselves by partitioning the goods into as many bundles as there are agents, under the assumption that they receive the least valuable bundle. This concept captures a natural and compelling benchmark for fairness, as it guarantees what an agent could ensure for themselves in a worst-case, divide-and-choose scenario. MMS was formally introduced in Budish2011 in the context of course allocation. Despite its intuitive appeal, MMS allocations are not guaranteed to exist in general. In fact, counterexamples with as few as three agents and a small number of goods have shown that no MMS exists Kurokawa2018; Feige2021. This inherent impossibility has led researchers to focus on approximate MMS allocations, where each agent receives at least a fraction of their MMS value. The study of such approximations has become a central direction in the literature, yielding progressively stronger guarantees over time Barman2020; Ghodsi2021; Garg2021; Feige2021 with the best known approximation factor of (34+33836) ( 34+ 33836 ) under additive valuations established by Akrami2024. Much of the prior work on fair allocation assumes that the set of items must be partitioned disjointly among the set of agents, meaning that no good can be shared among multiple agents. However, many practical scenarios, such as allocation of shared computing access jacquet2024sweetspotvm and community energy storage systems chang2022shared, may allow the sharing of resources in a structured way. For instance, consider allocating access to high-demand laboratory equipment at a university, such as a high-resolution electron microscope, a specialized DNA sequencer, and a powerful computing server. These devices are expensive, scarce, and cannot be physically subdivided, but each can be shared among a limited number of users via scheduled access time slots or usage quotas. However, sharing may come at a cost, and the effective value of a resource to each user can diminish as more users share it. A purely non-sharing allocation may leave some researchers without access to any resource, failing to meet basic fairness expectations. In contrast, allowing resources to be shared in a structured, bounded manner can help achieve fairness even when sharing incurs a cost, motivating the study of fair allocation under bounded, cost-sensitive sharing. Allowing such structured sharing can potentially lead to allocations with improved fairness guarantees.This leads to the central question: Can a fair allocation be obtained by relaxing the classical no-sharing constraint in structured ways, particularly in settings where fairness is otherwise unattainable? In this work, we allow each good to be allocated to at most k agents, while explicitly accounting for the costs incurred due to sharing. This framework significantly broadens the applicability of fair allocation, making it more aligned with real-world scenarios where limited sharing is often inevitable or desirable. A consequence of the result by Akrami2025 and Barman2025 implies that sharing among two agents is sufficient to ensure MMS fairness, assuming no cost is incurred when sharing goods. Including the cost of sharing makes the model more realistic, as sharing typically reduces the benefit that a good provides to each user. Therefore, we formalize the k-sharing fair allocation problem and introduce models to capture the cost of sharing (in Section 4). Our main theoretical contributions are as follows: (1) In Section 5, we show that exact maximin share (MMS) allocations can be achieved when goods are allowed to be cost-sensitively shared among at least half of the agents and when there is an even number of agents, under certain cost models. When agents are odd in number, we establish a slightly weaker MMS guarantee (Theorem 5). Further, for any cost-sharing model, we provide Shared Bag-Filling Algorithm for computing approximate MMS allocations in the shared setting (Theorem 5). (2) In Section 6, we introduce a stronger fairness notion for k-sharing allocations, Sharing Maximin Share (SMMS). We show that SMMS always exists when there are only two agents (Proposition 6) and under identical utilities (Proposition 6). Interestingly, the existing MMS counterexamples Kurokawa2018; Feige2021 admit feasible SMMS allocations, prompting us to construct a new counterexample to disprove universal SMMS existence (Theorem 6). (3) Additionally, we establish a connection between SMMS for shared settings and constrained MMS (CMMS), yielding approximation guarantees for SMMS (Proposition 7). 2. Related Work The literature on discrete fair allocation is extensive and rapidly evolving, typically operating under the two key assumptions: non-shareability, where an agent’s allocation is disjoint from others, and completeness, where all items must be allocated among all the agents. Recent survey articles, such as those by walshfair, Aziz2022, and Amanatidis2023, offer comprehensive insights into the algorithmic and complexity dimensions of the area of fair allocation. In addition to these broad overviews, more focused surveys have explored specific subdomains: for instance, aleksandrov2020online examined fairness in dynamic resource allocation, while Suksompong2021 and Biswas2023 investigate fairness under various structural set constraints. Despite significant advances, the well-studied maximin share (MMS) Budish2011 fairness guarantee does not hold under the standard assumptions of non-shareability and completeness kurokawa2016can; Kurokawa2018; Feige2021. Recent research has made progress on achieving various fairness guarantees by relaxing these classical assumptions through innovative approaches: (1) allowing some items to remain unallocated (as charity) Chaudhury2021; biswas2023algorithmic, (2) treating items expandable such as school seats or course seats, and allowing their capacities to be increased procaccia2024school; santhini2024approximation, (3) considering some items to be divisible Bismuth2024; Sadomirskiy2022 and (4) creating duplicate copies of items to enable multi-allocation Barman2025; Akrami2025. Barman2025 show that MMS fairness can be achieved under additive valuations by duplicating each item at most once, and Akrami et al. Akrami2025 show that MMS can be achieved with one duplicate copy of at most ⌊n/2⌋ n/2 items. While these results imply that allowing sharing among two agents helps achieving MMS fairness, the results fall short when the cost of sharing is considered. To the best of our knowledge, no prior work has considered cost-sensitive shared fair allocation setting. 3. Preliminaries An instance of a discrete fair allocation problem is typically represented by a triple I=(N,M,v)I=(N,M,v) where N is a set of n agents, M is a set of m indivisible items, and v=(v1,…,vn)v=(v_1,…,v_n) is a valuation profile, where each vi:2M→ℝv_i:2^M is a valuation function for agent i assigning a value to every subset of items S⊆MS M. In this work, we assume non-negative and additive valuations, that is, vi(S)∈ℝ0+v_i(S) _0^+ for all S⊆MS M and for each agent i∈Ni∈ N, and vi(S)=∑g∈Svi(g)v_i(S)= _g∈ Sv_i(\g\). Since we assume non-negative valuations, we will refer to items as goods. For brevity, we will write vi(g)v_i(g) instead of vi(g)v_i(\g\) throughout the paper. In the classical setting, an allocation is a tuple A=(A1,A2,…,An)A=(A_1,A_2,…,A_n) where each Ai⊆MA_i M is the bundle allocated to an agent i and satisfy two properties, namely (1) non-shareability: Ai∩Aj=∅A_i∩ A_j= for all i≠ji≠ j and (2) completeness: ⋃i∈NAi=M _i∈ NA_i=M. In other words, an allocation corresponds to a partition of the set of goods M into n disjoint subsets, with no good assigned to more than one agent. In this work, we focus on maximin share (MMS) fairness Budish2011, which is one of the most well-studied notions in discrete fair allocation literature. It guarantees each agent at least their maximin share value (MMSin(M)MMS_i^n(M)), that is, vi(Ai)≥MMSin(M)v_i(A_i) _i^n(M) where MMSin(M):=max(A1,…,An)∈n(M)minj∈[n]vi(Aj),MMS_i^n(M):= _(A_1,…,A_n) ^n(M) _j∈[n]v_i(A_j), (1) and n(M)A^n(M) denotes the set of all possible n-partitions of the set of goods M. In other words, the maximin share value MMSiMMS_i for an agent i is the maximum value she can guarantee for herself by partitioning the goods into n bundles and receiving the least valued bundle. While MMS often fails to exist in discrete fair allocation problems under the standard assumptions of non-shareability, we reveal new pathways to fairness by introducing cost-sensitive restricted sharing. We now formalize the problem setting in the subsequent section. 4. Problem Formulation We investigate fair allocation settings where each good is allowed to be shared among a fixed number of agents k. We introduce k-sharing allocations. Definition . A k-sharing allocation is a tuple A=(A1,…,An)A=(A_1,…,A_n) where the bundles Ai⊆MA_i M satisfy two properties, namely (1) k-limited shareability: ⋂i∈SAi=∅ _i∈ SA_i= , for every group S⊆NS N of size |S|>k|S|>k and (2) completeness: ⋃i∈NAi=M _i∈ NA_i=M. Further, kn(M)A_k^n(M) denotes the set of all possible k-sharing allocations of goods M. The k-limited shareability condition ensures that each good can be shared among at most k agents. To denote the set of agents sharing a good g under allocation A, we use Ng(A):=i∈N:g∈Ai.N_g(A):=\i∈ N:g∈ A_i\. According to the k-limited shareability condition, we are required to satisfy |Ng(A)|≤k|N_g(A)|≤ k. Additionally, we say that a k-sharing allocation is fully-shared if every good is shared by exactly k agents, that is, |Ng(A)|=k|N_g(A)|=k for all g∈Mg∈ M. In the classical (11-sharing) model, goods are allocated exclusively, and each agent’s utility is determined solely by the goods in her bundle. However, in the k-sharing setting, the utility an agent derives from a good may depend not only on having access to it but also on how many share it. Thus, rather than defining utility based only on the agent’s individual bundle, we consider utility functions uiu_i that take the full allocation A as input. Definition . The utility of an agent i in a k-sharing setting, ui:kn(M)→ℝ0+u_i _k^n(M) _0^+, is defined as ui(A)=∑g∈Ai[1−ci,g(Ng(A))]⋅vi(g)u_i(A)= _g∈ A_i [1-c_i,g(N_g(A)) ]· v_i(g) (2) with ci,g(Ng(A))∈[0,1]c_i,g(N_g(A))∈[0,1] denoting the cost incurred by agent i for sharing good g with agents Ng(A)N_g(A). Additionally, ci,g(Ng(A))=0 if |Ng(A)|=1.c_i,g(N_g(A))=0 if |N_g(A)|=1. (3) In this work, we consider goods-based cost models, where for every agent i∈Ni∈ N and good g∈Mg∈ M, the cost depends only on the number of agents sharing g, and is given by ci,g(Ng(A))=cg(|Ng(A)|)∈[0,1]c_i,g(N_g(A))=c_g(|N_g(A)|)∈[0,1]. (1) Cost-free sharing: cg(|Ng(A)|)=0c_g(|N_g(A)|)=0 for every g∈Mg∈ M (no cost of sharing). Here, the utility of agent i equals the valuation of their allocated bundle (including their shared goods), ui(A)=vi(Ai)u_i(A)=v_i(A_i). (2) Equal-share cost-sharing: cg(|Ng(A)|)=1−1|Ng(A)|c_g(|N_g(A)|)=1- 1|N_g(A)| for all g∈Mg∈ M. Therefore, each agent receives a utility of 1|Ng(A)| 1|N_g(A)| fraction of her valuation for the good g allocated to her, ui(A)=∑g∈Ai1|Ng(A)|⋅vi(g).u_i(A)= _g∈ A_i 1|N_g(A)|· v_i(g). (3) Generous cost-sharing: cg(|Ng(A)|)∈[0,1−1|Ng(A)|]c_g(|N_g(A)|)∈[0,1- 1|N_g(A)|] for every g∈Mg∈ M. Further, we assume costs are non-decreasing in the number of sharers: cg(ℓ′)≤cg(ℓ)c_g( )≤ c_g( ) for ℓ′<ℓ < . When cg(|Ng(A)|)=0c_g(|N_g(A)|)=0 for all g∈Mg∈ M, the model becomes cost-free. When cg(|Ng(A)|)=1−1|Ng(A)|c_g(|N_g(A)|)=1- 1|N_g(A)| for all g∈Mg∈ M, it represents equal-share. Using all the components, we now denote a cost-sensitive k-sharing fair allocation instance as a tuple (N,M,k,v,c)(N,M,k,v,c) where N is the set of n agents, M is the set of m goods, k is the sharing constraint, v=(vi,…,vn)v=(v_i,…,v_n) is the valuation profile, and the sharing-cost function is denoted by c=(cg(ℓ)))g∈M,ℓ∈1,…,kc=(c_g( )))_g∈ M, ∈\1,…,k\. 5. MMS under Cost-Sensitive Sharing A k-sharing allocation A∈kn(M)A _k^n(M) satisfies MMS if ui(A)≥MMSin(M)u_i(A) _i^n(M) for all i∈Ni∈ N (as defined in Equation 1). While sharing increases the flexibility to achieve fairer outcomes—by allowing agents to receive more (potentially shared) goods—it also introduces costs that complicate the structure of the utility function. For any given good, the utility an agent derives can be, due to the costs, lower when the good is shared than when it is received exclusively. We now highlight the generalizability of the equal-share cost-sharing model in terms of satisfying MMS, or any other threshold-based fairness notions. Observation 1. In a k-sharing setting, if an allocation satisfies MMS under equal-share cost-sharing model, then the allocation also satisfies MMS under any generous cost-sharing model, including cost-free sharing model. Observation 1 follows directly from the definitions of the cost-sharing models, implying that an agent’s utility for a given k-sharing allocation under the equal-share model cg(|Ng(A)|)=1−1|Ng(A)|c_g(|N_g(A)|)=1- 1|N_g(A)| increases when we consider lesser cost of sharing, 0≤cg(|Ng(A)|)<1−1|Ng(A)|0≤ c_g(|N_g(A)|)<1- 1|N_g(A)|. Therefore, we focus on the equal-share cost-sharing model to investigate the existence of MMS in the cost-sensitive k-sharing setting. Intuitively, allowing goods to be shared among more agents increases the likelihood of achieving a fair allocation. Indeed, when k=nk=n, each item can be shared among all agents, trivially satisfying MMS. Sharing among at Least Half of the Agents Assuming k≥n/2k≥ n/2 under equal-share cost-sharing model, we establish the existence of MMS when n is even, with a weaker MMS guarantee when n is odd. theorem In every k-sharing instance (N,M,k,v,c)(N,M,k,v,c) under equal-share cost-sharing model, with k≥n/2k≥ n/2 agents, there exists an allocation A that for every agent i satisfies: • ui(A)≥MMSin(M)u_i(A) _i^n(M) if n is even, • ui(A)≥MMSin+1(M)u_i(A) _i^n+1(M) if n is odd. Proof. We provide a constructive proof for both the cases. First, we consider n to be even. We arrange all the agents into ℓ=n/2 =n/2 disjoint pairs. For each pair of agents, i,j\i,j\, we define a classical (no-sharing) fair allocation instance, Ii,j=(N=i,j,M,v=(vi,vj))I_i,j=(N=\i,j\,M,v=(v_i,v_j)). Since MMS allocation can always be obtained when there are 2 players, we find one such allocation and denote it as Ai,j=(Ai,Aj)A_i,j=(A_i,A_j). Note that the allocated bundles between each pair are disjoint, Ai∩Aj=∅A_i∩ A_j= . Now, let us consider all such allocated bundles from all ℓ pairs of agents A=(A1,…,An)A=(A_1,…,A_n). Since the allocated bundles between each of the ℓ pairs were disjoint, each good g appears in exactly ℓ different bundles in A, and the utility is reduced by a factor of 1/ℓ1/ . Therefore, for any agent i, the utility of AiA_i upon sharing each good with ℓ agents, under equal-share cost-sharing model is: ui(A) u_i(A) =∑g∈Ai(1−cg(ℓ))⋅vi(g) = _g∈ A_i(1-c_g( ))· v_i(g) =∑g∈Ai1ℓ⋅vi(g)=1ℓ⋅vi(Ai) = _g∈ A_i 1 · v_i(g)= 1 · v_i(A_i) ≥1ℓmaxB∈12(M)minh∈i,jvi(Bh)=1ℓ⋅MMSi2(M) ≥ 1 _B _1^2(M) _h∈\i,j\v_i(B_h)= 1 · MMS^2_i(M) (4) Now, let B∗∈12ℓ(M)B^* _1^2 (M) be the MMSin(M)MMS_i^n(M) maximizer. Let C be the union of the ℓ least-valued bundles in B∗B^* according to agent i, and let C′=M∖C =M C. Both C and C′C have total value at least ℓ⋅minh∈Nvi(Bh∗) · _h∈ Nv_i(B^*_h). Therefore, the bipartition (C,C′)∈12(M)(C,C ) _1^2(M) satisfies: minvi(C),vi(C′)≥ℓ⋅MMSin(M). \v_i(C),v_i(C )\≥ ·MMS_i^n(M). (5) Inequality (5) along with the fact that MMSi2(M)≥minvi(D),vi(D′) MMS^2_i(M)≥ \v_i(D),v_i(D )\ for any (D,D′)∈12(M)(D,D ) ^2_1(M), and combining with Inequality (4), we obtain ui(A)≥MMSin(M)u_i(A) _i^n(M) when n is even. Next, we consider n to be odd. In this case, we add a dummy agent with zero valuation for all goods. With n+1n+1 (even) agents, we apply the construction for even agents, obtaining k-sharing allocation of n+1n+1 agents, A, which satisfies: ui(A)≥MMSin+1(M)u_i(A) _i^n+1(M) for all agents i∈Ni∈ N. Finally, the dummy agent is removed and its goods are arbitrarily distributed among all the agents. Since this can only increase the utility of each agent in N, the result follows. ∎ Next, we show how to compute an α-approximate MMS allocation in polynomial time for any k≥2k≥ 2, possibly yielding a better approximation than algorithms without sharing. Approximate MMS via Cost-Sensitive k-Sharing Our polynomial-time algorithm, Shared Bag-Filling, (Algorithm 1) works under any general cost model with ci,g(Ng(A))∈[0,1]c_i,g(N_g(A))∈[0,1], including the generous cost-sharing models.for any cost-sharing model, not only for generous goods-based ones. This formally means that the costs satisfy ci,g(Ng(A))∈[0,1]c_i,g(N_g(A))∈[0,1] without any additional restrictions. The algorithm computes an α-approximate MMS allocation, with the guarantee depending on the maximum sharing cost: C:=maxi∈N,g∈M,S⊆N,|S|≤kci,g(S).C:= _i∈ N,g∈ M,S N,|S|≤ kc_i,g(S). Notably, Algorithm 1 requires neither the knowledge nor the computation of C. Algorithm 1 Shared Bag-Filling Algorithm 0: I=(N,M,k,v,c)I=(N,M,k,v,c) 0: The output allocation A is α-MMS where α=min1,(1−C)(k−1)α= \1,(1-C)(k-1)\. 1: N~←N N← N, M~←M M← M // remaining agents and goods Phase 1 2: while ∃i∈N,∃g∈M∃ i∈ N,∃ g∈ M s.t. vi(g)≥vi(M~)|N~|v_i(g)≥ v_i( M)| N| do 3: Ai←gA_i←\g\; M~←M~∖g M← M \g\; N~←N~∖i N← N \i\ 4: end while Phase 2 5: vinorm(g)←|N~|vi(M~)⋅vi(g)v_i^norm(g)← | N|v_i( M)· v_i(g) for all i∈N~i∈ N and all g∈M~g∈ M 6: Let ℳM be the multiset of k copies of each good from M~ M // denote the multiplicity of g in ℳM by ξℳ(g) _M(g) 7: v~i(g)=1k⋅vinorm(g) v_i(g)= 1k· v_i^norm(g) for all i∈N~,g∈M~i∈ N,g∈ M 8: while |N~|>1| N|>1 do 9: Initialize empty bag B←∅B← 10: while exists g∈ℳg s.t. ξℳ(g)=|N~| _M(g)=| N| do 11: B←B∪gB← B∪\g\ 12: ℳ←ℳ∖gM \g\ // ensures ξℳ(g)<|N~| _M(g)<| N| 13: end while 14: while v~i(B)<k−1k v_i(B)< k-1k for all i∈Ni∈ N do 15: Select arbitrary g∈ℳg such that g∉Bg∉ B 16: B←B∪gB← B∪\g\ and ℳ←ℳ∖gM \g\ 17: end while 18: Choose any agent i∗∈N~i^*∈ N such that v~i∗(B)≥k−1k v_i^*(B)≥ k-1k 19: Ai∗←BA_i^*← B 20: N~←N~∖i∗ N← N \i^*\ // invariant ξℳ(g)≤|N~| _M(g)≤| N| holds 21: end while 22: Aj←ℳA_j , where j is the remaining agent in N~ N 23: return A=(A1,…,An)A=(A_1,…,A_n) Algorithm 1 builds on the classic bag-filling technique Ghodsi2021; garg2019approximating; Garg2021, adapted to the k-sharing setting. It runs in two phases. Phase 1 allocates large goods, i.e., those with vi(g)≥vi(M)/|N|v_i(g)≥v_i(M)/|N| vi(M~)/|N~|v_i( M)/| N| for some i∈N~i∈ N. Since g already meets agent i’s MMS guarantee (in the instance with M~ M, N~ N), we can assign it directly to her and exclude her from further allocation, as by the monotonicity of MMS (see Appendix A), this does not reduce the MMS values of the remaining agents on the remaining goods. Phase 2 begins by normalizing the valuations of the remaining agents N′N by setting vinorm(M′)=|N′|v_i^norm(M )=|N |, where M′M are the remaining goods. This guarantees MMSinorm≤1MMS_i^norm≤ 1. In the subsequent steps, uinorm(A)≥MMSinormu_i^norm(A) _i^norm is ensured for each remaining agent, which implies the original MMS guarantee. Details are deferred to Appendix A. Each good g∈M’g∈ M’ is then replaced by k virtual copies (shares), and valuations are scaled so that each share has value v~i(g)=1k⋅vinorm(g) v_i(g)= 1k· v_i^norm(g). This transformation preserves total value and ensures that the final outcome corresponds to a fully-shared allocation over M’M’, while reducing the problem to allocating small items. Phase 2 then proceeds similarly to classic bag-filling, with the constraint that no bag contains multiple shares of the same good. It starts with an empty bag B, adds one share of each good whose number of remaining shares equals the number of remaining agents, then continues adding shares arbitrarily until some agent i satisfies v~i(B)≥k−1k v_i(B)≥ k-1k. The bag is allocated to agent i, and the process repeats. The last agent receives all remaining goods. For first |N′|−1|N |-1 agents, uinorm(A)≥(1−C)⋅vinorm(Ai)=(1−C)⋅k⋅v~i(Ai)≥(1−C)⋅k⋅k−1k=(1−C)⋅(k−1). splitu_i^norm(A)&≥(1-C)· v_i^norm(A_i)=(1-C)· k· v_i(A_i)\\ &≥(1-C)· k· k-1k=(1-C)·(k-1). split (6) Since the valuations are normalized, we have MMSinorm≤1MMS_i^norm≤ 1. Therefore, it holds uinorm(A)≥(1−C)(k−1)⋅MMSinormu_i^norm(A)≥(1-C)(k-1)·MMS_i^norm. There are two issues to address in the analysis of Phase 2. First, it is not immediately clear that the algorithm cannot get stuck—i.e., that at any point, there is always an item that can be added to the current bag when it is not acceptable to every agents. Second, it’s not obvious that the last agent, who receives the remaining goods, values them at least at their (1−C)(k−1)(1-C)(k-1)-MMS value. The key to understanding why these concerns do not arise lies in the following lemma, which shows that at every iteration of the algorithm there remain shares of sufficient amount and value to satisfy the remaining agents. Lemma At the beginning and the end of every iteration of Phase 2 (Lines 8-21) of Algorithm 1, for every i∈N~i∈ N, it holds v~i(ℳ)≥|N~|, v_i(M)≥| N|, where ℳM is the multiset of k copies of each good from M~ M. Proof. Initially, v~i(ℳ)=k⋅v~i(M′)=k⋅1k⋅vinorm(M′)=|N′| v_i(M)=k· v_i(M )=k· 1k· v_i^norm(M )=|N |. Assume that the invariant holds at the beginning of some iteration, when the remaining shares are ℳM. If the while loop at Line 14 does not execute, that is, already the initial bag B (containing exactly one share of each good whose number of remaining shares equals the number of remaining agents) satisfies v~i∗(B)≥k−1k v_i^*(B)≥ k-1k for some agent i∗i^*, then the bag is immediately assigned to agent i∗i^*. In this case, the total value of B is at most 1|N~|v~i(ℳ) 1| N| v_i(M) for every agent. This means v~i(ℳ∖B) v_i(M B) ≥v~i(ℳ)−1|N~|v~i(ℳ)=|N~|−1|N~|v~i(ℳ) ≥ v_i(M)- 1| N| v_i(M)= | N|-1| N| v_i(M) which is by the assumption larger or equal to |N~|−1| N|-1. Otherwise, if the loop starting at Line 14 executes at least once, additional goods are added to the bag B according to Lines 15-18. During this process, before the last good was added, the value of B was at most (k−1)/k(k-1)/k for every agent. As all shares are valued by all agents at most 1/k1/k, the value of the bag is at most 11. In both cases, the invariant is preserved. ∎ Combining Lemma 5 with the Phase 2 invariant—that the number of shares of every remaining item is at most the number of remaining agents—we conclude that a dead-end state cannot occur because if there is no share left to add to the bag, then every remaining agent must already prefer the bag. Proposition Phase 2 does not enter a dead-end state. Proof. Suppose that at some point, no share can be added to the current bag B without violating the “distinct goods” condition, while, at the same time, no agent values the bag at least (k−1)/k(k-1)/k. But This means B already contains at least one share of every remaining good in ℳM and since no good appears more than |N~|| N| times in ℳM, it follows for every i∈N~i∈ N that v~i(B)≥1|N~|⋅v~i(ℳ)≥1>k−1k. v_i(B)≥ 1| N|· v_i(M)≥ 1> k-1k. This contradicts the assumption of a dead-end state. ∎ The second issue is handled directly by Lemma 5. The lemma implies for the last agent i and the remaining shares ℳM of unique goods, v~i(ℳ)≥1 v_i(M)≥ 1, which means by receiving all of these shares, his utility is at least his MMS value in the instance with agents and goods from the start of Phase 2. By monotonicity of MMS (Appendix A), this completes the argument and yields the following result. The next result follows directly from Propositions LABEL:prop:correctness and 5, as well as from the monotonicity of MMS, scale invariance, and observation, that the algorithm runs in polynomial time. theorem Algorithm 1 computes in polynomial time the exact MMS k-sharing allocation, if (1−C)(k−1)≥1(1-C)(k-1)≥ 1, or (1−C)(k−1)(1-C)(k-1)-MMS k-sharing allocation otherwise. Proof. All players addressed in Phase 1 receive at least their MMS (guaranteed by monotonicity; Appendix A). Phase 2 operates on a normalized instance (Appendix A, scale invariance) where MMSin(M)inorm≤1MMS_i^n(M)_i^norm≤ 1 for all remaining agents. By Proposition 5, no dead-end occurs, therefore each agent except the last receives a bag B satisfying uinorm(B)≥(1−C)(k−1)u_i^norm(B)≥(1-C)(k-1) (Equation (6)), and the last agent receives all remaining goods, ensuring utility at least 1. Thus, the algorithm guarantees an exact MMS for all agents when (1−C)(k−1)≥1(1-C)(k-1)≥ 1, and (1−C)(k−1)(1-C)(k-1)-MMS otherwise. Clearly, the algorithm runs in polynomial time in the number of agents and goods. ∎ We note that for equal-share cost, where C=(k−1)/kC=(k-1)/k, the algorithm produces k−1k k-1k-MMS using this algorithm. However, when C is a fixed constant, exact MMS can always be achieved for sufficiently large k—specifically, whenever k≥1+11−Ck≥ 1+ 11-C. Equivalently, for a fixed k, exact MMS is attainable as long as C≤k−2k−1C≤ k-2k-1. Table 1 illustrates this trade-off between the maximal cost of sharing and sharing degree. Table 1. MMS Approximation factor obtained using Algorithm 1 for various values of C and k k C 0.0 0.1 0.2 0.3 0.5 0.7 0.8 0.9 0.99 2 1.0 0.9 0.8 0.7 0.5 0.3 0.2 0.1 0.01 3 1.0 1.0 1.0 1.0 1.0 0.6 0.4 0.2 0.02 4 1.0 1.0 1.0 1.0 1.0 0.9 0.6 0.3 0.03 5 1.0 1.0 1.0 1.0 1.0 1.0 0.8 0.4 0.04 6 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.5 0.05 8 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.7 0.07 10 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.9 0.09 15 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.14 20 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.19 25 1.0 1.0 1.0 1.0 1.0 1.0 1.0 1.0 0.24 6. Defining Stronger MMS for k-Sharing A natural generalization of the maximin share (MMS) to the k-sharing setting is to guarantee, for each agent i, the maximum over all k-sharing allocations of the minimum utility they could receive under some assignment of bundles. Formally, we introduce Sharing Maximin Share (SMMS). Definition (SMMS). A k-sharing allocation A is said to satisfy k-sharing maximin share (SMMS) if for each agent i∈Ni∈ N: ui(A)≥SMMSin,k(M)u_i(A) _i^n,k(M), where SMMSin,k(M):=maxB∈kn(M)minj∈[n]ui(Bi↔j),SMMS_i^n,k(M):= _B _k^n(M) _j∈[n]u_i(B_i j), (7) kn(M)A_k^n(M) is the set of all possible k-sharing allocations, and Bi↔jB_i j denotes the modified allocation obtained from B by swapping the bundles assigned to agents i and j. Note that although in this work we assume the sharing-cost and utility of any good depends only on the number of agents sharing the good, the representation of modified allocation as Bi↔jB_i j allows the sharing-cost and utility to be modeled as functions of the specific agents involved, rather than merely the size of the sharing group. In Definition 6, minj∈[n]ui(Bi↔j) _j∈[n]u_i(B_i j), captures the worst-case bundle in B for agent i, taking into account that in the k-sharing model the utility depends on the entire allocation, not just the agent’s own bundle. The utility ui(Bi↔j)u_i(B_i j) can be expressed as ui(Bi↔j)=∑g∈Bj[1−cg(|Ng(B)|)]⋅vi(g).u_i(B_i j)= _g∈ B_j [1-c_g(|N_g(B)|) ]· v_i(g). First, we investigate the existence of SMMS assuming some restricted cases: (1) only two agents and (2) identical valuations. Proposition For any k-sharing instance (N,M,k,v,c)(N,M,k,v,c) with generous cost-sharing model and |N|=k=2|N|=k=2, an SMMS allocation always exists. Proposition For any k-sharing instance (N,M,k,v,c)(N,M,k,v,c) with goods-based cost-sharing instance and identical valuations vi(g)=vj(g)v_i(g)=v_j(g) for i≠ji≠ j and for all g∈Mg∈ M, an SMMS allocation always exists. The proof of Propositions 6 and 6 are provided in Appendices B and C, respectively. For three agents, computing the SMMS becomes significantly more challenging because full-sharing (each good shared by exactly k agents) may not be the best option. Example (Full-sharing is not optimal) Consider an equal-share 2-sharing instance with three agents and two goods, g1g_1 and g2g_2. Agents have identical valuations: v(g1)=1v(g_1)=1 and v(g2)=2v(g_2)=2. An optimal allocation assigns g1g_1 to one agent, while g2g_2 is shared between the two remaining agents. In contrast to the equal-share model, the cost-free model always favors full sharing as the optimal choice. We note that the SMMS value of an agent under the generous cost-sharing model is within a factor of (1−C)(1-C) of their value in the cost-free model, where C is the maximal cost per good. The details of this comparison are provided in Appendix D. Surprisingly, we found that the existing MMS counterexamples Kurokawa2018; Feige2021, in fact, admit SMMS allocations, which we explore next. Incompatibility of MMS and SMMS In this section, we show that SMMS allocations can exist even in instances where MMS allocations do not. Conversely, we also provide a counterexample demonstrating that an SMMS allocation may fail to exist even when an MMS allocation does exist. Feige2021 considers n=3n=3 agents and m=9m=9 goods in which no MMS allocation exists under 1-sharing. The instance is defined by agent-specific valuations over the goods, represented as 3×33× 3 matrices: V1=[116232641012199],V2=[11622264913209],V3=[115232541013209].V_1= bmatrix1&16&23\\ 26&4&10\\ 12&19&9 bmatrix,V_2= bmatrix1&16&22\\ 26&4&9\\ 13&20&9 bmatrix,V_3= bmatrix1&15&23\\ 25&4&10\\ 13&20&9 bmatrix. The goods are indexed from 1 to 9 in row-major order. Although no MMS allocation exists under 11-sharing, we observe that SMMS allocations do exist for both the equal-share and cost-free cost-sharing models even under 22-sharing. Equal-Share SMMS Allocation In the equal-share model, the sum of utilities of all bundles, given an allocation A is equal to vi(M)v_i(M) for every agent i. As vi(M)=120v_i(M)=120, SMMSin,k(M)≤40SMMS_i^n,k(M)≤ 40. At the same time, we have the following allocation with the corresponding utility, proving SMMSin,k(M)=40SMMS_i^n,k(M)=40 for every agent i: • Agent 1 receives goods 1,2,3\1,2,3\, utility: 40.00, • Agent 2 receives goods 4,5,8\4,5,8\, utility: 40.00, • Agent 3 receives goods 6,7,8,9\6,7,8,9\, utility: 42.00, This is thus SMMS allocation. Notice that it was enough to share only one of the goods to achieve SMMS. Cost-Free SMMS Allocation As the utility of the least bundle in equal-share is bounded by 40, in cost-free sharing, the value of the least bundles is valued at most twice this price, i.e., SMMSin,k(M)≤80SMMS_i^n,k(M)≤ 80 for every i∈Ni∈ N. The following allocation: • Agent 1 receives goods 1,2,3,4,5,6\1,2,3,4,5,6\, utility: 80.00, • Agent 2 receives goods 2,3,7,8,9\2,3,7,8,9\, utility: 80.00, • Agent 3 receives goods 4,5,6,7,8,9\4,5,6,7,8,9\, utility: 81.00, is thus an SMMS allocation. A similar behaviour can be observed for the example from Kurokawa2018, where they constructed an instance with n=3n=3 and m=12m=12 goods, in which no 1-sharing MMS allocation exists. The valuation of agent i∈Ni∈ N for a good (k,ℓ)∈M(k, )∈ M is given by vi(k,ℓ)=106⋅Sk,ℓ+103⋅Tk,ℓ+Ek,ℓi,v_i(k, )=10^6· S_k, +10^3· T_k, +E^i_k, , where S=[111111111111],T=[17251212223281102123]S= bmatrix1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 bmatrix, T= bmatrix17&25&12&1\\ 2&22&3&28\\ 11&0&21&23 bmatrix and E1=[3−1−1−100000000],E2=[3−100−1000−1000],E3=[30−1000−10000−1].E^1= [ smallmatrix3&-1&-1&-1\\ 0&0&0&0\\ 0&0&0&0 smallmatrix ],E^2= [ smallmatrix3&-1&0&0\\ -1&0&0&0\\ -1&0&0&0 smallmatrix ],E^3= [ smallmatrix3&0&-1&0\\ 0&0&-1&0\\ 0&0&0&-1 smallmatrix ]. Equal-Share SMMS Allocation For each agent, vi(M)=12,165,000v_i(M)=12,165,000 for every i∈Ni∈ N, thus SMMSin,k(M)≤vi(M)3=4,055,000SMMS_i^n,k(M)≤ v_i(M)3=4,055,000. The following allocation: • Agent 1 - 1,2,3,5,10\1,2,3,5,10\, utility: 4,055,001, • Agent 2 - 4,7,8,12\4,7,8,12\, utility: 4,055,000, • Agent 3 - 5,6,9,10,11\5,6,9,10,11\, utility: 4,055,000. is thus an SMMS allocation. Cost-Free SMMS Allocation Once again, assuming the SMMS value in the cost-free model is at most twice the SMMS value in equal share, we get SMMSin,k(M)≤8,110,000SMMS_i^n,k(M)≤ 8,110,000. The following allocation is thus an SMMS allocation: • Agent 1 - 1,2,3,5,7,8,10,12\1,2,3,5,7,8,10,12\, utility: 8,110,001, • Agent 2 - 1,3,4,6,7,9,11,12\1,3,4,6,7,9,11,12\, utility: 8,110,001, • Agent 3 - 2,4,5,6,8,9,10,11\2,4,5,6,8,9,10,11\, utility: 8,110,000. However, under 2-sharing, the following allocation ensures SMMS under cost-free model: Similarly, in the example by Kurokawa2018, the following 2-sharing allocation also gives each agent their SMMS value under cost-free model: Justification for these SMMS allocations and similar results under equal-share cost are deferred to Appendix LABEL:app:smms-superior. Given these examples, it may seem that achieving SMMS is easier than achieving MMS; however, we provide a counterexample for SMMS by using the structure of the instance proposed by Kurokawa2018, where SMMS does not exist, even though MMS does. theorem There exists an instance of cost-free 22-sharing problem with n=3n=3 and m=12m=12, which does not admit an SMMS allocation, but admits MMS allocation. Proof. Let M=(k,ℓ)∣k∈[3],ℓ∈[4]M=\(k, ) k∈[3], ∈[4]\. The valuation of agent i∈Ni∈ N for a good (k,ℓ)∈M(k, )∈ M is given by vi(k,ℓ)=107⋅Sk,ℓ+103⋅Tk,ℓ+Ek,ℓi,v_i(k, )=10^7· S_k, +10^3· T_k, +E^i_k, , S=[111111111111],T=[17251212223281102123],S= bmatrix1&1&1&1\\ 1&1&1&1\\ 1&1&1&1 bmatrix, T= bmatrix17&25&12&1\\ 2&22&3&28\\ 11&0&21&23 bmatrix, E1=[−21010000−1010],E2=[00−2001000100],E3=[−1−10000100100].E^1= [ smallmatrix-2&1&0&1\\ 0&0&0&0\\ -1&0&1&0 smallmatrix ],E^2= [ smallmatrix0&0&-2&0\\ 0&1&0&0\\ 0&1&0&0 smallmatrix ],E^3= [ smallmatrix-1&-1&0&0\\ 0&0&1&0\\ 0&1&0&0 smallmatrix ]. The choice of matrix S enforces that for each agent i, his SMMSi3,2(M)SMMS_i^3,2(M) is achieved for an allocation which assigns each good to exactly two agents, i.e. each agent receives 8 goods. Under such 22-sharing allocations, SMMSi3,2(M)∼8⋅107SMMS_i^3,2(M) 8· 10^7 for every agent, which cannot be achieved for allocations where any share contains less than 8 goods (in such case, such agent receives strictly less than 8⋅1078· 10^7). Matrix T was chosen in such a way that if we label it using three different types of labels (numeric: 1,2,31,2,3, Greek: α,β,γα,β,γ, and symbols: +,−,∗+,-,*), entries corresponding to one specific label sum to exactly 55: T=[17+1α25−1α12+1β1∗1γ2−2α22∗2β3+2γ28−2γ11+3α0−3β21∗3β23+3γ].T= bmatrix^α17^1_+&^α25^1_-&^β12^1_+&^γ1^1_*\\ ^α2^2_-&^β22^2_*&^γ3^2_+&^γ28^2_-\\ ^α11^3_+&^β0^3_-&^β21^3_*&^γ23^3_+ bmatrix. Since the total sum of entries in matrix T is 3×55=1653× 55=165, any other partitioning of the goods into three bundles of four must include one whose sum in T is strictly less than 55. Now, consider an allocation that divides M into three bundles, each containing 8 goods. Each bundle is constructed by selecting goods associated with two labels of the same type—for instance, one bundle includes goods labeled with α and β, another with β, γ, and the third with α, γ. In this allocation, the sum of entries in T for each bundle is exactly 110. By the argument above, any allocation that does not follow this label-based structure yields at least one bundle for which the sum of entries in T is strictly less than 110. This means, if there is an SMMS allocation, it must be one of those described above; assigning pairs of labels to agents (1) according to 1,2,3, (2) according to α, β, γ, (3) according to ++, −-, ∗*. Each of the three ways guarantees SMMSi3,2(M)SMMS_i^3,2(M) to one of the agents i, which is the same for all of the agents and equal to 8,110,0008,110,000. However, none of the three ways assign SMMSi3,2(M)SMMS_i^3,2(M) to all of the agents at the same time. This is enforced by the structure of matrices E1E^1, E2E^2, and E3E^3. In division according to 1,2,3, both agent 2 and agent 3 need to be assigned elements with labels 2 and 3, otherwise their value is 8,109,9998,109,999. Similarly, in division according to α,β,γα,β,γ, both agents 1 and 3 need to be assigned elements with β and γ, or, once again, their value is less than their SMMS value. Finally, in division according to +,−,∗+,-,*, both agents 1 and 2 need to be assigned elements with −- and ∗*. Finally, assigning each agent their corresponding row (i.e., the first row to the first agent and so on) yields a valid 11-sharing MMS allocation. ∎ Despite the lack of general existence, we show that an α(1−C)α(1-C)-SMMS allocation of a goods-based cost-sharing model with C being the maximal cost can be computed in polynomial time, via a reduction to α-CMMS. 7. Approximate SMMS We provide a connection of SMMS with the cardinality-constrained maximin share (CMMS). An instance of the fair allocation problem under cardinality constraints Hummel2022; Biswas2018 is denoted as (N,M,v,b)(N,M,v,b) where N is the set of agents, M=C1,…,CℓM=\C_1,…,C_ \ is a set of goods partitioned into sets CiC_i according to ℓ types and b=(b1,…,bℓ)b=(b_1,…,b_ ) is the budget profile of types. In this setting, only a subset of allocations ℱ⊆A1n(M)F A^n_1(M) is feasible; under feasible allocation, no player can receive more than bib_i goods of type i. Formally, A∈ℱA satisfies for every i∈[n]i∈[n], j∈[ℓ]j∈[ ] that |Ai∩Cj|≤bj|A_i∩ C_j|≤ b_j. Here, the cardinality-constrained maximin share (CMMS) value is CMMSin(M):=maxA∈ℱminj∈[n]vi(Aj).CMMS^n_i(M):= _A _j∈[n]v_i(A_j). (8) In any goods-based cost-sharing setting with cg(|Ng(A)|)∈[0,1]c_g(|N_g(A)|)∈[0,1], fully-shared SMMS allocations correspond to allocations of CMMS of a special case of the fair allocation model under cardinality constraints, as stated in Proposition 7 (see Appendix E for more details and proof). Proposition For every instance I=(N,M,u)I=(N,M,u) of the goods-based k-sharing problem, there exists an instance I~=(N,M~,v~,b) I=(N, M, v,b) of a fair allocation under cardinality constraints such that fully-shared allocations A∈knA _k^n correspond bijectively to feasible allocations A~∈ℱ A , and the bijection preserves agents’ utilities: ∀i∈N,ui(A)=v~i(A~i)∀ i∈ N,u_i(A)= v_i( A_i). If we define the full-sharing maximin share value SMMS¯i SMMS_i by restricting the SMMS definition to full-k-sharing allocations, then it follows from Proposition 7 that CMMSi=SMMS¯iCMMS_i= SMMS_i for every i∈Ni∈ N and also any α-CMMS allocation A~ A corresponds to an α-SMMS¯ SMMS allocation A. As SMMS¯i SMMS_i is defined over less allocations than SMMSiSMMS_i, we have SMMSi≥SMMS¯iSMMS_i≥ SMMS_i. More importantly, we can bound SMMSiSMMS_i and MMSiMMS_i by SMMS¯i SMMS_i from above, allowing us to construct approximations of these by α-CMMSCMMS allocations. Lemma For every goods-based k-sharing model with maximal possible sharing cost C, it holds (1) SMMS¯i≥(1−C)⋅SMMSi SMMS_i≥(1-C)·SMMS_i, (2) SMMS¯i≥k⋅(1−C)⋅MMSi SMMS_i≥ k·(1-C)·MMS_i. Proof. (1.) Let a k-sharing allocation A be an SMMSiSMMS_i maximizer , and let B be a fully-shared allocation obtained by taking A and assigning the remaining shares of each good to arbitrary agents. Consequently, Aj⊆BjA_j B_j for every j∈Nj∈ N. Since A is SMMSiSMMS_i maximizer, SMMSiSMMS_i is equal to minj∈Nui(Ai↔j) _j∈ Nu_i(A_i j) =minj∈N∑g∈Aj(1−cg(|Ng(Ai↔j)|))⋅vi(g) = _j∈ N _g∈ A_j (1-c_g (|N_g(A_i j)| ) )· v_i(g) ≤minj∈N∑g∈Ajvi(g) ≤ _j∈ N _g∈ A_jv_i(g) (9) where the last inequality follows from the fact that removing costs increases utility. Further, since B is a fully-shared allocation, we have that SMMS¯i SMMS_i is at least minj∈Nui(Bi↔j) _j∈ Nu_i(B_i j) =minj∈N∑g∈Bj(1−cg(|Ng(Bi↔j)|))⋅vi(g) = _j∈ N _g∈ B_j(1-c_g(|N_g(B_i j)|))· v_i(g) ≥(1−C)⋅minj∈N∑g∈Bjvi(g) ≥(1-C)· _j∈ N _g∈ B_jv_i(g) (10) where the final inequality uses that C is the maximum cost. Finally, since Aj⊆BjA_j B_j, we have (1−C)⋅minj∈N∑g∈Bjvi(g)≥(1−C)⋅minj∈N∑g∈Ajvi(g)(1-C)· _j∈ N _g∈ B_jv_i(g)≥(1-C)· _j∈ N _g∈ A_jv_i(g) which in combination with (7) and (7) concludes the proof. (2.) Let a 1-sharing allocation A∈1nA _1^n be an MMSiMMS_i maximizer. We construct a different fully-shared allocation B by giving each agent their own bundle from A and the next k−1k-1 consecutive bundles, looping around to the beginning if we run out. Without the costs, each agent i values each bundle in B more than k-times the least valuable bundle in A, i.e., ∀j∈N∀ j∈ N, we have vi(Bj)≥k⋅minℓ∈Nvi(Aℓ)≥k⋅MMSi.v_i(B_j)≥ k· _ ∈ Nv_i(A_ )≥ k·MMS_i. (11) Note that (7) still holds for this allocation B, since the inequality relied only on B being full-sharing. Combining (7) with (11) therefore gives us: SMMS¯i≥(1−C)⋅minj∈Nvi(Bj)≥k⋅(1−C)⋅MMSi. SMMS_i≥(1-C)· _j∈ Nv_i(B_j)≥ k·(1-C)·MMS_i. ∎ By combining the equivalence between CMMSCMMS and SMMS¯ SMMS with the upper bounds from Lemma 7, we obtain approximation results for both MMS and SMMS. Proposition Let α∈(0,1]α∈(0,1], and suppose that for every fair division instance with cardinality constraints, there exists an α-CMMSCMMS allocation. Then, for any goods-based k-sharing model with maximum cost C, there exist: • an α⋅(1−C)α·(1-C)-SMMSSMMS allocation, and • an α⋅k⋅(1−C)α· k·(1-C)-MMSMMS allocation. The best known α=1/2α=1/2 Hummel2022 gives a 12 12-SMMS guarantee in the cost-free model and 12k 12k-SMMS under equal-share. Also, while a larger k leads to a worse approximation factor, the SMMS value may increase due to the greater flexibility in sharing. Regarding MMS approximations, we note that α=1/2α=1/2 does not improve upon the bag-filling algorithm (Proposition 5), which guarantees (k−1)(1−C)(k-1)(1-C)-MMS. However, for α>k−1kα> k-1k, the approach via α-CMMS yields better guarantees—meaning that improvements occur even for α=1/2+εα=1/2+ with arbitrarily small ε>0 >0. 8. Conclusion In this paper, we studied how allowing limited sharing of indivisible goods affects fairness, specifically focusing on Maximin Share (MMS) fairness. By permitting goods to be shared among up to k agents, we found that previously unattainable fairness guarantees become achievable. We introduced Sharing Maximin Share (SMMS) fairness and for both notions explored when fair solutions exist, revealing important trade-offs between fairness, sharing costs, and the maximum number of agents allowed to share each good. Our analysis highlighted the challenges arising when agents have different opinions on sharing—some may prefer to share goods, while others may not—particularly under equal-share. These differences underline the difficulty of designing fair allocation methods acceptable to all agents. Our findings show that allowing bounded cost-sensitive sharing greatly improves the practicality of fair allocations, provided that the costs of sharing are not excessive, making our proposed mechanisms suitable for scenarios where sharing is possible. Table 1 could be viewed as a baseline for future work refining the boundary where sharing can or cannot lead to improved MMS guarantees depending on the parameters k and C. A key open question is determining the lower bound on the number of agents k needed to achieve fairness under generous cost-sharing model. The theoretical results established in this paper open up new research directions for fair resource allocation when a limited sharing of resources are allowed in multi-agent environments. It opens the door to exploring various cost-sharing models that reflect structured, real-world constraints. One promising direction is to consider models where the cost of sharing is determined not by the goods themselves, but by the group of other agents they are sharing with—for example, agents may differ in how effectively they can make use of shared resources, with some incurring lower costs when participating in sharing, and costs being divided equally when similarly capable agents share the same good. acks This work was carried out while H.S. and M.C. were participants in the 2025 DIMACS REU program at Rutgers University, supported by the NSF grant CCF-2447342. H.S. and M.C. were partly supported by the RSJ Foundation and by the Department of Applied Mathematics and the Computer Science Institute of Charles University. H.S. was supported by the Horizon Europe Programme under Grant Agreement No. 101183743 (AGATE). References Appendix A Details of the Algorithm 1 At the Phase 1 of Algorithm 1, large goods are given to respective agents with an assumption, that this process will reduce the problem of MMS allocation between a smaller number of agents with smaller number of small goods. This reduction is justified by monotonicity of the MMS, a result which was already proved for example by Feige2021. For the sake of completeness, we provide the proof. Proposition (Monotonicity of MMS) Let I=(N,M,k,v,c)I=(N,M,k,v,c) be an instance of the fair division problem. For every i∈Ni∈ N and every g∈Mg∈ M, it holds MMSin−1(M∖g)≥MMSin(M).MMS_i^n-1(M \g\) _i^n(M). Proof. Let A=(A1,…,An)A=(A_1,…,A_n) be an MMSiMMS_i maximizer and assume without loss of generality that g∈Ang∈ A_n, n≠in≠ i. Then for allocation of n−1n-1 agents, B=(A1,…,An−2,An−1∪An∖g)B=(A_1,…,A_n-2,A_n-1∪ A_n \g\), the minimal bundle is at least the minimal bundle of A, proving the monotonicity. ∎ At the beginning of Phase 2 of Algorithm 1, |N~|≥1| N|≥ 1 and, unless MMSin(M)=0MMS_i^n(M)=0 in the original instance, the value of the remaining goods is vi(M~)>0v_i( M)>0 for all i∈N~i∈ N. Therefore, we scale valuations of remaining agents by factor |N~|vi(M~)>0 | N|v_i( M)>0, so that the MMS value of every remaining agent is bounded from above by 11. The following proposition shows that this does not ruin the approximation guarantee. Corresponding result for classical setting was used and proved by garg2019approximating, our proof is a natural generalization of their proof for k-sharing setting. Proposition (Scale Invariance) Let A=(A1,…,An)A=(A_1,…,A_n) be an α-MMS k-sharing allocation for instance I=(N,M,v,k,c)I=(N,M,v,k,c). If valuations are scaled by a positive factor r>0r>0, i.e., vir(g)=r⋅vi(g)v^r_i(g)=r· v_i(g) for every i∈Ni∈ N, allocation A remains α-MMS in the scaled instance Ir=(N,M,k,vr,c)I^r=(N,M,k,v^r,c). Proof. Let MiM_i and MirM^r_i denote the MMS value of agent i in instance I and IrI^r respectively. For any k-sharing allocation A∈knA _k^n, we have uir(A) u_i^r(A) =∑g∈Ai(1−ci,g(Ng(A)))⋅vir(g) = _g∈ A_i(1-c_i,g(N_g(A)))· v_i^r(g) =∑g∈Ai(1−ci,g(Ng(A)))⋅r⋅vi(g) = _g∈ A_i(1-c_i,g(N_g(A)))· r· v_i(g) =r∑g∈Ai(1−ci,g(Ng(A)))⋅vi(g) =r _g∈ A_i(1-c_i,g(N_g(A)))· v_i(g) =r⋅ui(A). =r· u_i(A). Therefore Mir=r⋅MiM^r_i=r· M_i. Let A be an α-MMS k-sharing allocation for instance I. Since uir(A)=r⋅ui(A)≥r⋅α⋅Mi=α⋅Miru^r_i(A)=r· u_i(A)≥ r·α· M_i=α· M^r_i, A is an α-MMS allocation even in the scaled instance IrI^r. ∎ Appendix B SMMS with Two Agents Proposition 6. For any generous goods-based 22-sharing instance (N,M,k,v,c)(N,M,k,v,c) with |N|=2|N|=2, an SMMS allocation always exists. Proof. We show that the 2-sharing allocation C=(M,M)C=(M,M), in which all goods are assigned to both agents, is an SMMS allocation. To this end, let A=(B1∪S,B2∪S)A=(B_1∪ S,B_2∪ S) be an SMMS maximizer for agent i where B1∩B2=∅B_1∩ B_2= , and suppose agent i∈Ni∈ N receives the smaller share, i.e., vi(Bi)≤vi(Bj)v_i(B_i)≤ v_i(B_j). This means that vi(Bi)≤vi(Bi)+vi(Bj)2≤ui(D),v_i(B_i)≤ v_i(B_i)+v_i(B_j)2≤ u_i(D), where in 22-sharing allocation D, agent i receives only the set Bi∪BjB_i∪ B_j, shared entirely with agent j, and no other goods. The difference between ui(D)u_i(D) and ui(C)u_i(C) is exactly the utility agent i receives from the shared goods S, which also accounts for the difference between ui(A)u_i(A) and vi(Bi)v_i(B_i). It therefore follows that ui(A)≤ui(C)u_i(A)≤ u_i(C), and so the fully-shared allocation C satisfies the SMMS condition. ∎ Appendix C SMMS under Identical Utilities We initiate this section by proving Proposition 6, before we show that in general, identical utilities appear only in goods-based cost-sharing models. Proposition 6. For any goods-based cost-sharing instance (N,M,k,v,c)(N,M,k,v,c) with identical valuations vi(g)=vj(g)v_i(g)=v_j(g) for i≠ji≠ j and for all g∈Mg∈ M, an SMMS allocation always exists. First, we can observe that if all agents have identical utilities, an SMMS allocation always exists for any instance (N,M,k,v,c)(N,M,k,v,c). The proof is straightforward, relying on the fact that any allocation that is an SMMS maximizer for one agent is an SMMS maximizer for all other agents, therefore it is an SMMS allocation. Observation 2. For any instance (N,M,k,v,c)(N,M,k,v,c) with identical utilities, i.e., ui(A)=uj(Ai↔j)u_i(A)=u_j(A_i j) for all A∈knA _k^n and all i,j∈Ni,j∈ N, an SMMS allocation always exists. We further establish in Proposition C that in the k-sharing setting identical utilities occur precisely when agents have identical valuations and the cost structure is goods-based. Proposition In a k-sharing instance (N,M,k,v,c)(N,M,k,v,c), all agents have identical utility functions, i.e., ui(A)=uj(Ai↔j) for all i,j∈N,A∈knu_i(A)=u_j(A_i j) for all i,j∈ N,A _k^n if and only if all agents have identical valuations and the costs are goods-based. Proof. (⇐ ) If all agents have identical valuations and the costs are goods-based, then utility depends only on the allocation structure, not the agent’s identity. Therefore, all agents have identical utility functions. (⇒ ) Assume that all agents have identical utility functions. Fix a good g∈Mg∈ M, and consider any 1-sharing allocation A in which agent i is allocated only good g. Then for any i,j∈Ni,j∈ N, we have vi(g)=vi(Ai)=ui(A)=uj(Ai↔j)=vj(Ai)=vj(g),v_i(g)=v_i(A_i)=u_i(A)=u_j(A_i j)=v_j(A_i)=v_j(g), so all agents have identical valuations. Now consider two groups S,S′⊆NS,S N of the same size, along with agents i∈Si∈ S and j∈S′j∈ S . To show that ci,g(S)=cj,g(S′)c_i,g(S)=c_j,g(S ), consider an arbitrary set T⊆NT N of size at most k, and an allocation A in which good g is shared by all agents in T, while the remaining goods are allocated arbitrarily among the agents in N∖TN T , while preserving k-sharing . Further, fix x∈Tx∈ T and y∈N∖xy∈ N x. We make two observations based on whether y∈Ty∈ T, the relation ux(A)=uy(Ax↔y)u_x(A)=u_y(A_x y), and the fact that both agents receive only good g in the respective allocations: (1) If y∈Ty∈ T, then (1−cx,g(T))⋅v(g)=(1−cy,g(T))⋅v(g)(1-c_x,g(T))· v(g)=(1-c_y,g(T))· v(g) ⟹cx,g(T)=cy,g(T). c_x,g(T)=c_y,g(T). (2) If y∉Ty∉ T, then (1−cx,g(T))⋅v(g)=(1−cy,g(T∖x∪y))⋅v(g)(1-c_x,g(T))· v(g)=(1-c_y,g(T x∪ y))· v(g) ⟹cx,g(T)=cy,g(T∖x∪y). c_x,g(T)=c_y,g(T x∪ y). The first observation means that when a group of agents shares a good among themselves, each agent incurs the same cost for the sharing. The second observation, in combination with the first, implies that if two equally-sized groups differ by exactly one agent (i.e., one agent from one group can be swapped for one from the other), then the cost of sharing the good in the first group is the same for each of its agent as the cost of sharing the good in the other group for each of its agent. Extending on this argument, we can gradually swap agents x∈S∖S′x∈ S S with agents y∈S′∖Sy∈ S S to transform S into S′S , preserving the cost at each step. This shows that agents in S incur the same cost for sharing good g as those in S′S , which concludes the proof. ∎ Proposition 6 simply follows from the Observation 2 and Proposition C. Appendix D Comparing SMMS Across Cost Models Before turning to structural relationships between fairness notions, we briefly compare the SMMS values obtained under different cost-sharing models. In particular, we consider how the cost-free and generous models relate. Lemma Let SMMSicfSMMS^cf_i be the SMMS value of agent i in the cost-free model and SMMSiCSMMS^C_i the SMMS value of agent i in a generous cost-sharing model with maximal cost for sharing a good being C. Then it holds SMMSicf≥SMMSiC≥(1−C)SMMSicf.SMMS^cf_i ^C_i≥(1-C)SMMS^cf_i. Proof. For the first inequality, let k-sharing allocation A be an SMMSiCSMMS^C_i maximizer. Since the cost-free model imposes no cost on sharing, the utility of agent i from allocation A is at least as high in the cost-free model as in the model with costs. Therefore, SMMSicf≥SMMSiCSMMS^cf_i ^C_i. For the second inequality, let full-sharing allocation A be an SMMSicfSMMS^cf_i maximizer. In the model with sharing costs bounded by C, each good contributes at least a (1−C)(1-C) fraction of its value compared to the cost-free model. Since utility is additive, the total utility of agent i in this model is at least (1−C)SMMSicf(1-C)SMMS^cf_i. Hence, SMMSiC≥(1−C)SMMSicfSMMS^C_i≥(1-C)SMMS^cf_i, as claimed. ∎ Appendix E Relationship between SMMS and CMMS Proposition 7. For every instance I=(N,M,u)I=(N,M,u) of the goods-based k-sharing problem, there exists an instance I~=(N,M~,v~,b) I=(N, M, v,b) of a fair allocation under cardinality constraints such that fully-shared allocations A∈knA _k^n correspond bijectively to feasible allocations A~∈ℱ A , and the bijection preserves agents’ utilities: ∀i∈N,ui(A)=v~i(A~i)∀ i∈ N,u_i(A)= v_i( A_i). Proof. Let (N,M,k,v,c)(N,M,k,v,c) be an instance of a cost-free k-sharing problem with M=g1,…gmM=\g_1,… g_m\. Let us now define an instance of fair division problem under cardinality constraints (N,M~,v~,b)(N, M, v,b) satisfying M~=G1,…,Gm M=\G_1,…,G_m\ with Gi=gij∣j∈[k]G_i=\g_i^j j∈[k]\, the unit budget profile b=(1,…,1)b=(1,…,1), and v~i(gxy)=(1−cg(k))vi(gx) v_i(g_x^y)=(1-c_g(k))v_i(g_x) for every x∈[m]x∈[m], y∈[k]y∈[k], i∈Ni∈ N. For every allocation A~∈ℱ A (feasible according to the cardinality constraints), there is an allocation A∈kn(M)A _k^n(M), defined as Ai=gi∣gij∈A~iA_i=\g_i g_i^j∈ A_i\ for every i∈Ni∈ N. For both of these allocations, v~i(A~j)=vi(Aj) v_i( A_j)=v_i(A_j), as v~i(A~j)=∑gxy∈A~jv~i(gxy)=∑gx∈Aj(1−cg(k))vi(gx)=ui(Aj). v_i( A_j)= _g_x^y∈ A_j v_i(g_x^y)= _g_x∈ A_j(1-c_g(k))v_i(g_x)=u_i(A_j). Similarly, for every instance of fair division problem under cardinality constraints (N,M~,b,v~)(N, M,b, v) satisfying M~=C1,…,Cℓ M=\C_1,…,C_ \ with |Ci|=|Cℓ|=k|C_i|=|C_ |=k, b=(1,…,1)b=(1,…,1) and v~i(g1)=v~i(g2) v_i(g_1)= v_i(g_2) for every i∈Ni∈ N, g1,g2∈Cjg_1,g_2∈ C_j, j∈[ℓ]j∈[ ], one can construct an instance of the goods-based k-sharing problem (N,M,k,v,c)(N,M,k,v,c) where goods in M are the sets CiC_i themselves and the utility of vi(Ci)=v~i(g)/(1−cg(k))v_i(C_i)= v_i(g)/(1-c_g(k)) for any g∈Cig∈ C_i. For such a pair of instances, any full-k-sharing allocations (sharing all goods among exactly k agents) correspond to feasible allocations in ℱF with v~i(A~j)=ui(Aj) v_i( A_j)=u_i(A_j) for every A and A~ A. ∎