Reforming an Envy-Free Matching

• URL: http://arxiv.org/abs/2207.02641v1
• Date: Wed, 6 Jul 2022 13:03:49 GMT
• Title: Reforming an Envy-Free Matching
• Authors: Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
• Abstract summary: We consider the problem of reforming an envy-free matching when each agent is assigned a single item. We consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching.
• Score: 3.615389896666528
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of reforming an envy-free matching when each agent is assigned a single item. Given an envy-free matching, we consider an operation to exchange the item of an agent with an unassigned item preferred by the agent that results in another envy-free matching. We repeat this operation as long as we can. We prove that the resulting envy-free matching is uniquely determined up to the choice of an initial envy-free matching, and can be found in polynomial time. We call the resulting matching a reformist envy-free matching, and then we study a shortest sequence to obtain the reformist envy-free matching from an initial envy-free matching. We prove that a shortest sequence is computationally hard to obtain even when each agent accepts at most four items and each item is accepted by at most three agents. On the other hand, we give polynomial-time algorithms when each agent accepts at most three items or each item is accepted by at most two agents. Inapproximability and fixed-parameter (in)tractability are also discussed.

Related papers

• 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)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  Multi-armed bandits are a sequential-decision-making framework, where, at each interaction step, the learner selects an arm and observes a reward. We consider the scenario in which the learner has access to a set of mediators, each of which selects the arms on the agent's behalf according to a and possibly unknown policy. We propose a sequential decision-making strategy for discovering the best arm under the assumption that the mediators' policies are known to the learner.
  arXiv  Detail & Related papers  (2023-08-29T18:18:21Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Doubly Adversarial Federated Bandits [7.23389716633927]
  We study a new non-stochastic federated multi-armed bandit problem with multiple agents collaborating via a communication network. Our algorithm gives a positive answer to an open question proposed in Cesa-Bianchi et al.
  arXiv  Detail & Related papers  (2023-01-22T22:36:43Z)
• Thou Shalt not Pick all Items if Thou are First: of Strategyproof and Fair Picking Sequences [7.2834950390171205]
  We study how to balance priority in the sequence and number of items received. For several meaningful choices of parameters, we show that the optimal sequence can be computed in a simple way.
  arXiv  Detail & Related papers  (2023-01-11T13:04:51Z)
• The Dichotomous Affiliate Stable Matching Problem: Approval-Based Matching with Applicant-Employer Relations [27.388757379210034]
  We introduce the Dichotomous Affiliate Stable Matching (DASM) Problem, where agents' preferences indicate dichotomous acceptance or rejection of another agent in the marketplace. Our results are threefold: (1) we use a human study to show that real-world matching rankings follow our assumed valuation function; (2) we prove that there always exists a stable solution by providing an efficient, easily-implementable algorithm that finds such a solution; and (3) we experimentally validate the efficiency of our algorithm versus a linear-programming-based approach.
  arXiv  Detail & Related papers  (2022-02-22T18:56:21Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• On the Expressivity of Markov Reward [89.96685777114456]
  This paper is dedicated to understanding the expressivity of reward as a way to capture tasks that we would want an agent to perform. We frame this study around three new abstract notions of "task" that might be desirable: (1) a set of acceptable behaviors, (2) a partial ordering over behaviors, or (3) a partial ordering over trajectories.
  arXiv  Detail & Related papers  (2021-11-01T12:12:16Z)
• 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)
• Jealousy-freeness and other common properties in Fair Division of Mixed Manna [2.28438857884398]
  We consider a fair division setting where indivisible items are allocated to agents. We make a distinction between items that are good for some agents and bad for others.
  arXiv  Detail & Related papers  (2020-04-23T21:39:12Z)
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
  The Combinatorial Multi-Armed Bandit problem is a sequential decision-making problem in which an agent selects a set of arms on each round. We show that the recently proposed Gini-weighted smoothness parameter determines the lower bounds for monotone reward functions.
  arXiv  Detail & Related papers  (2020-02-13T08:53:43Z)

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.