Abstract: Resource allocation problem is a basic class of combinatorial optimization problem and has found widespread application across various fields, such as economics and computer science where resources like goods and chores must be allocated among agents. In our survey, we focus on the challenges caused by indivisible resources. We consider fairness and efficiency criteria, including envy-freeness, proportionality, equitability, maximin share, Pareto optimality, and their relaxations. And we survey the recent progress of existential results, algorithms, and approximations that satisfy various fairness criteria in related literature. Additionally, we discuss algorithms that achieve both fairness and efficiency, such as envy free up to one item and Pareto optimality. We also study the computational complexity of these algorithms, and the likelihood of finding fair and efficient allocations. And we summarize the common algorithm design techniques, and open questions for future research.

Key words: fairness, efficiency, resource allocation