Object reachability via swaps under strict and weak preferences

摘要

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.