Search

We consider the problem of fair allocation of $m$ indivisible items to a group of $n$ agents with subsidy (money). Our work mainly focuses on the allocation of chores but most of our results extend to the allocation of goods as well. We consider the case when agents have (general) additive cost functions. Assuming that the maximum cost of an item to an agent can be compensated by one dollar, we show that a total of $n/4$ dollars of subsidy suffices to ensure a proportional allocation. Moreover, we show that $n/4$ is tight in the sense that there exists an instance with $n$ agents for which every proportional allocation requires a total subsidy of at least $n/4$. We also consider the weighted case and show that a total subsidy of $(n-1)/2$ suffices to ensure a weighted proportional allocation., 24 pages, 4 figures

Allocating resources to individuals in a fair manner has been a topic of interest since ancient times, with most of the early mathematical work on the problem focusing on resources that are infinitely divisible. Over the last decade, there has been a surge of papers studying computational questions regarding the indivisible case, for which exact fairness notions such as envy-freeness and proportionality are hard to satisfy. One main theme in the recent research agenda is to investigate the extent to which their relaxations, like maximin share fairness (MMS) and envy-freeness up to any good (EFX), can be achieved. In this survey, we present a comprehensive review of the recent progress made in the related literature by highlighting different ways to relax fairness notions, common algorithm design techniques, and the most interesting questions for future research., Comment: This survey unifies and extends preliminary versions that appeared in IJCAI 2022 (arXiv:2202.07551) and SIGecom Exchanges (arXiv:2202.08713). It has been accepted for publication to the journal of Artificial Intelligence (AIJ)

We consider the online bipartite matching problem on $(k,d)$-bounded graphs, where each online vertex has at most $d$ neighbors, each offline vertex has at least $k$ neighbors, and $k\geq d\geq 2$. The model of $(k,d)$-bounded graphs is proposed by Naor and Wajc (EC 2015 and TEAC 2018) to model the online advertising applications in which offline advertisers are interested in a large number of ad slots, while each online ad slot is interesting to a small number of advertisers. They proposed deterministic and randomized algorithms with a competitive ratio of $1 - (1-1/d)^k$ for the problem, and show that the competitive ratio is optimal for deterministic algorithms. They also raised the open questions of whether strictly better competitive ratios can be achieved using randomized algorithms, for both the adversarial and stochastic arrival models. In this paper we answer both of their open problems affirmatively. For the adversarial arrival model, we propose a randomized algorithm with competitive ratio $1 - (1-1/d)^k + \Omega(d^{-4}\cdot e^{-\frac{k}{d}})$ for all $k\geq d\geq 2$. We also consider the stochastic model and show that even better competitive ratios can be achieved. We show that for all $k\geq d\geq 2$, the competitive ratio is always at least $0.8237$. We further consider the $b$-matching problem when each offline vertex can be matched at most $b$ times, and provide several competitive ratio lower bounds for the adversarial and stochastic model., Comment: 23 pages, 5 figures

We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent $i$ has a non-negative weight $w_i$ that represents its obligation for undertaking the chores. We consider the fairness notion of weighted envy-freeness up to one item (WEF1) and propose an efficient picking sequence algorithm for computing WEF1 allocations. Our analysis is based on a natural and powerful continuous interpretation for the picking sequence algorithms in the weighted setting, which might be of independent interest. Using this interpretation, we establish the necessary and sufficient conditions under which picking sequence algorithms can guarantee other fairness notions in the weighted setting. We also study the existence of fair and efficient allocations and propose efficient algorithms for the computation of WEF1 and PO allocations for the bi-valued instances. Our result generalizes that of Garg et al. (AAAI 2022) and Ebadian et al. (AAMAS 2022) to the weighted setting. Our work also studies the price of fairness for WEF1, and the implications of WEF1 to other fairness notions., Comment: 26 pages, 2 figures

We consider the problem of fairly allocating a sequence of indivisible items that arrive online in an arbitrary order to a group of n agents with additive normalized valuation functions. We consider both the allocation of goods and chores and propose algorithms for approximating maximin share (MMS) allocations. When agents have identical valuation functions the problem coincides with the semi-online machine covering problem (when items are goods) and load balancing problem (when items are chores), for both of which optimal competitive ratios have been achieved. In this paper, we consider the case when agents have general additive valuation functions. For the allocation of goods, we show that no competitive algorithm exists even when there are only three agents and propose an optimal 0.5-competitive algorithm for the case of two agents. For the allocation of chores, we propose a (2-1/n)-competitive algorithm for n>=3 agents and a square root of 2 (approximately 1.414)-competitive algorithm for two agents. Additionally, we show that no algorithm can do better than 15/11 (approximately 1.364)-competitive for two agents., 29 pages, 1 figure (to appear in ICML 2023)

