Bounded incentives in manipulating the probabilistic serial rule

Haoqiang Huang; Zihe Wang; Zhide Wei; Jie Zhang

doi:10.1016/j.jcss.2023.103491

Bounded incentives in manipulating the probabilistic serial rule

Haoqiang Huang, Zihe Wang, Zhide Wei, Jie Zhang

Research output: Contribution to journal › Article › peer-review

1 Citation (SciVal)

22 Downloads (Pure)

Abstract

The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead self-interested agents to manipulate the mechanism, undermining its practical adoption. To gauge the potential for manipulation, we explore an extreme scenario where a manipulator has complete knowledge of other agents' reports and unlimited computational resources to find their best strategy. We establish tight incentive ratio bounds of the mechanism. Furthermore, we complement these worst-case guarantees by conducting experiments to assess an agent's average utility gain through manipulation. The findings reveal that the incentive for manipulation is very small. These results offer insights into the mechanism's resilience against strategic manipulation, moving beyond the recognition of its lack of incentive compatibility.

Original language	English
Article number	103491
Number of pages	15
Journal	Journal of Computer and System Sciences
Volume	140
Early online date	28 Oct 2023
DOIs	https://doi.org/10.1016/j.jcss.2023.103491 https://doi.org/10.1016/j.jcss.2023.103491
Publication status	Published - 31 Mar 2024

Bibliographical note

Funding Information:
The authors thank the reviewers for their thoughtful comments and efforts towards improving the manuscript. Zihe Wang was supported by the Shanghai Sailing Program (Grant No. 18YF1407900 ) and the National NSFC (Grant No. 61806121 ). Jie Zhang was supported by a Leverhulme Trust Research Project Grant (2021–2024) and an EPSRC research grant ( EP/W014912/1 ). Part of this work was done when Jie Zhang was visiting Peking University.

Data availability:
No data was used for the research described in the article.

Data Availability Statement

No data was used for the research described in the article.

Funding

The authors thank the reviewers for their thoughtful comments and efforts towards improving the manuscript. Zihe Wang was supported by the Shanghai Sailing Program (Grant No. 18YF1407900 ) and the National NSFC (Grant No. 61806121 ). Jie Zhang was supported by a Leverhulme Trust Research Project Grant (2021–2024) and an EPSRC research grant ( EP/W014912/1 ). Part of this work was done when Jie Zhang was visiting Peking University. The authors thank the reviewers for their thoughtful comments and efforts towards improving the manuscript. Zihe Wang was supported by the Shanghai Sailing Program (Grant No. 18YF1407900) and the National NSFC (Grant No. 61806121). Jie Zhang was supported by a Leverhulme Trust Research Project Grant (2021–2024) and an EPSRC research grant (EP/W014912/1). Part of this work was done when Jie Zhang was visiting Peking University.

Funders	Funder number
National NSFC	61806121
Shanghai Sailing Program	18YF1407900
Engineering and Physical Sciences Research Council	EP/W014912/1
Leverhulme Trust	2021–2024
Peking University

Keywords

Incentive ratio
Manipulation
Probabilistic serial mechanism
Random assignment
Resource allocation

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science
Computer Networks and Communications
Computational Theory and Mathematics
Applied Mathematics

Access to Document

Bounded incentives in manipulating the probabilistic serial rule (accepted author manuscript)Accepted author manuscript, 627 KBLicence: CC BY-NC-ND
1-s2.0-S002200002300096X-main-2Final published version, 878 KB

Cite this

