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


Graphical Resource Allocation with Matching-Induced Utilities

Bo Li

Hong Kong Polytechnic University

Abstract:
Motivated by real-world applications, we study the fair allocation of graphical resources, where the resources are the vertices in a graph. Upon receiving a set of resources, an agent's utility equals the weight of the maximum matching in the induced subgraph. We care about both maximin share (MMS) fairness and envy-freeness up to one item (EF1). Regarding MMS, the problem does not admit a finite approximation ratio for heterogeneous agents. For homogeneous agents, we design constant-approximation polynomial-time algorithms, and also note that a significant amount of social welfare is sacrificed inevitably in order to ensure (approximate) MMS fairness. We then consider EF1 allocations whose existence is guaranteed.
We show that for homogeneous agents, there is an EF1 allocation that ensures at least a constant fraction of the maximum possible social welfare. However, the social welfare guarantee of EF1 allocations degrades to 1/n for heterogeneous agents, where n is the number of agents. Fortunately, for two special yet typical cases, namely binary-weight and two-agent, we are able to design polynomial-time algorithms ensuring constant fractions of the maximum social welfare.
Joint work with Zheng Chen, Minming Li and Guochuan Zhang

Bio:
Bo Li is currently an assistant professor in the Department of Computing at the Hong Kong Polytechnic University. Formerly, he was a Postdoctoral Fellow in the Department of Computer Science at the University of Oxford and in the Department of Electrical and Computer Engineering at the University of Texas at Austin. He received his Ph.D. in Computer Science from Stony Brook University. He is broadly interested in algorithms, AI, and computational economics, including problems related to resource allocation, game theory, online algorithms, and their applications to Blockchain and machine learning.