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 incentive-compatible, thereby these desirable properties only hold for the agents' declared preferences, rather than their genuine preferences. A substantial utility gain through strategic behaviors would trigger self-interested agents to manipulate the mechanism and would subvert the very foundation of adopting the mechanism in practice. In this paper, we characterize the extent to which an individual agent can increase its utility by strategic manipulation. We show that the incentive ratio of the mechanism is $\frac{3}{2}$. That is, no agent can misreport its preferences such that its utility becomes more than 1.5 times of what it is when reports truthfully. This ratio is a worst-case guarantee by allowing an agent to have complete information about other agents' reports and to figure out the best response strategy even if it is computationally intractable in general. To complement this worst-case study, we further evaluate an agent's utility gain on average by experiments. The experiments show that an agent' incentive in manipulating the rule is very limited. These results shed some light on the robustness of Probabilistic Serial against strategic manipulation, which is one step further than knowing that it is not incentive-compatible.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessSimilar Papers 제목 키워드 기반
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)…
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…
General Policies, Subgoal Structure, and Planning Width
It has been observed that many classical planning domains with atomic goals can be solved by means of a simple polynomial exploration procedure, called IW, that runs in time exponential in the problem width, which in the…
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…
FairnessRawlsian Assignments
We study the assignment of indivisible goods to individuals without monetary transfers. Previous literature has mainly focused on efficiency and individually fair assignments; consequently, egalitarian concerns have been…
Fairness