Constrained Serial Rule on the Full Preference Domain
We study the problem of assigning objects to agents in the presence of arbitrary linear constraints when agents are allowed to be indifferent between objects. Our main contribution is the generalization of the (Extended) Probabilistic Serial mechanism via a new mechanism called the Constrained Serial Rule. This mechanism is computationally efficient and maintains desirable efficiency and fairness properties namely constrained ordinal efficiency and envy-freeness among agents of the same type. Our mechanism is based on a linear programming approach that accounts for all constraints and provides a re-interpretation of the bottleneck set of agents that form a crucial part of the Extended Probabilistic Serial mechanism.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
Random 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…
The Vigilant Eating Rule: A General Approach for Probabilistic Economic Design with Constraints
We consider the problem of probabilistic allocation of objects under ordinal preferences. We devise an allocation mechanism, called the vigilant eating rule (VER), that applies to nearly arbitrary feasibility constraints…
Bounded Incentives in Manipulating the Probabilistic Serial Rule
The Probabilistic Serial mechanism is well-known for its desirable fairness and efficiency properties. It is one of the most prominent protocols for the random assignment problem. However, Probabilistic Serial is not inc…
FairnessTowards a Characterization of Random Serial Dictatorship
Random serial dictatorship (RSD) is a randomized assignment rule that - given a set of $n$ agents with strict preferences over $n$ houses - satisfies equal treatment of equals, ex post efficiency, and strategyproofness. …
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…
Fairness