Robust Allocations with Diversity Constraints

• URL: http://arxiv.org/abs/2109.15015v1
• Date: Thu, 30 Sep 2021 11:09:31 GMT
• Title: Robust Allocations with Diversity Constraints
• Authors: Zeyu Shen and Lodewijk Gelauff and Ashish Goel and Aleksandra Korolova and Kamesh Munagala
• Abstract summary: We show that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules.
• Score: 65.3799850959513
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce diversity constraints on the items they are allocated. We motivate this via settings where the items themselves correspond to user ad slots or task workers with attributes such as race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into an allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing robustness. These are no negative externality -- other agents are not hurt -- and monotonicity -- the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is uniquely positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules. We finally perform an empirical simulation on real-world data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.

Related papers

• Using Protected Attributes to Consider Fairness in Multi-Agent Systems [7.061167083587786]
  Fairness in Multi-Agent Systems (MAS) depends on various factors, including the system's governing rules, the behaviour of the agents, and their characteristics. We take inspiration from the work on algorithmic fairness, which addresses bias in machine learning-based decision-making. We adapt fairness metrics from the algorithmic fairness literature to the multi-agent setting, where self-interested agents interact within an environment.
  arXiv  Detail & Related papers  (2024-10-16T08:12:01Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  We study EgalMAB, an egalitarian assignment problem in the context of multi-armed bandits. We design and analyze a UCB-based policy EgalUCB and establish upper bounds on the cumulative regret.
  arXiv  Detail & Related papers  (2024-10-08T09:49:47Z)
• Tackling Ambiguity from Perspective of Uncertainty Inference and Affinity Diversification for Weakly Supervised Semantic Segmentation [12.308473939796945]
  Weakly supervised semantic segmentation (WSSS) with image-level labels aims to achieve dense tasks without laborious annotations. The performance of WSSS, especially the stages of generating Class Activation Maps (CAMs) and refining pseudo masks, widely suffers from ambiguity. We propose UniA, a unified single-staged WSSS framework, to tackle this issue from the perspective of uncertainty inference and affinity diversification.
  arXiv  Detail & Related papers  (2024-04-12T01:54:59Z)
• Byzantine-Resilient Decentralized Multi-Armed Bandits [25.499420566469098]
  We develop an algorithm that fuses an information mixing step among agents with a truncation of inconsistent and extreme values. This framework can be used to model attackers in computer networks, instigators of offensive content into recommender systems, or manipulators of financial markets.
  arXiv  Detail & Related papers  (2023-10-11T09:09:50Z)
• Hierarchical Imitation Learning for Stochastic Environments [31.64016324441371]
  Existing methods that improve distributional realism typically rely on hierarchical policies. We propose Robust Type Conditioning (RTC), which eliminates the shift with adversarial training under environmentality. Experiments on two domains, including the large-scale Open Motion dataset, show improved distributional realism while maintaining or improving task performance compared to state-of-the-art baselines.
  arXiv  Detail & Related papers  (2023-09-25T10:10:34Z)
• Counterfactual Conservative Q Learning for Offline Multi-agent Reinforcement Learning [54.788422270960496]
  We propose a novel multi-agent offline RL algorithm, named CounterFactual Conservative Q-Learning (CFCQL) CFCQL calculates conservative regularization for each agent separately in a counterfactual way and then linearly combines them to realize an overall conservative value estimation. We prove that it still enjoys the underestimation property and the performance guarantee as those single agent conservative methods do, but the induced regularization and safe policy improvement bound are independent of the agent number.
  arXiv  Detail & Related papers  (2023-09-22T08:10:25Z)
• ERMAS: Becoming Robust to Reward Function Sim-to-Real Gaps in Multi-Agent Simulations [110.72725220033983]
  Epsilon-Robust Multi-Agent Simulation (ERMAS) is a framework for learning AI policies that are robust to such multiagent sim-to-real gaps. ERMAS learns tax policies that are robust to changes in agent risk aversion, improving social welfare by up to 15% in complextemporal simulations. In particular, ERMAS learns tax policies that are robust to changes in agent risk aversion, improving social welfare by up to 15% in complextemporal simulations.
  arXiv  Detail & Related papers  (2021-06-10T04:32:20Z)
• Diverse Rule Sets [20.170305081348328]
  Rule-based systems are experiencing a renaissance owing to their intuitive if-then representation. We propose a novel approach of inferring diverse rule sets, by optimizing small overlap among decision rules. We then devise an efficient randomized algorithm, which samples rules that are highly discriminative and have small overlap.
  arXiv  Detail & Related papers  (2020-06-17T14:15:25Z)
• Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning [59.62721526353915]
  Multi-agent settings in the real world often involve tasks with varying types and quantities of agents and non-agent entities. Our method aims to leverage these commonalities by asking the question: What is the expected utility of each agent when only considering a randomly selected sub-group of its observed entities?''
  arXiv  Detail & Related papers  (2020-06-07T18:28:41Z)
• 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.