מירב זהבי

The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current “status”. For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms.