Top trading cycles handle matroid constraints and ties in preferences

Top Trading Cycles with Indifferences under Matroid Constraints

Computer Science and Game Theory

Summary

This work looks at how to exchange items among people who may start with some items and might not have clear preferences among them. Each person has a limited choice of items according to special rules (called matroid constraints), and the authors develop a method called top-class trading cycles (TCTC) to handle this. TCTC lets people trade fairly, efficiently, and without lying about preferences, even when they are unsure between items. The method works quickly and generalizes previous approaches used in housing and school assignments. It helps ensure everyone gets a good and fair deal under complex rules.

What this means in practice

  • For school district planners: Assign students to schools fairly under complex seat constraints and when students have tied preferences among schools.
  • For public housing agencies: Reallocate houses among tenants efficiently respecting legal restrictions and allowing tenants to express equal preference among multiple houses.

Authors

Yasushi Kawase

Abstract

We study the reallocation of indivisible objects among agents who may hold initial endowments and may be indifferent between objects. Each agent has her own set of admissible objects, and a matroid constraint specifies which combinations of assigned objects are feasible. The model contains the housing market, house allocation with newcomers who hold no endowment, and the assignment of students to schools under matroidal constraints at each school. For this model, we introduce the top-class trading cycles mechanism (TCTC), which extends the top trading cycles mechanism (TTC) to matroid constraints and weak preferences. When a trading cycle is selected, TCTC fixes each agent's top indifference class rather than a specific object and postpones the choice within the class to the end. TCTC is individually rational, Pareto efficient, and weakly group-strategy-proof on the full domain of weak preferences, and it runs in polynomial time. When preferences and reports are strict, TCTC is strongly group-strategy-proof. Together with a known impossibility result, our theorem establishes a maximal domain of school-by-school constraints for individual rationality, Pareto efficiency, and strategy-proofness.