Object reachability via swaps under strict and weak preferences
- PDF / 2,386,769 Bytes
- 33 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 210 Views
(2020) 34:51
Object reachability via swaps under strict and weak preferences Sen Huang1 · Mingyu Xiao1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The Housing Market problem is a widely studied resource 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 first consider 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 among objects is allowed). This problem is polynomial-time solvable in a star-network and NP-complete in a tree-network. It is left as a challenging open problem whether the problem is polynomial-time solvable when the network is a path. We answer this open problem positively by giving a polynomial-time algorithm. Then we show that when the preferences of the agents are weak (ties among objects are allowed), the problem becomes NP-hard when the network is a path and can be solved in polynomial time when the network is a star. Besides, we consider the computational complexity of finding different optimal assignments for the problem in the special case where the network is a path or a star. Keywords Resource allocation · Social choice theory · Pareto efficiency · Computational complexity · Coordination and cooperation
1 Introduction Allocating indivisible objects to agents is an important problem in both computer science and economics. A widely studied setting is that each agent can only receive one single object and each agent has preferences over objects. The problem is called the Assignment problem [1, 2], or the House Allocation problem [3, 4]. When each agent is initially endowed with an object and we want to reallocate objects under some conditions without any monetary transfers, the problem is known as Housing Market problem [5]. Housing * Mingyu Xiao [email protected] Sen Huang [email protected] 1
University of Electronic Science and Technology of China, Chengdu, China
13
Vol.:(0123456789)
51
Page 2 of 33
Autonomous Agents and Multi-Agent Systems
(2020) 34:51
Market has several real-life applications such as allocation of housings [6], organ exchange [7], and so on. There are two different preference sets for agents. One is strict, which is a full ordinal list of all objects, and the other one is weak, where agents are allowed to be indifferent between objects. Both preference sets have been widely studied. Under strict preferences, the celebrated Top Trading Cycle rule [5] has several important properties, e.g. strategy-proofness, and has been frequently used in mechanism design. Some modifications of Top Trading Cycle rule, called Top Trading Absorbing Sets rule and Top Cycles rule, were introduced for weak preferences [8, 9]. More studies of Housing Ma
Data Loading...