We study the single-choice prophet inequality problem, where a gambler faces a sequence of $n$ online i.i.d. random variables drawn from an unknown distribution. When a variable reveals its value, the gambler needs to decide irrevocably whether or not to accept it. The goal is to maximize the competitive ratio between the expected gain of the gambler and that of the maximum variable. It is shown by Correa et al. that when the distribution is unknown or only $o(n)$ uniform samples from the distribution are given, the best an algorithm can do is $1/e$-competitive. In contrast, when the distribution is known or $\Omega(n)$ uniform samples are given, the optimal competitive ratio 0.7451 can be achieved. In this paper, we propose a new model in which the algorithm has access to an oracle that answers quantile queries about the distribution, and study the extent to which we can use a small number of queries to achieve good competitive ratios. Naturally, by making queries to the oracle, one can implement the threshold-based blind strategies that use the answers from the queries as thresholds to accept variables. Our first contribution is to prove that the competitive ratio improves gracefully with the number of thresholds. Particularly with two thresholds our algorithm achieves a competitive ratio of 0.6786. Our second contribution, surprisingly, shows that with a single query, we can do strictly better than with a single threshold. The algorithm sets a threshold in the first phase by making a single query and uses the maximum realization from the first phase as the threshold for the second phase. It can be viewed as a natural combination of the single-threshold algorithm and the algorithm for the secretary problem. By properly choosing the quantile to query and the break-point between the two phases, we achieve a competitive ratio of 0.6718., Comment: 22 pages

The theory of algorithmic fair allocation is within the center of multi-agent systems and economics in the last decade due to its industrial and social importance. At a high level, the problem is to assign a set of items that are either goods or chores to a set of agents so that every agent is happy with what she obtains. Particularly, in this survey, we focus on indivisible items, for which absolute fairness such as envy-freeness and proportionality cannot be guaranteed. One main theme in the recent research agenda is about designing algorithms that approximately achieve the fairness criteria. We aim at presenting a comprehensive survey of recent progresses through the prism of algorithms, highlighting the ways to relax fairness notions and common techniques to design algorithms, as well as the most interesting questions for future research.

In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents' budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1.

In this paper, we study how to fairly allocate m indivisible chores to n (asymmetric) agents. We consider (weighted) proportionality up to any item (PROPX) and show that a (weighted) PROPX allocation always exists and can be computed efficiently. For chores, we argue that PROPX might be a more reliable relaxation for proportionality by the facts that any PROPX allocation ensures 2-approximation of maximin share (MMS) fairness [Budish, 2011] for symmetric agents and of anyprice share (APS) fairness [Babaioff et al, 2021] for asymmetric agents. APS allocations for chores have not been studied before the current work, and our result implies a 2-approximation algorithm. Another by-product result is that an EFX and a weighted EF1 allocation for indivisible chores exist if all agents have the same ordinal preference, which might be of independent interest. We then consider the partial information setting and design algorithms that only use agents' ordinal preferences to compute approximately PROPX allocations. Our algorithm achieves a 2-approximation for both symmetric and asymmetric agents, and the approximation ratio is optimal. Finally, we study the price of fairness (PoF), i.e., the loss in social welfare by enforcing allocations to be (weighted) PROPX. We prove that the tight ratio for PoF is Theta(n) for symmetric agents and unbounded for asymmetric agents.

We study the oblivious matching problem, which aims at finding a maximum matching on a graph with unknown edge set. Any algorithm for the problem specifies an ordering of the vertex pairs. The matching is then produced by probing the pairs following the ordering, and including a pair if both of them are unmatched and there exists an edge between them. The unweighted (Chan et al. (SICOMP 2018)) and the vertex-weighted (Chan et al. (TALG 2018)) versions of the problem are well studied. In this paper, we consider the edge-weighted oblivious matching problem on bipartite graphs, which generalizes the stochastic bipartite matching problem. Very recently, Gamlath et al. (SODA 2019) studied the stochastic bipartite matching problem, and proposed an (1-1/e)-approximate algorithm. We give a very simple algorithm adapted from the Ranking algorithm by Karp et al. (STOC 1990), and show that it achieves the same (1-1/e) approximation ratio for the oblivious matching problem on bipartite graph., 5 pages

In classic network security games, the defender distributes defending resources to the nodes of the network, and the attacker attacks a node, with the objective to maximize the damage caused. Existing models assume that the attack at node u causes damage only at u. However, in many real-world security scenarios, the attack at a node u spreads to the neighbors of u and can cause damage at multiple nodes, e.g., for the outbreak of a virus. In this paper, we consider the network defending problem against contagious attacks. Existing works that study shared resources assume that the resource allocated to a node can be shared or duplicated between neighboring nodes. However, in real world, sharing resource naturally leads to a decrease in defending power of the source node, especially when defending against contagious attacks. To this end, we study the model in which resources allocated to a node can only be transferred to its neighboring nodes, which we refer to as a reallocation process. We show that this more general model is difficult in two aspects: (1) even for a fixed allocation of resources, we show that computing the optimal reallocation is NP-hard; (2) for the case when reallocation is not allowed, we show that computing the optimal allocation (against contagious attack) is also NP-hard. For positive results, we give a mixed integer linear program formulation for the problem and a bi-criteria approximation algorithm. Our experimental results demonstrate that the allocation and reallocation strategies our algorithm computes perform well in terms of minimizing the damage due to contagious attacks., Comment: 9 pages; AAAI 2021

