Finding Fair and Efficient Allocations When Valuations Don't Add Up

• URL: http://arxiv.org/abs/2003.07060v4
• Date: Fri, 18 Jun 2021 05:21:10 GMT
• Title: Finding Fair and Efficient Allocations When Valuations Don't Add Up
• Authors: Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, Yair Zick
• Abstract summary: We show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) achieves allocation that envy-freeness up to one item (EF1) exists and is computationally tractable. This is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1.
• Score: 25.962505544590947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to {\em matroid rank functions}. This is a versatile valuation class with several desirable properties (such as monotonicity and submodularity), which naturally lends itself to a number of real-world domains. We use these properties to our advantage; first, we show that when agent valuations are matroid rank functions, a socially optimal (i.e. utilitarian social welfare-maximizing) allocation that achieves envy-freeness up to one item (EF1) exists and is computationally tractable. We also prove that the Nash welfare-maximizing and the leximin allocations both exhibit this fairness/efficiency combination, by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. To the best of our knowledge, this is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1. Moreover, for a subclass of these valuation functions based on maximum (unweighted) bipartite matching, we show that a leximin allocation can be computed in polynomial time. Additionally, we explore possible extensions of our results to fairness criteria other than EF1 as well as to generalizations of the above valuation classes.

Related papers

• Statistical Inference of Optimal Allocations I: Regularities and their Implications [3.904240476752459]
  We first derive Hadamard differentiability of the value function through a detailed analysis of the general properties of the sorting operator. Building on our Hadamard differentiability results, we demonstrate how the functional delta method can be used to directly derive the properties of the value function process.
  arXiv  Detail & Related papers  (2024-03-27T04:39:13Z)
• Explainable Disparity Compensation for Efficient Fair Ranking [0.3759936323189418]
  Ranking functions that are used in decision systems often produce disparate results for different populations because of bias in the underlying data. Recent compensatory measures have mostly focused on opaque transformations of the ranking functions to satisfy fairness guarantees. In this paper we propose easily explainable data-driven compensatory measures for ranking functions.
  arXiv  Detail & Related papers  (2023-07-25T09:12:50Z)
• Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations [20.774185319381985]
  We study the problem of fairly allocating a set of indivisible goods among agents with bivalued submodular valuations. We show that neither the leximin nor the MNW allocation is guaranteed to be envy free up to one good.
  arXiv  Detail & Related papers  (2023-02-06T19:41:28Z)
• Approximating the Shapley Value without Marginal Contributions [11.539320505465149]
  The Shapley value, which is arguably the most popular approach for assigning a meaningful contribution value to players in a cooperative game, has recently been used intensively in explainable artificial intelligence. We propose two parameter-free and domain-independent approximation algorithms based on a representation of the Shapley value detached from the notion of marginal contribution.
  arXiv  Detail & Related papers  (2023-02-01T20:14:22Z)
• RankFeat: Rank-1 Feature Removal for Out-of-distribution Detection [65.67315418971688]
  textttRankFeat is a simple yet effective textttpost hoc approach for OOD detection. textttRankFeat achieves the emphstate-of-the-art performance and reduces the average false positive rate (FPR95) by 17.90% compared with the previous best method.
  arXiv  Detail & Related papers  (2022-09-18T16:01:31Z)
• Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasets [101.5329678997916]
  We study episodic two-player zero-sum Markov games (MGs) in the offline setting. The goal is to find an approximate Nash equilibrium (NE) policy pair based on a dataset collected a priori.
  arXiv  Detail & Related papers  (2022-02-15T15:39:30Z)
• Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness [16.187873844872637]
  We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance. We show that the corresponding allocations not only are EFX but also satisfy maximin share fairness, something that is not true for this algorithm in the non-strategic setting!
  arXiv  Detail & Related papers  (2021-09-17T16:57:20Z)
• Scalable Personalised Item Ranking through Parametric Density Estimation [53.44830012414444]
  Learning from implicit feedback is challenging because of the difficult nature of the one-class problem. Most conventional methods use a pairwise ranking approach and negative samplers to cope with the one-class problem. We propose a learning-to-rank approach, which achieves convergence speed comparable to the pointwise counterpart.
  arXiv  Detail & Related papers  (2021-05-11T03:38:16Z)
• Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency [83.02999769628593]
  We offer a theoretical characterization of off-policy evaluation (OPE) in reinforcement learning. We show that the minimax approach enables us to achieve a fast rate of convergence for weights and quality functions. We present the first finite-sample result with first-order efficiency in non-tabular environments.
  arXiv  Detail & Related papers  (2021-02-05T03:20:39Z)
• Are we Forgetting about Compositional Optimisers in Bayesian Optimisation? [66.39551991177542]
  This paper presents a sample methodology for global optimisation. Within this, a crucial performance-determiningtrivial is maximising the acquisition function. We highlight the empirical advantages of the approach to optimise functionation across 3958 individual experiments.
  arXiv  Detail & Related papers  (2020-12-15T12:18:38Z)
• Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration [143.43658264904863]
  We show how iteration under a more standard notion of low inherent Bellman error, typically employed in least-square value-style algorithms, can provide strong PAC guarantees on learning a near optimal value function. We present a computationally tractable algorithm for the reward-free setting and show how it can be used to learn a near optimal policy for any (linear) reward function.
  arXiv  Detail & Related papers  (2020-08-18T04:34:21Z)

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.