Zobrazeno 1 - 10
of 291
pro vyhledávání: '"Suksompong, Warut"'
We study the allocation of indivisible goods that form an undirected graph and investigate the worst-case welfare loss when requiring that each agent must receive a connected subgraph. Our focus is on both egalitarian and utilitarian welfare. Specifi
Externí odkaz:
http://arxiv.org/abs/2405.03467
We study the complexity of a fundamental algorithm for fairly allocating indivisible items, the round-robin algorithm. For $n$ agents and $m$ items, we show that the algorithm can be implemented in time $O(nm\log(m/n))$ in the worst case. If the agen
Externí odkaz:
http://arxiv.org/abs/2404.19402
Autor:
Manurangsi, Pasin, Suksompong, Warut
We investigate fairness in the allocation of indivisible items among groups of agents using the notion of maximin share (MMS). While previous work has shown that no nontrivial multiplicative MMS approximation can be guaranteed in this setting for gen
Externí odkaz:
http://arxiv.org/abs/2404.11543
Publikováno v:
Operations Research Letters, 54:107103 (2024)
House allocation refers to the problem where $m$ houses are to be allocated to $n$ agents so that each agent receives one house. Since an envy-free house allocation does not always exist, we consider finding such an allocation in the presence of subs
Externí odkaz:
http://arxiv.org/abs/2403.01162
We study the problem of aggregating distributions, such as budget proposals, into a collective distribution. An ideal aggregation mechanism would be Pareto efficient, strategyproof, and fair. Most previous work assumes that agents evaluate budgets ac
Externí odkaz:
http://arxiv.org/abs/2402.15904
In the allocation of indivisible goods, a prominent fairness notion is envy-freeness up to one good (EF1). We initiate the study of reachability problems in fair division by investigating the problem of whether one EF1 allocation can be reached from
Externí odkaz:
http://arxiv.org/abs/2312.07241
We study a portioning setting in which a public resource such as time or money is to be divided among a given set of candidates, and each agent proposes a division of the resource. We consider two families of aggregation rules for this setting -- tho
Externí odkaz:
http://arxiv.org/abs/2307.15586
Charity is typically carried out by individual donors, who donate money to charities they support, or by centralized organizations such as governments or municipalities, which collect individual contributions and distribute them among a set of charit
Externí odkaz:
http://arxiv.org/abs/2305.10286
Autor:
Yuen, Sheung Man, Suksompong, Warut
Publikováno v:
Discrete Applied Mathematics, 357:112-131 (2024)
We study the problem of fairly allocating a divisible resource in the form of a graph, also known as graphical cake cutting. Unlike for the canonical interval cake, a connected envy-free allocation is not guaranteed to exist for a graphical cake. We
Externí odkaz:
http://arxiv.org/abs/2304.11659
Autor:
Suksompong, Warut, Teh, Nicholas
Publikováno v:
Mathematical Social Sciences, 126:48-59 (2023)
We study the problem of fairly allocating indivisible goods to agents with weights corresponding to their entitlements. Previous work has shown that, when agents have binary additive valuations, the maximum weighted Nash welfare rule is resource-, po
Externí odkaz:
http://arxiv.org/abs/2303.14454