The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity., Comment: 16 pages, 2 figures

Classic dynamic data structure problems maintain a data structure subject to a sequence S of updates and they answer queries using the latest version of the data structure, i.e., the data structure after processing the whole sequence. To handle operations that change the sequence S of updates, Demaine et al. (TALG 2007) introduced retroactive data structures. A retroactive operation modifies the update sequence S in a given position t, called time, and either creates or cancels an update in S at time t. A partially retroactive data structure restricts queries to be executed exclusively in the latest version of the data structure. A fully retroactive data structure supports queries at any time t: a query at time t is answered using only the updates of S up to time t. If the sequence S only consists of insertions, the resulting data structure is an incremental retroactive data structure. While efficient retroactive data structures have been proposed for classic data structures, e.g., stack, priority queue and binary search tree, the retroactive version of graph problems are rarely studied. In this paper we study retroactive graph problems including connectivity, minimum spanning forest (MSF), maximum degree, etc. We provide fully retroactive data structures for maintaining the maximum degree, connectivity and MSF in $\tilde{O}(n)$ time per operation. We also give an algorithm for the incremental fully retroactive connectivity with $\tilde{O}(1)$ time per operation. We compliment our algorithms with almost tight hardness results. We show that under the OMv conjecture (proposed by Henzinger et al. (STOC 2015)), there does not exist fully retroactive data structures maintaining connectivity or MSF, or incremental fully retroactive data structure maintaining the maximum degree with $O(n^{1-\epsilon})$ time per operation, for any constant $\epsilon > 0$.

Huang et al.~(STOC 2018) introduced the fully online matching problem, a generalization of the classic online bipartite matching problem in that it allows all vertices to arrive online and considers general graphs. They showed that the ranking algorithm by Karp et al.~(STOC 1990) is strictly better than $0.5$-competitive and the problem is strictly harder than the online bipartite matching problem in that no algorithms can be $(1-1/e)$-competitive. This paper pins down two tight competitive ratios of classic algorithms for the fully online matching problem. For the fractional version of the problem, we show that a natural instantiation of the water-filling algorithm is $2-\sqrt{2} \approx 0.585$-competitive, together with a matching hardness result. Interestingly, our hardness result applies to arbitrary algorithms in the edge-arrival models of the online matching problem, improving the state-of-art $\frac{1}{1+\ln 2} \approx 0.5906$ upper bound. For integral algorithms, we show a tight competitive ratio of $\approx 0.567$ for the ranking algorithm on bipartite graphs, matching a hardness result by Huang et al. (STOC 2018)., Comment: To appear SODA 2019

We consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of $(5 - \sqrt{5})/2 \approx 1.382$, matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case., Comment: 36 pages, 6 figures, to appear in APPROX 2018

We consider the online vector packing problem in which we have a $d$ dimensional knapsack and items $u$ with weight vectors $\mathbf{w}_u \in \mathbb{R}_+^d$ arrive online in an arbitrary order. Upon the arrival of an item, the algorithm must decide immediately whether to discard or accept the item into the knapsack. When item $u$ is accepted, $\mathbf{w}_u(i)$ units of capacity on dimension $i$ will be taken up, for each $i\in[d]$. To satisfy the knapsack constraint, an accepted item can be later disposed of with no cost, but discarded or disposed of items cannot be recovered. The objective is to maximize the utility of the accepted items $S$ at the end of the algorithm, which is given by $f(S)$ for some non-negative monotone submodular function $f$. For any small constant $\epsilon > 0$, we consider the special case that the weight of an item on every dimension is at most a $(1-\epsilon)$ fraction of the total capacity, and give a polynomial-time deterministic $O(\frac{k}{\epsilon^2})$-competitive algorithm for the problem, where $k$ is the (column) sparsity of the weight vectors. We also show several (almost) tight hardness results even when the algorithm is computationally unbounded. We show that under the $\epsilon$-slack assumption, no deterministic algorithm can obtain any $o(k)$ competitive ratio, and no randomized algorithm can obtain any $o(\frac{k}{\log k})$ competitive ratio. For the general case (when $\epsilon = 0$), no randomized algorithm can obtain any $o(k)$ competitive ratio. In contrast to the $(1+\delta)$ competitive ratio achieved in Kesselheim et al. (STOC 2014) for the problem with random arrival order of items and under large capacity assumption, we show that in the arbitrary arrival order case, even when $\| \mathbf{w}_u \|_\infty$ is arbitrarily small for all items $u$, it is impossible to achieve any $o(\frac{\log k}{\log\log k})$ competitive ratio., Comment: The conference version of this paper appears in ESA 2017