Achieving Proportionality up to the Maximin Item with Indivisible Goods

• URL: http://arxiv.org/abs/2009.09508v3
• Date: Thu, 14 Jan 2021 17:31:04 GMT
• Title: Achieving Proportionality up to the Maximin Item with Indivisible Goods
• Authors: Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin
• Abstract summary: We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances. We show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations.
• Score: 14.002498730240902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.

Related papers

• Fairness Aware Reinforcement Learning via Proximal Policy Optimization [7.061167083587786]
  This paper introduces fairness in Proximal Policy Optimization (PPO) with a penalty term derived from demographic parity, counterfactual fairness, and conditional statistical parity. We evaluate our approach in the Allelopathic Harvest game, a cooperative and competitive MAS focused on resource collection.
  arXiv  Detail & Related papers  (2025-02-06T10:45:55Z)
• Fairness-Accuracy Trade-Offs: A Causal Perspective [58.06306331390586]
  We analyze the tension between fairness and accuracy from a causal lens for the first time. We show that enforcing a causal constraint often reduces the disparity between demographic groups. We introduce a new neural approach for causally-constrained fair learning.
  arXiv  Detail & Related papers  (2024-05-24T11:19:52Z)
• Proportional Fairness in Clustering: A Social Choice Perspective [14.226371312639145]
  We study the proportional clustering problem of Chen et al. [ICML'19] and relate it to the area of multiwinner voting in computational social choice. We show that any approximation to proportional fairness is also an approximation to individual fairness and vice versa.
  arXiv  Detail & Related papers  (2023-10-27T14:12:56Z)
• Navigating Fairness Measures and Trade-Offs [0.0]
  I show that by using Rawls' notion of justice as fairness, we can create a basis for navigating fairness measures and the accuracy trade-off. This also helps to close part of the gap between philosophical accounts of distributive justice and the fairness literature.
  arXiv  Detail & Related papers  (2023-07-17T13:45:47Z)
• Mimicking Better by Matching the Approximate Action Distribution [48.95048003354255]
  We introduce MAAD, a novel, sample-efficient on-policy algorithm for Imitation Learning from Observations. We show that it requires considerable fewer interactions to achieve expert performance, outperforming current state-of-the-art on-policy methods.
  arXiv  Detail & Related papers  (2023-06-16T12:43:47Z)
• Proportional Fairness in Obnoxious Facility Location [70.64736616610202]
  We propose a hierarchy of distance-based proportional fairness concepts for the problem. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. We prove existence results for two extensions to our model.
  arXiv  Detail & Related papers  (2023-01-11T07:30:35Z)
• Fair Bayes-Optimal Classifiers Under Predictive Parity [33.648053823193855]
  This paper considers predictive parity, which requires equalizing the probability of success given a positive prediction among different protected groups. We propose an algorithm we call FairBayes-DPP, aiming to ensure predictive parity when our condition is satisfied.
  arXiv  Detail & Related papers  (2022-05-15T04:58:10Z)
• Under-Approximating Expected Total Rewards in POMDPs [68.8204255655161]
  We consider the optimal expected total reward to reach a goal state in a partially observable Markov decision process (POMDP) We use mixed-integer linear programming (MILP) to find such minimal probability shifts and experimentally show that our techniques scale quite well.
  arXiv  Detail & Related papers  (2022-01-21T16:43:03Z)
• 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)
• Provably Good Batch Reinforcement Learning Without Great Exploration [51.51462608429621]
  Batch reinforcement learning (RL) is important to apply RL algorithms to many high stakes tasks. Recent algorithms have shown promise but can still be overly optimistic in their expected outcomes. We show that a small modification to Bellman optimality and evaluation back-up to take a more conservative update can have much stronger guarantees.
  arXiv  Detail & Related papers  (2020-07-16T09:25:54Z)
• Opportunistic Multi-aspect Fairness through Personalized Re-ranking [5.8562079474220665]
  We present a re-ranking approach to fairness-aware recommendation that learns individual preferences across multiple fairness dimensions. We show that our opportunistic and metric-agnostic approach achieves a better trade-off between accuracy and fairness than prior re-ranking approaches.
  arXiv  Detail & Related papers  (2020-05-21T04:25:20Z)

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.