The Crawler: Three Equivalence Results for Object (Re)allocation Problems when Preferences Are Single-peaked
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".
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fairness for Multi-Self Agents
We investigate whether fairness is compatible with efficiency in economies with multi-self agents, who may not be able to integrate their multiple objectives into a single complete and transitive ranking. We adapt envy-f…
FairnessSwap Dynamics in Single-Peaked Housing Markets
This paper focuses on the problem of fairly and efficiently allocating resources to agents. We consider a specific setting, usually referred to as a housing market, where each agent must receive exactly one resource (and…
An Optimal Procedure to Check Pareto-Optimality in House Markets with Single-Peaked Preferences
Recently, the problem of allocating one resource per agent with initial endowments (house markets) has seen a renewed interest: indeed, while in the domain of strict preferences the Top Trading Cycle algorithm is known t…
Efficient reallocation of indivisible resources: Pair-efficiency versus Pareto-efficiency
In the object reallocation problem, achieving Pareto-efficiency is desirable, but may be too demanding for implementation purposes. In contrast, pair-efficiency, which is the minimal efficiency requirement, is more suita…
Discovering Forbidden Topics in Language Models
Refusal discovery is the task of identifying the full set of topics that a language model refuses to discuss. We introduce this new problem setting and develop a refusal discovery method, LLM-crawler, that uses token pre…
Memorization