The Probabilistic Serial and Random Priority Mechanisms with Minimum Quotas
Consider the problem of assigning indivisible objects to agents with strict ordinal preferences over objects, where each agent is interested in consuming at most one object, and objects have integer minimum and maximum quotas. We define an assignment to be feasible if it satisfies all quotas and assume such an assignment always exists. The Probabilistic Serial (PS) and Random Priority (RP) mechanisms are generalised based on the same intuitive idea: Allow agents to consume their most preferred available object until the total mass of agents yet to be allocated is exactly equal to the remaining amount of unfilled lower quotas; in this case, we restrict agents' menus to objects which are yet to fill their minimum quotas. We show the mechanisms satisfy the same criteria as their classical counterparts: PS is ordinally efficient, envy-free and weakly strategy-proof; RP is strategy-proof, weakly envy-free but not ordinally efficient.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Axiomatization of the Random Priority Rule
We study the problem of assigning indivisible objects to agents where each is to receive at most one. To ensure fairness in the absence of monetary compensation, we consider random assignments. Random Priority, also know…
FairnessRandom Serial Dictatorship versus Probabilistic Serial Rule: A Tale of Two Random Mechanisms
For assignment problems where agents, specifying ordinal preferences, are allocated indivisible objects, two widely studied randomized mechanisms are the Random Serial Dictatorship (RSD) and Probabilistic Serial Rule (PS…
Paired Course and Dorm Allocation
Consider a university administrator who must assign students to both courses and dorms and runs (random) serial dictatorship independently in each market. While serial dictatorship is efficient for each individual matchi…
Multi-type Resource Allocation with Partial Preferences
We propose multi-type probabilistic serial (MPS) and multi-type random priority (MRP) as extensions of the well known PS and RP mechanisms to the multi-type resource allocation problem (MTRA) with partial preferences. In…
FairnessVocal Bursts Type PredictionLocal Priority Mechanisms
We introduce a novel family of mechanisms for constrained allocation problems which we call local priority mechanisms. These mechanisms are parameterized by a function which assigns a set of agents, the local compromiser…