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 Faculty Forum in TCS


Ordinal Approximation Algorithms for MMS Allocation of Chores

Xiaowei Wu

University of Macau

Abstract: We initiate the work on maximin share (MMS) fair allocation of m indivisible chores to n agents using only their ordinal preferences, from both algorithmic and mechanism design perspectives. The previous best-known approximation ratio using ordinal preferences is 2-1/n by Aziz et al. [AAAI 2017]. We improve this result by giving a deterministic 5/3-approximation algorithm that determines an allocation sequence of agents, according to which items are allocated one by one. By a tighter analysis, we show that for n=2 and 3, our algorithm achieves better approximation ratios, and is actually optimal. We also consider the setting with strategic agents, where agents may misreport their preferences to manipulate the outcome. We first provide a strategyproof O(log (m/n))-approximation consecutive picking algorithm, and then improve the approximation ratio to O((log n)^0.5) by a randomized algorithm. Both algorithms only use the ordinal preferences of agents.

Bio: Dr. Xiaowei Wu is an Assistant Professor in the Department of Computer and Information Science with the State Key Laboratory of Internet of Things for Smart City (IOTSC) at University of Macau (UM). He received his Ph.D. degree from the University of Hong Kong (HKU) and his B.Eng. degree from University of Science and Technology of China (USTC). His research interests span various topics in online approximation algorithms, algorithmic game theory and data mining. He has published more than 30 papers in top theory or artificial intelligence conferences and journals including JACM, SICOMP, MAPR, STOC, FOCS, SODA, AAAI and IJCAI.