We study one-sided matching markets in which agents come to the market with endowments, e.g. a house allocation setting in which some people already have houses. It is known that the natural extension of the Hylland-Zeckhauser scheme for one-sided matching markets is no longer guaranteed to have equilibria when agents have endowments. We give a stronger example for this fact and show that an approximate notion of equilibrium (which is guaranteed to exist) has many desirable fairness properties. Moreover, we give a combinatorial FPTAS for such an approximate equilibrium under bi-valued utilities. We also show that a similar combinatorial algorithm can be used to compute a Nash-bargaining solution under bi-valued utilities as well.
(Joint work with Jugal Garg and Vijay Vazirani)