More Like this

1. Approximating Maximin Share Allocations

   https://doi.org/10.4230/OASIcs.SOSA.2019.20  

   Garg, Jugal; McGlaughlin, Peter; Taki, Setareh (January 2019, Open access series in informatics)

   We study the problem of fair allocation of M indivisible items among N agents using the popular notion of maximin share as our measure of fairness. The maximin share of an agent is the largest value she can guarantee herself if she is allowed to choose a partition of the items into N bundles (one for each agent), on the condition that she receives her least preferred bundle. A maximin share allocation provides each agent a bundle worth at least their maximin share. While it is known that such an allocation need not exist [Procaccia and Wang, 2014; Kurokawa et al., 2016], a series of work [Procaccia and Wang, 2014; David Kurokawa et al., 2018; Amanatidis et al., 2017; Barman and Krishna Murthy, 2017] provided 2/3 approximation algorithms in which each agent receives a bundle worth at least 2/3 times their maximin share. Recently, [Ghodsi et al., 2018] improved the approximation guarantee to 3/4. Prior works utilize intricate algorithms, with an exception of [Barman and Krishna Murthy, 2017] which is a simple greedy solution but relies on sophisticated analysis techniques. In this paper, we propose an alternative 2/3 maximin share approximation which offers both a simple algorithm and straightforward analysis. In contrast to other algorithms, our approach allows for a simple and intuitive understanding of why it works. 

   more » « less
2. Parallel Algorithm for Non-Monotone DR-Submodular Maximization

   Ene, A; Nguyen, H (January 2020, Proceedings of Machine Learning Research)

   null (Ed.)

   In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy epsilon, our algorithm achieves a 1/e−epsilon approximation using O(logn*log(1/epsilon)/epsilon^3) parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearly-optimal for any constant epsilon. Previous algorithms achieve worse approximation guarantees using Ω(log^2 n) parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality. 

   more » « less
3. Parallel Algorithm for Non-Monotone DR-Submodular Maximization

   Ene, Alina; Nguyen, Huy L (July 2020, International Conference on Machine Learning)

   null (Ed.)

   In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy $$\epsilon$$, our algorithm achieves a $$1/e - \epsilon$$ approximation using $$O(\log{n} \log(1/\epsilon) / \epsilon^3)$$ parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearly-optimal for any constant $$\epsilon$$. Previous algorithms achieve worse approximation guarantees using $$\Omega(\log^2{n})$$ parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality. 

   more » « less
4. Parallel Algorithm for Non-Monotone DR-Submodular Maximization

   Ene, Alina; Nguyen, Huy L (June 2020, International Conference on Machine Learning)

   null (Ed.)

   In this work, we give a new parallel algorithm for the problem of maximizing a non-monotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy $$\epsilon$$, our algorithm achieves a $$1/e - \epsilon$$ approximation using $$O(\log{n} \log(1/\epsilon) / \epsilon^3)$$ parallel rounds of function evaluations. The approximation guarantee nearly matches the best approximation guarantee known for the problem in the sequential setting and the number of parallel rounds is nearly-optimal for any constant $$\epsilon$$. Previous algorithms achieve worse approximation guarantees using $$\Omega(\log^2{n})$$ parallel rounds. Our experimental evaluation suggests that our algorithm obtains solutions whose objective value nearly matches the value obtained by the state of the art sequential algorithms, and it outperforms previous parallel algorithms in number of parallel rounds, iterations, and solution quality. 

   more » « less
5. Greedy-Based Online Fair Allocation with Adversarial Input: Enabling Best-of-Many-Worlds Guarantees

   https://doi.org/10.1609/aaai.v38i9.28858  

   Yang, Zongjun; Liao, Luofeng; Kroer, Christian (March 2024, Proceedings of the AAAI Conference on Artificial Intelligence)

   We study an online allocation problem with sequentially arriving items and adversarially chosen agent values, with the goal of balancing fairness and efficiency. Our goal is to study the performance of algorithms that achieve strong guarantees under other input models such as stochastic inputs, in order to achieve robust guarantees against a variety of inputs. To that end, we study the PACE (Pacing According to Current Estimated utility) algorithm, an existing algorithm designed for stochastic input. We show that in the equal-budgets case, PACE is equivalent to an integral greedy algorithm. We go on to show that with natural restrictions on the adversarial input model, both the greedy allocation and PACE have asymptotically bounded multiplicative envy as well as competitive ratio for Nash welfare, with the multiplicative factors either constant or with optimal order dependence on the number of agents. This completes a best-of-many-worlds guarantee for PACE, since past work showed that PACE achieves guarantees for stationary and stochastic-but-non-stationary input models. 

   more » « less