@article{93f75ae5b27548cea0027c450d8bcae5,

title = "Bounded incentives in manipulating the probabilistic serial rule",

abstract = "The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead self-interested agents to manipulate the mechanism, undermining its practical adoption. To gauge the potential for manipulation, we explore an extreme scenario where a manipulator has complete knowledge of other agents' reports and unlimited computational resources to find their best strategy. We establish tight incentive ratio bounds of the mechanism. Furthermore, we complement these worst-case guarantees by conducting experiments to assess an agent's average utility gain through manipulation. The findings reveal that the incentive for manipulation is very small. These results offer insights into the mechanism's resilience against strategic manipulation, moving beyond the recognition of its lack of incentive compatibility.",

keywords = "Incentive ratio, Manipulation, Probabilistic serial mechanism, Random assignment, Resource allocation",

author = "Haoqiang Huang and Zihe Wang and Zhide Wei and Jie Zhang",

note = "Funding Information: The authors thank the reviewers for their thoughtful comments and efforts towards improving the manuscript. Zihe Wang was supported by the Shanghai Sailing Program (Grant No. 18YF1407900 ) and the National NSFC (Grant No. 61806121 ). Jie Zhang was supported by a Leverhulme Trust Research Project Grant (2021–2024) and an EPSRC research grant ( EP/W014912/1 ). Part of this work was done when Jie Zhang was visiting Peking University. Data availability: No data was used for the research described in the article.",

year = "2024",

month = mar,

day = "31",

doi = "10.1016/j.jcss.2023.103491",

language = "English",

volume = "140",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Elsevier Academic Press Inc",

}

TY - JOUR

T1 - Bounded incentives in manipulating the probabilistic serial rule

AU - Huang, Haoqiang

AU - Wang, Zihe

AU - Wei, Zhide

AU - Zhang, Jie

N1 - Funding Information: The authors thank the reviewers for their thoughtful comments and efforts towards improving the manuscript. Zihe Wang was supported by the Shanghai Sailing Program (Grant No. 18YF1407900 ) and the National NSFC (Grant No. 61806121 ). Jie Zhang was supported by a Leverhulme Trust Research Project Grant (2021–2024) and an EPSRC research grant ( EP/W014912/1 ). Part of this work was done when Jie Zhang was visiting Peking University. Data availability: No data was used for the research described in the article.

PY - 2024/3/31

Y1 - 2024/3/31

N2 - The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead self-interested agents to manipulate the mechanism, undermining its practical adoption. To gauge the potential for manipulation, we explore an extreme scenario where a manipulator has complete knowledge of other agents' reports and unlimited computational resources to find their best strategy. We establish tight incentive ratio bounds of the mechanism. Furthermore, we complement these worst-case guarantees by conducting experiments to assess an agent's average utility gain through manipulation. The findings reveal that the incentive for manipulation is very small. These results offer insights into the mechanism's resilience against strategic manipulation, moving beyond the recognition of its lack of incentive compatibility.

AB - The Probabilistic Serial mechanism is valued for its fairness and efficiency in addressing the random assignment problem. However, it lacks truthfulness, meaning it works well only when agents' stated preferences match their true ones. Significant utility gains from strategic actions may lead self-interested agents to manipulate the mechanism, undermining its practical adoption. To gauge the potential for manipulation, we explore an extreme scenario where a manipulator has complete knowledge of other agents' reports and unlimited computational resources to find their best strategy. We establish tight incentive ratio bounds of the mechanism. Furthermore, we complement these worst-case guarantees by conducting experiments to assess an agent's average utility gain through manipulation. The findings reveal that the incentive for manipulation is very small. These results offer insights into the mechanism's resilience against strategic manipulation, moving beyond the recognition of its lack of incentive compatibility.

KW - Incentive ratio

KW - Manipulation

KW - Probabilistic serial mechanism

KW - Random assignment

KW - Resource allocation

UR - http://www.scopus.com/inward/record.url?scp=85176583253&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2023.103491

DO - 10.1016/j.jcss.2023.103491

M3 - Article

AN - SCOPUS:85176583253

SN - 0022-0000

VL - 140

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

M1 - 103491

ER -

Bounded incentives in manipulating the probabilistic serial rule

Abstract

Bibliographical note

Data Availability Statement

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Logistics Optimisation After Brexit and COVID-19

Cite this

Bounded incentives in manipulating the probabilistic serial rule

Abstract

Bibliographical note

Data Availability Statement

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Projects

Logistics Optimisation After Brexit and COVID-19

Cite this