On Approximate MMS Allocations on Restricted Graph Classes
Václav Blažej, Michał Dębski, Zbigniew Lonc, Marta Piecyk, Paweł Rzążewski · 2025
Read On Approximate MMS Allocations on Restricted Graph Classes by Václav Blažej, Michał Dębski, Zbigniew Lonc, Marta Piecyk, Paweł Rzążewski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-06343.txt.
Introduction
Blažej and co-authors study fair division of indivisible goods in a mathematics paper from two thousand twenty-five. The goods sit on a graph, and each person's bundle must form a connected piece of it. Fairness is judged by the maximin share, the best a person can guarantee by splitting the goods themselves.
A perfectly fair split may not exist, so the team looks for near-fair ones that give each person a fixed fraction of that share. Such splits are known for some graph types but not for all graphs. The authors prove they exist for several more classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
Catalog record
| CREATOR | Václav Blažej, Michał Dębski, Zbigniew Lonc, Marta Piecyk, Paweł Rzążewski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-06343
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Approximate MMS Allocations on Restricted Graph Classes Václav Blažej, Michał Dębski, Zbigniew Lonc, Marta Piecyk, Paweł Rzążewski Abstract We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and d d -claw-free graphs for any fixed d d , such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs. † † paperid: 123 1 Introduction Fair division of goods is a fundamental problem in social choice theory, computer science, and economics. The objective is to allocate goods to agents in a way that satisfies a specified fairness criterion. The study of this problem dates back to the seminal work of Steinhaus [ Steinhaus(1948) ] . Extensive research has been conducted on the fair division of divisible goods (Brams and Taylor [ Brams and Taylor(1996) ] , Procaccia [ Procaccia(2016) ] ). In this case, the problem is known as the cake-cutting problem . Another variant of the problem, that we deal with in this paper, is fair division of a set of indivisible goods. In this case, the problem involves a set of items and a set of agents, each with her own utility function for the goods, which assigns some values to all subsets of goods, called bundles. It is commonly assumed, as we do in this paper, that utility functions are additive, i.e., the value of each bundle is equal to the sum of the values of the individual items in this bundle. It has been shown that for divisible goods, allocations satisfying natural criteria such as envy-freeness or proportionality always exist (Brams and Taylor [ Brams and Taylor(1996) ] ). However, when the goods are indivisible, it is easy to give examples where no allocation satisfies these criteria. Therefore, there is a need to define fairness criteria that are more realistic and achievable when allocating indivisible goods. In recent years, one of the most extensively studied fairness criteria for the allocation of indivisible goods has been the maximin share criterion, introduced by Budish [ Budish(2011) ] . The maximin share of an agent is the maximum value the agent can ensure to obtain by dividing the set of goods into n parts, where n is the number of agents, and receiving a part with the minimum value. An allocation satisfies the maximin share criterion if every agent receives a set of goods of value at least equal to her maximin share. Such allocations are referred to as maximin allocations , or simply mms-allocations . For several years it has been an open problem whether mms-allocations always exist. This question was answered in the negative (Procaccia and Wang [ Procaccia and Wang(2014) ] , Feige et al. [ Feige et al.(2022)Feige, Sapir, and Tauber ] ), even for as few as three agents. In light of this, it is natural to look for approximate mms-allocations , which guarantee that each agent receives a bundle of value at least some positive fraction of her maximin share. Procaccia and Wang [ Procaccia and Wang(2014) ] proved the existence of an allocation ensuring every agent a bundle of value at least \frac{2}{3} of her maximin share. This approximation ratio has since been improved in several subsequent papers (Amanatidis et al. [ Amanatidis et al.(2017)Amanatidis, Markakis, Nikzad, and Saberi ] , Barman and Krishnamurthy [ Barman and Krishnamurthy(2020) ] , Garg et al. [ Garg et al.(2019)Garg, McGlaughlin, and Taki ] , Ghodsi et al., [ Ghodsi et al.(2018)Ghodsi, Hajiaghayi, Seddighin, Seddighin, and Yami ] , Garg and Taki [ Garg and Taki(2021) ] , Akrami et al. [ Akrami et al.(2023)Akrami, Garg, Sharma, and Taki ] ). The best known result of this kind is given by the following recent theorem. Theorem 1 (Akrami and Garg [ Akrami and Garg(2024) ] ) . For any set of goods and any set of agents, there always exists an allocation in which each agent gets at least \frac{3}{4}+\frac{3}{3836} of her maximin share. In this paper, we study the problem of mms-allocations under some connectivity constraints imposed on the set of goods. We follow the framework proposed by Bouveret et al. [ Bouveret et al.(2017)Bouveret, Cechlárová, Elkind, Igarashi, and Peters ] . In this framework, the items to be distributed among agents are represented as vertices of a connected graph, referred to as the graph of goods . An allocation satisfies a fairness criterion if the values of the bundles received by agents are not only of sufficiently high value to them but also induce connected subgraphs in the graph of goods. This model captures a variety of applications. One of them is the problem of consolidating land plots (King and Burton [ King and Burton(1982) ] ). In this scenario, highly fragmented plots need to be reallocated to farmers in such a way that the new plots they receive are close one to another. Other examples include the allocation of rooms in a building to research groups (Bouveret et al., [ Bouveret et al.(2017)Bouveret, Cechlárová, Elkind, Igarashi, and Peters ] ) or the distribution of airline connections among carriers (Lonc [ Lonc(2023) ] ). The original problem of fair allocation of indivisible goods becomes a special case in this framework when the graph of goods is complete. The problem of the existence of mms-allocations and approximate mms-allocations has been investigated for several classes of graphs. Bouveret et al. [ Bouveret et al.(2017)Bouveret, Cechlárová, Elkind, Igarashi, and Peters ] proved that mms-allocations always exist when the graph of goods is a tree. Moreover, they provided an example demonstrating that if the graph of goods is a cycle, then for certain utility functions of the agents, an mms-allocation may not exist. Lonc and Truszczynski [ Lonc and Truszczynski(2020) ] thoroughly studied the case where the graph of goods is a cycle. They proved that in this case, for any set of agents, an allocation guaranteeing the agents bundles of value at least \frac{\sqrt{5}-1}{2}\approx 0.62 of their maximin shares always exists. Lonc [ Lonc(2023) ] considered the case where the graph of goods is d -claw-free, i.e., it does not contain a star with d edges as an induced subgraph. He proved that for d\geq 3 , if the graph of goods is d -claw-free, then there