International Joint Conference On Theoretical Computer Science – Frontier of Algorithmic Wisdom

August 15-19, 2022, City University of Hong Kong, Hong Kong

 

Invited Speakers

Young PhD Forum


Multiwinner Voting Using Favorite-Candidate Rule

Zeyu Ren

Renmin University of China

Abstract:
We investigate multiwinner election problem seeking to minimize the social cost. We are interested in strategy-proof mechanisms where each voter only reports a single candidate. The quality of a mechanism is measured by its distortion, defined as the worst-case ratio between the social cost achieved by the mechanism and the optimal one. We find that the ratio between the maximum and minimum distances among every two candidates plays a vital role in the setting. We discuss two cases according to the dimension. When voters and candidates are embedded in 1-dimensional space, we establish several lower bounds of the distortion. When voters and candidates are embedded in multi-dimensional space, we give an asymptotically tight bound of the distortion.

Bio:
He received the bachelor’s degree from School of Information, Renmin University of China, and master's degree at Renmin University of China in 2020. He is currently studying at the Gaoling School of Artificial Intelligence, Renmin University of China, in the second year of his doctorate. The doctoral supervisor is Zihe Wang.