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
- 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) - Robust and Performance Incentivizing Algorithms for Multi-Armed Bandits
with Strategic Agents [57.627352949446625]
We consider a variant of the multi-armed bandit problem.
Specifically, the arms are strategic agents who can improve their rewards or absorb them.
We identify a class of MAB algorithms which satisfy a collection of properties and show that they lead to mechanisms that incentivize top level performance at equilibrium.
arXiv Detail & Related papers (2023-12-13T06:54:49Z) - 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) - On the Complexity of Multi-Agent Decision Making: From Learning in Games
to Partial Monitoring [105.13668993076801]
A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees.
We study this question in a general framework for interactive decision making with multiple agents.
We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
arXiv Detail & Related papers (2023-05-01T06:46:22Z) - Bandit Social Learning: Exploration under Myopic Behavior [58.75758600464338]
We study social learning dynamics motivated by reviews on online platforms.
Agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration.
We derive stark learning failures for any such behavior, and provide matching positive results.
arXiv Detail & Related papers (2023-02-15T01:57:57Z) - 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.