Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEquitable Division of a Path
63
0
0.0
(
0
)
Added by
Chinmay Sonar
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study fair resource allocation under a connectedness constraint wherein a set of indivisible items are arranged on a path and only connected subsets of items may be allocated to the agents. An allocation is deemed fair if it satisfies equitability up to one good (EQ1), which requires that agents utilities are approximately equal. We show that achieving EQ1 in conjunction with well-studied measures of economic efficiency (such as Pareto optimality, non-wastefulness, maximum egalitarian or utilitarian welfare) is computationally hard even for binary additive valuations. On the algorithmic side, we show that by relaxing the efficiency requirement, a connected EQ1 allocation can be computed in polynomial time for any given ordering of agents, even for general monotone valuations. Interestingly, the allocation computed by our algorithm has the highest egalitarian welfare among all allocations consistent with the given ordering. On the other hand, if efficiency is required, then tractability can still be achieved for binary additive valuations with interval structure. On our way, we strengthen some of the existing results in the literature for other fairness notions such as envy-freeness up to one good (EF1), and also provide novel results for negatively-valued items or chores.
rate research
Read More
Behavioural economists have shown that people are often averse to inequality and will make choices to avoid unequal outcomes. In this paper, we consider how to allocate indivisible goods fairly so as to minimize inequality. We consider how this interacts with axiomatic properties such as envy-freeness, Pareto efficiency and strategy-proofness. We also consider the computational complexity of computing allocations minimizing inequality. Unfortunately, this is computationally intractable in general so we consider several tractable greedy online mechanisms that minimize inequality. Finally, we run experiments to explore the performance of these methods.
We consider the problem of fairly allocating indivisible goods, among agents, under cardinality constraints and additive valuations. In this setting, we are given a partition of the entire set of goods---i.e., the goods are categorized---and a limit is specified on the number of goods that can be allocated from each category to any agent. The objective here is to find a fair allocation in which the subset of goods assigned to any agent satisfies the given cardinality constraints. This problem naturally captures a number of resource-allocation applications, and is a generalization of the well-studied (unconstrained) fair division problem. The two central notions of fairness, in the context of fair division of indivisible goods, are envy freeness up to one good (EF1) and the (approximate) maximin share guarantee (MMS). We show that the existence and algorithmic guarantees established for these solution concepts in the unconstrained setting can essentially be achieved under cardinality constraints. Specifically, we develop efficient algorithms which compute EF1 and approximately MMS allocations in the constrained setting. Furthermore, focusing on the case wherein all the agents have the same additive valuation, we establish that EF1 allocations exist and can be computed efficiently even under laminar matroid constraints.
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.
We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely crucially on the free disposal assumption, meaning that the mechanism is allowed to throw away part of the resource at no cost. In the present work, we remove this assumption and focus on mechanisms that always allocate the entire resource. We exhibit a truthful and envy-free mechanism for cake cutting and chore division for two agents with piecewise uniform valuations, and we complement our result by showing that such a mechanism does not exist when certain additional constraints are imposed on the mechanisms. Moreover, we provide bounds on the efficiency of mechanisms satisfying various properties, and give truthful mechanisms for multiple agents with restricted classes of valuations.
This paper is part of an ongoing endeavor to bring the theory of fair division closer to practice by handling requirements from real-life applications. We focus on two requirements originating from the division of land estates: (1) each agent should receive a plot of a usable geometric shape, and (2) plots of different agents must be physically separated. With these requirements, the classic fairness notion of proportionality is impractical, since it may be impossible to attain any multiplicative approximation of it. In contrast, the ordinal maximin share approximation, introduced by Budish in 2011, provides meaningful fairness guarantees. We prove upper and lower bounds on achievable maximin share guarantees when the usable shapes are squares, fat rectangles, or arbitrary axes-aligned rectangles, and explore the algorithmic and query complexity of finding fair partitions in this setting.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
