Bounded incentives in manipulating the probabilistic serial rule

DOI10.1016/J.JCSS.2023.103491MaRDI QIDQ6142601zbMATH OpenOpenAlexFDO

Authors Haoqiang Huang, Zihe Wang, Zhide Wei, Jie Zhang

Publication date 4 January 2024

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2001.10640

zbMATH Keywords

incentive ratiomanipulationprobabilistic serial mechanismrandom assignmentresource allocation

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: 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 $frac32$. 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.

Cites work

• A new solution to the random assignment problem.
• A solution to the random assignment problem on the full preference domain
• An equilibrium analysis of the probabilistic serial mechanism
• An experimental study on the incentives of the probabilistic serial mechanism
• Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms
• Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
• Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules
• How Profitable Are Strategic Behaviors in a Market?
• Incentive ratio: a game theoretical analysis of market equilibria
• Incentive Ratios of Fisher Markets
• On a conjecture by Gale about one-sided matching problems
• Probabilistic assignment of objects: characterizing the serial rule
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Single transferable vote resists strategic voting
• Size versus fairness in the assignment problem
• Social welfare in one-sided matching markets without money
• Social welfare in one-sided matchings: random priority and beyond
• Strategy-proof allocation of indivisible goods
• The computational difficulty of manipulating an election
• The zero-one principle for switching networks
• Why do popular mechanisms lack efficiency in random environments?

Cited in

(2)

• When is truthfully allocating chores no harder than goods?
• Fair and almost truthful mechanisms for additive valuations and beyond

This page was built for publication: Bounded incentives in manipulating the probabilistic serial rule

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6142601)