  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.

Computer Science and Game Theory;Artificial Intelligence;Multiagent Systems