The Leximin Approach for a Sequence of Collective Decisions

• URL: http://arxiv.org/abs/2305.18024v1
• Date: Mon, 29 May 2023 11:28:27 GMT
• Title: The Leximin Approach for a Sequence of Collective Decisions
• Authors: Ido Kahana and Noam Hazon
• Abstract summary: We analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. In the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations.
• Score: 6.3734441349747035
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: In many situations, several agents need to make a sequence of decisions. For example, a group of workers that needs to decide where their weekly meeting should take place. In such situations, a decision-making mechanism must consider fairness notions. In this paper, we analyze the fairness of three known mechanisms: round-robin, maximum Nash welfare, and leximin. We consider both offline and online settings, and concentrate on the fairness notion of proportionality and its relaxations. Specifically, in the offline setting, we show that the three mechanisms fail to find a proportional or approximate-proportional outcome, even if such an outcome exists. We thus introduce a new fairness property that captures this requirement, and show that a variant of the leximin mechanism satisfies the new fairness property. In the online setting, we show that it is impossible to guarantee proportionality or its relaxations. We thus consider a natural restriction on the agents' preferences, and show that the leximin mechanism guarantees the best possible additive approximation to proportionality and satisfies all the relaxations of proportionality.

Related papers

• Social Choice for Heterogeneous Fairness in Recommendation [9.753088666705985]
  Algorithmic fairness in recommender systems requires close attention to the needs of a diverse set of stakeholders. Previous work has often been limited by fixed, single-objective definitions of fairness. Our work approaches recommendation fairness from the standpoint of computational social choice.
  arXiv  Detail & Related papers  (2024-10-06T17:01:18Z)
• 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)
• Causal Fairness for Outcome Control [68.12191782657437]
  We study a specific decision-making task called outcome control in which an automated system aims to optimize an outcome variable $Y$ while being fair and equitable. In this paper, we first analyze through causal lenses the notion of benefit, which captures how much a specific individual would benefit from a positive decision. We then note that the benefit itself may be influenced by the protected attribute, and propose causal tools which can be used to analyze this.
  arXiv  Detail & Related papers  (2023-06-08T09:31:18Z)
• 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)
• Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism [103.36492220921109]
  We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank which satisfies Strong Proportionality in expectation. Our main characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation.
  arXiv  Detail & Related papers  (2022-05-30T00:51:57Z)
• Strategyproof and Proportionally Fair Facility Location [77.16035689756859]
  We focus on a simple, one-dimensional collective decision problem (often referred to as the facility location problem) We analyze a hierarchy of proportionality-based fairness axioms of varying strength. For each axiom, we characterize the family of mechanisms that satisfy the axiom and strategyproofness.
  arXiv  Detail & Related papers  (2021-11-02T12:41:32Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)

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.