Object Reachability via Swaps along a Line

Authors

  • Sen Huang University of Electronic Science and Technology of China
  • Mingyu Xiao University of Electronic Science and Technology of China

DOI:

https://doi.org/10.1609/aaai.v33i01.33012037

Abstract

The HOUSING MARKET problem is a widely studied resources allocation problem. In this problem, each agent can only receive a single object and has preferences over all objects. Starting from an initial endowment, we want to reach a certain assignment via a sequence of rational trades. We consider the problem whether an object is reachable for a given agent under a social network, where a trade between two agents is allowed if they are neighbors in the network and no participant has a deficit from the trade. Assume that the preferences of the agents are strict (no tie is allowed). This problem is polynomially solvable in a star-network and NPcomplete in a tree-network. It is left as a challenging open problem whether the problem is polynomially solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Furthermore, we show that the problem on a path will become NP-hard when the preferences of the agents are weak (ties are allowed).

Downloads

Published

2019-07-17

How to Cite

Huang, S., & Xiao, M. (2019). Object Reachability via Swaps along a Line. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01), 2037-2044. https://doi.org/10.1609/aaai.v33i01.33012037

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms