Papers for

public housing agencies

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Top trading cycles handle matroid constraints and ties in preferences

Top Trading Cycles with Indifferences under Matroid Constraints

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.

Sat 26 SeptComputer Science and Game Theory
The gist
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.
Open → 2609.32337v1