Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStrategy-proofness, Envy-freeness and Pareto efficiency in Online Fair Division with Additive Utilities
116
0
0.0
(
0
)
Added by
Martin Aleksandrov D
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We consider fair division problems where indivisible items arrive one-by-one in an online fashion and are allocated immediately to agents who have additive utilities over these items. Many existing offline mechanisms do not work in this online setting. In addition, many existing axiomatic results often do not transfer from the offline to the online setting. For this reason, we propose here three new online mechanisms, as well as consider the axiomatic properties of three previously proposed online mechanisms. In this paper, we use these mechanisms and characterize classes of online mechanisms that are strategy-proof, and return envy-free and Pareto efficient allocations, as well as combinations of these properties. Finally, we identify an important impossibility result.
rate research
Read More
We study the fair division of items to agents supposing that agents can form groups. We thus give natural generalizations of popular concepts such as envy-freeness and Pareto efficiency to groups of fixed sizes. Group envy-freeness requires that no group envies another group. Group Pareto efficiency requires that no group can be made better off without another group be made worse off. We study these new group properties from an axiomatic viewpoint. We thus propose new fairness taxonomies that generalize existing taxonomies. We further study ne
We study a new but simple model for online fair division in which indivisible items arrive one-by-one and agents have monotone utilities over bundles of the items. We consider axiomatic properties of mechanisms for this model such as strategy-proofness, envy-freeness, and Pareto efficiency. We prove a number of impossibility results that justify why we consider relaxations of the properties, as well as why we consider restricted preference domains on which good axiomatic properties can be achieved. We propose two mechanisms that have good axiomatic fairness properties on restricted but common preference domains.
Two simple and attractive mechanisms for the fair division of indivisible goods in an online setting are LIKE and BALANCED LIKE. We study some fundamental computational problems concerning the outcomes of these mechanisms. In particular, we consider what expected outcomes are possible, what outcomes are necessary, and how to compute their exact outcomes. In general, we show that such questions are more tractable to compute for LIKE than for BALANCED LIKE. As LIKE is strategy-proof but BALANCED LIKE is not, we also consider the computational problem of how, with BALANCED LIKE, an agent can compute a strategic bid to improve their outcome. We prove that this problem is intractable in general.
Computing market equilibria is a problem of both theoretical and applied interest. Much research focuses on the static case, but in many markets items arrive sequentially and stochastically. We focus on the case of online Fisher markets: individuals have linear, additive utility and items drawn from a distribution arrive one at a time in an online setting. We define the notion of an equilibrium in such a market and provide a dynamics which converges to these equilibria asymptotically. An important use-case of market equilibria is the problem of fair division. With this in mind, we show that our dynamics can also be used as an online item-allocation rule such that the time-averaged allocations and utilities converge to those of a corresponding static Fisher market. This implies that other good properties of market equilibrium-based fair division such as no envy, Pareto optimality, and the proportional share guarantee are also attained in the online setting. An attractive part of the proposed dynamics is that the market designer does not need to know the underlying distribution from which items are drawn. We show that these convergences happen at a rate of $O(tfrac{log t}{t})$ or $O(tfrac{(log t)^2}{t})$ in theory and quickly in real datasets.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
