Fairness and efficiency in resource allocation

Abstract

Fairness and efficiency are two fundamental topics in resource allocation. In resource allocation problems, we need to allocate a set of items to a set of agents. From an efficiency perspective, our goal is to maximize the total reward of the allocation. From the perspective of fairness, we want to ensure that every agent feels the allocation is fair. This thesis aims to identify required allocations from these different perspectives. We present our findings in three parts: (i) efficiency in online resource allocation, (ii) fairness in offline resource allocation, and (iii) fairness and efficiency in offline resource allocation.

In Part I, we study the efficiency guarantees in the fully online matching problem, which is a constrained resource allocation problem. Since efficiency is easily guaranteed in the offline setting, we focus on the fully online setting where both agents and items arrive dynamically. For this problem, we provide a randomized algorithm that achieves a competitive ratio of $0.1549$.

In Part II, we investigate fairness guarantees in the offline resource allocation problem. In this part, we first consider a mixed goods setting where some items can be divided into arbitrarily small pieces, while others can only be fully allocated to an agent. In this problem, we propose two ``up to a fraction'' relaxations of some classical fairness concepts, and prove the existence of such fair allocations in the mixed goods setting. We then return to the indivisible goods setting, where every item must be fully allocated to a single agent. In this setting, we allow some uncertainties in agents' preferences towards items and provide some complexity analysis of finding allocations that can be fair with a high probability.

In Part III, we aim to find a fair and efficient allocation in the offline resource allocation problem. We first study the price of fairness, which measures the efficiency loss when considering the fairness constraints. For this, we consider both the indivisible goods and the mixed goods settings, and provide a tight analysis of the price of fairness in these two settings. We then come to a resource allocation problem for cloud computing, where agents have Leontief preferences over items. In this setting, we propose several new mechanisms that can produce a fair allocation with better social welfare guarantee.