The crawler: three equivalence results for object (re)allocation problems when preferences are single-peaked

DOI10.1016/J.JET.2022.105466zbMATH Open1497.91144OpenAlexW4280530169MaRDI QIDQ2155231FDOQ2155231

Authors Yuki Tamura, Hadi Hosseini

Publication date 15 July 2022

Published in Journal of Economic Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.06909

zbMATH Keywords

single-peaked preferencesobject reallocation problemsrandom priority rulethe crawler

Mathematics Subject Classification ID

Individual preferences (91B08) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Abstract: For object reallocation problems, if preferences are strict but otherwise unrestricted, the Top Trading Cycles rule (TTC) is the leading rule: It is the only rule satisfying efficiency, individual rationality, and strategy-proofness. However, on the subdomain of single-peaked preferences, Bade (2019) defines a new rule, the "crawler", which also satisfies these three properties. (i) The crawler selects an allocation by "visiting" agents in a specific order. A natural "dual" rule can be defined by proceeding in the reverse order. Our first theorem states that the crawler and its dual are actually the same. (ii) Single-peakedness of a preference profile may in fact hold for more than one order and its reverse. Our second theorem states that the crawler is invariant to the choice of the order. (iii) For object allocation problems (as opposed to reallocation problems), we define a probabilistic version of the crawler by choosing an endowment profile at random according to a uniform distribution, and applying the original definition. Our third theorem states that this rule is the same as the "random priority rule".

Recommendations

• Object reallocation problems under single-peaked preferences: two characterizations of the crawler
• Matching with single-peaked preferences
• Object reallocation problems with single-dipped preferences
• An alternative characterization of the equal-distance rule for allocation problems with single-peaked preferences
• The object allocation problem with random priorities

Cites work

• A general equivalence theorem for allocation of indivisible objects
• A short proof for the characterization of the core in housing markets
• An Exact Analysis of Stable Allocation
• An alternative proof of a characterization of the TTC mechanism
• House allocation with existing tenants: an equivalence
• Incentive compatible allocation and exchange of discrete resources
• Lotteries in student assignment: an equivalence result
• Matching with single-peaked preferences
• Object reallocation problems under single-peaked preferences: two characterizations of the crawler
• On cores and indivisibility
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Random mechanisms for house allocation with existing tenants
• Random serial dictatorship: the one and only
• Strategy-proof allocation of indivisible goods
• Strategy-proofness and the strict core in a market with indivisibilities
• The Division Problem with Single-Peaked Preferences: A Characterization of the Uniform Allocation Rule

Cited in

(4)

• Matching with single-peaked preferences
• Exchange of indivisible goods under matroid constraints
• Object reallocation problems with single-dipped preferences
• Object reallocation problems under single-peaked preferences: two characterizations of the crawler

This page was built for publication: The crawler: three equivalence results for object (re)allocation problems when preferences are single-peaked

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155231)