Object Reachability via Swaps along a Line

Sen Huang, Mingyu XiaoAAAI 2019 · DOI

Object Reachability via Swaps along a Line

Introduction

The Housing Market problem is a classic model in economics and computer science where agents are each endowed with one unique object and have preferences over all available objects. The goal is to reallocate these objects through "rational trades"—swaps where no participant ends up with an object they like less than their current one. In many real-world scenarios, agents can only trade with people they know, forming a social network. While reachability is easy in a "star" network but NP-complete in a general "tree" network, the "path" network—where agents are lined up like houses on a street—remained a frustratingly open "frontier of tractability." This paper finally settles whether the path structure is computationally easy or hard.

Problem Formulation: Swaps on a Path

In a path network, agents are arranged linearly, and trades can only occur between adjacent neighbors. This constraint significantly limits the possible sequences of trades compared to a complete graph.

Figure 1: A path network P with four agents, their initial object endowments, and a sequence of rational swaps.

As shown in Figure 1, a sequence of swaps $\sigma_0, \sigma_1, \dots$ can move objects along the path. The central question is whether a specific agent can eventually obtain a specific object through such a sequence of mutually beneficial trades.

Strict Preferences: The $O(n^4)$ Algorithm

When agents have strict preferences (no ties), the authors identify a crucial Monotonicity property, or the "No-Turn-Back" rule. They prove that in any sequence of rational swaps on a path, an object moves monotonically toward its destination. It never visits the same agent twice and never reverses direction. This is because any move away from its eventual target would require a swap that is not mutually beneficial at some later stage.

This monotonicity allows the problem to be decomposed. By identifying the "partner" object in the final swap that delivers the target object to the target agent, the search space is narrowed to a set of $n$ candidate "neat" instances. The authors then model the directional constraints of all involved objects as a 2-Satisfiability (2-SAT) problem. Since 2-SAT is solvable in linear time, the overall reachability problem can be solved in $O(n^4)$ time.

Weak Preferences: NP-Hardness

The tractability of the problem vanishes when agents are allowed to be indifferent between objects (weak preferences). In this regime, the "No-Turn-Back" rule fails; an object might move away from an agent and later return without violating rationality. The authors prove that determining reachability becomes NP-hard through a reduction from 2P1N-SAT, a specific version of the Boolean satisfiability problem.

Figure 6: The high-level structure of the reduction used to prove NP-hardness for weak preferences, showing a chain of gadgets.

The reduction constructs a path of gadgets (represented by blocks $B_i$ and circles $C_j$ in Figure 6) such that the target object can reach the target agent $T$ if and only if the original SAT instance is satisfiable. This highlights a sharp "complexity jump" caused by the introduction of indifference.

Conclusion and Future Work

This work maps the "frontier of tractability" for network-constrained resource allocation. By solving the path network case, it provides both a practical algorithm for strict preferences and a theoretical boundary for weak preferences. Future research may extend these findings to more complex topologies like cycles or grids, or explore the reachability of entire assignments rather than single objects.

Summary updated

BibTeX
@inproceedings{huang2019object,
  author = {Sen Huang and Mingyu Xiao},
  title = {{Object Reachability via Swaps along a Line}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012037},
}
Figure