On Reachable Assignments Under Dichotomous Preferences

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider the problem of determining whether a target item assignment can be reached from an initial item assignment by a sequence of pairwise exchanges of items between agents. In particular, we consider the situation where each agent has a dichotomous preference over the items, that is, each agent evaluates each item as acceptable or unacceptable. Furthermore, we assume that communication between agents is limited, and the relationship is represented by an undirected graph. Then, a pair of agents can exchange their items only if they are connected by an edge and the involved items are acceptable. We prove that this problem is PSPACE -complete even when the communication graph is complete (that is, every pair of agents can exchange their items), and this problem can be solved in polynomial time if an input graph is a tree.

Original languageEnglish
Title of host publicationPRIMA 2022
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 24th International Conference, Proceedings
EditorsReyhan Aydoğan, Natalia Criado, Victor Sanchez-Anguix, Jérôme Lang, Marc Serramia
PublisherSpringer Science and Business Media Deutschland GmbH
Pages650-658
Number of pages9
ISBN (Print)9783031212024
DOIs
Publication statusPublished - 2023
Event24th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020 - Valencia , Spain
Duration: 2022 Nov 162022 Nov 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13753 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference24th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020
Country/TerritorySpain
CityValencia
Period22/11/1622/11/18

Keywords

  • Combinatorial reconfiguration
  • Dichotomous preference
  • Item assignment

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'On Reachable Assignments Under Dichotomous Preferences'. Together they form a unique fingerprint.

Cite this