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

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


Invited Speakers

Track A

EFX under Budget Constraint

Sijia Dai

Chinese Academy of Sciences

Fair division captures many real-world scenarios and plays an important role in many research fields including computer science, economy, operations research, etc. For the problem of indivisible goods allocation, it is well-known that an allocation satisfying the {\em maximum Nash Social Welfare} (Max-NSW) is {\em envy-free up to one good} (EF1), which is an important fairness concept. However, EF1 is often considered to be somewhat weak since one may remove the most valuable good. In this paper, we investigate the relationship between the Max-NSW allocation and a stronger fairness concept, {\em envy-free up to any good} (EFX), which means the envyness disappears after the removal of the least valuable good. We focus on the budget-feasible variant in which each agent has a budget to cover the total cost of goods she gets. We show that a Max-NSW allocation guarantees $\frac{1}{4}$-EFX when agents' value are in the \textit{Binary} $\{0,1\}$. Moreover, we provide an algorithm to find a budget-feasible EFX allocation for the \textit{Binary} variant.

Sijia Dai is a postgraduate student in Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences. Prior to that, she was an undergraduate student at Beijing Normal University and studied Economics. Sijia Dai is broadly interested in computational aspects of economics and game theory, design and analysis of algorithms. Currently, she is working on designing approximation algorithms for fair division problems.