Jealousy-freeness and other common properties in Fair Division of Mixed Manna

• URL: http://arxiv.org/abs/2004.11469v3
• Date: Tue, 12 May 2020 19:18:02 GMT
• Title: Jealousy-freeness and other common properties in Fair Division of Mixed Manna
• Authors: Martin Aleksandrov
• Abstract summary: We consider a fair division setting where indivisible items are allocated to agents. We make a distinction between items that are good for some agents and bad for others.
• Score: 2.28438857884398
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a fair division setting where indivisible items are allocated to agents. Each agent in the setting has strictly negative, zero or strictly positive utility for each item. We, thus, make a distinction between items that are good for some agents and bad for other agents (i.e. mixed), good for everyone (i.e. goods) or bad for everyone (i.e. bads). For this model, we study axiomatic concepts of allocations such as jealousy-freeness up to one item, envy-freeness up to one item and Pareto-optimality. We obtain many new possibility and impossibility results in regard to combinations of these properties. We also investigate new computational tasks related to such combinations. Thus, we advance the state-of-the-art in fair division of mixed manna.

Related papers

• Temporal Fair Division of Indivisible Items [61.235172150247614]
  We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. We aim to ensure that the cumulative allocation at each round satisfies approximate temporal envy-freeness up to one item (TEF1)
  arXiv  Detail & Related papers  (2024-10-18T16:43:36Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  We study EgalMAB, an egalitarian assignment problem in the context of multi-armed bandits. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret.
  arXiv  Detail & Related papers  (2024-10-08T09:49:47Z)
• Honor Among Bandits: No-Regret Learning for Online Fair Division [20.38824614301761]
  We consider the problem of online fair division of indivisible goods to players when there are a finite number of types of goods and player values are drawn from distributions with unknown means. Our main result is the design of an explore-then-commit algorithm that achieves $tildeO(T2/3)$ regret while maintaining either fairness constraint.
  arXiv  Detail & Related papers  (2024-07-01T20:44:52Z)
• Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
  We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
  arXiv  Detail & Related papers  (2024-05-31T19:26:05Z)
• Ranking a Set of Objects using Heterogeneous Workers: QUITE an Easy Problem [54.90613714264689]
  We focus on the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of unequal workers. We propose QUITE, a non-adaptive ranking algorithm that jointly estimates workers' reliabilities and qualities of objects.
  arXiv  Detail & Related papers  (2023-10-03T12:42:13Z)
• Reforming an Envy-Free Matching [3.615389896666528]
  We consider the problem of reforming an envy-free matching when each agent is assigned a single item. We consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching.
  arXiv  Detail & Related papers  (2022-07-06T13:03:49Z)
• Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking [36.42838320396534]
  We argue that any particular choice of such a link function may be difficult to defend. This not only avoids the need to choose a link function, but also more meaningfully quantifies the impact on the items beyond exposure.
  arXiv  Detail & Related papers  (2022-06-15T02:20:30Z)
• (Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna [10.933894827834825]
  We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality.
  arXiv  Detail & Related papers  (2022-02-06T01:29:50Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning [59.62721526353915]
  Multi-agent settings in the real world often involve tasks with varying types and quantities of agents and non-agent entities. Our method aims to leverage these commonalities by asking the question: What is the expected utility of each agent when only considering a randomly selected sub-group of its observed entities?''
  arXiv  Detail & Related papers  (2020-06-07T18:28:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.