PROPm Allocations of Indivisible Goods to Multiple Agents

• URL: http://arxiv.org/abs/2105.11348v1
• Date: Mon, 24 May 2021 15:34:33 GMT
• Title: PROPm Allocations of Indivisible Goods to Multiple Agents
• Authors: Artem Baklanov, Pranav Garimidi, Vasilis Gkatzelis, Daniel Schoepflin
• Abstract summary: We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. We show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods.
• Score: 3.361550072563245
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the classic problem of fairly allocating a set of indivisible goods among a group of agents, and focus on the notion of approximate proportionality known as PROPm. Prior work showed that there exists an allocation that satisfies this notion of fairness for instances involving up to five agents, but fell short of proving that this is true in general. We extend this result to show that a PROPm allocation is guaranteed to exist for all instances, independent of the number of agents or goods. Our proof is constructive, providing an algorithm that computes such an allocation and, unlike prior work, the running time of this algorithm is polynomial in both the number of agents and the number of goods.

Related papers

• Temporal Fair Division of Indivisible Items [61.235172150247614]
  We study a fair division model where indivisible items arrive sequentially, and must be allocated immediately and irrevocably. Previous work on online fair division has shown impossibility results in achieving approximate envy-freeness under these constraints. We aim to ensure that the cumulative allocation at each round satisfies approximate temporal envy-freeness up to one item (TEF1)
  arXiv  Detail & Related papers  (2024-10-18T16:43:36Z)
• Online Fair Division with Contextual Bandits [41.57721032039409]
  This paper considers a novel online fair division problem involving multiple agents in which a learner observes an indivisible item. Existing algorithms assume a small number of items with a sufficiently large number of copies, which ensures a good utility estimation for all item-agent pairs. We then propose algorithms for online fair division with sub-linear regret guarantees.
  arXiv  Detail & Related papers  (2024-08-23T05:25:58Z)
• Are Bounded Contracts Learnable and Approximately Optimal? [8.121834515103243]
  This paper considers the hidden-action model of the principal-agent problem, in which a principal incentivizes an agent to work on a project using a contract. We investigate whether contracts with bounded payments are learnable and approximately optimal.
  arXiv  Detail & Related papers  (2024-02-22T12:19:19Z)
• Replication-proof Bandit Mechanism Design with Bayesian Agents [11.758708370032469]
  We study the problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms. We consider Bayesian agents who only know the distribution from which their own arms' mean rewards are sampled, unlike the original setting of by Shin et al. 2022.
  arXiv  Detail & Related papers  (2023-12-28T08:36:35Z)
• Approximate Linear Programming for Decentralized Policy Iteration in Cooperative Multi-agent Markov Decision Processes [5.842054972839244]
  We consider a cooperative multi-agent Markov decision process involving m agents. In the policy iteration process of multi-agent setup, the number of actions grows exponentially with the number of agents. We propose approximate decentralized policy iteration algorithms using approximate linear programming with function approximation.
  arXiv  Detail & Related papers  (2023-11-20T14:14:13Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Robust Allocations with Diversity Constraints [65.3799850959513]
  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.
  arXiv  Detail & Related papers  (2021-09-30T11:09:31Z)
• Multi-agent Policy Optimization with Approximatively Synchronous Advantage Estimation [55.96893934962757]
  In multi-agent system, polices of different agents need to be evaluated jointly. In current methods, value functions or advantage functions use counter-factual joint actions which are evaluated asynchronously. In this work, we propose the approximatively synchronous advantage estimation.
  arXiv  Detail & Related papers  (2020-12-07T07:29:19Z)
• Achieving Proportionality up to the Maximin Item with Indivisible Goods [14.002498730240902]
  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.
  arXiv  Detail & Related papers  (2020-09-20T19:21:19Z)
• 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)
• Scalable Multi-Agent Inverse Reinforcement Learning via Actor-Attention-Critic [54.2180984002807]
  Multi-agent adversarial inverse reinforcement learning (MA-AIRL) is a recent approach that applies single-agent AIRL to multi-agent problems. We propose a multi-agent inverse RL algorithm that is more sample-efficient and scalable than previous works.
  arXiv  Detail & Related papers  (2020-02-24T20:30:45Z)

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.