Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations
59
0
0.0
(
0
)
Added by
Siddharth Barman
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We develop polynomial-time algorithms for the fair and efficient allocation of indivisible goods among $n$ agents that have subadditive valuations over the goods. We first consider the Nash social welfare as our objective and design a polynomial-time algorithm that, in the value oracle model, finds an $8n$-approximation to the Nash optimal allocation. Subadditive valuations include XOS (fractionally subadditive) and submodular valuations as special cases. Our result, even for the special case of submodular valuations, improves upon the previously best known $O(n log n)$-approximation ratio of Garg et al. (2020). More generally, we study maximization of $p$-mean welfare. The $p$-mean welfare is parameterized by an exponent term $p in (-infty, 1]$ and encompasses a range of welfare functions, such as social welfare ($p = 1$), Nash social welfare ($p to 0$), and egalitarian welfare ($p to -infty$). We give an algorithm that, for subadditive valuations and any given $p in (-infty, 1]$, computes (in the value oracle model and in polynomial time) an allocation with $p$-mean welfare at least $frac{1}{8n}$ times the optimal. Further, we show that our approximation guarantees are essentially tight for XOS and, hence, subadditive valuations. We adapt a result of Dobzinski et al. (2010) to show that, under XOS valuations, an $O left(n^{1-varepsilon} right)$ approximation for the $p$-mean welfare for any $p in (-infty,1]$ (including the Nash social welfare) requires exponentially many value queries; here, $varepsilon>0$ is any fixed constant.
rate research
Read More
We consider the problem of approximating maximum Nash social welfare (NSW) while allocating a set of indivisible items to $n$ agents. The NSW is a popular objective that provides a balanced tradeoff between the often conflicting requirements of fairness and efficiency, defined as the weighted geometric mean of agents valuations. For the symmetric additive case of the problem, where agents have the same weight with additive valuations, the first constant-factor approximation algorithm was obtained in 2015. This led to a flurry of work obtaining constant-factor approximation algorithms for the symmetric case under mild generalizations of additive, and $O(n)$-approximation algorithms for more general valuations and for the asymmetric case. In this paper, we make significant progress towards both symmetric and asymmetric NSW problems. We present the first constant-factor approximation algorithm for the symmetric case under Rado valuations. Rado valuations form a general class of valuation functions that arise from maximum cost independent matching problems, including as special cases assignment (OXS) valuations and weighted matroid rank functions. Furthermore, our approach also gives the first constant-factor approximation algorithm for the asymmetric case under Rado valuations, provided that the maximum ratio between the weights is bounded by a constant.
Approximating the optimal social welfare while preserving truthfulness is a well studied problem in algorithmic mechanism design. Assuming that the social welfare of a given mechanism design problem can be optimized by an integer program whose integrality gap is at most $alpha$, Lavi and Swamy~cite{Lavi11} propose a general approach to designing a randomized $alpha$-approximation mechanism which is truthful in expectation. Their method is based on decomposing an optimal solution for the relaxed linear program into a convex combination of integer solutions. Unfortunately, Lavi and Swamys decomposition technique relies heavily on the ellipsoid method, which is notorious for its poor practical performance. To overcome this problem, we present an alternative decomposition technique which yields an $alpha(1 + epsilon)$ approximation and only requires a quadratic number of calls to an integrality gap verifier.
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al.~cite{dasgupta2020explainable}. Specifically, we focus on the $k$-means and $k$-medians problems and provide nearly tight upper and lower bounds. First, we provide an $O(log k log log k)$-approximation algorithm for explainable $k$-medians, improving on the best known algorithm of $O(k)$~cite{dasgupta2020explainable} and nearly matching the known $Omega(log k)$ lower bound~cite{dasgupta2020explainable}. In addition, in low-dimensional spaces $d ll log k$, we show that our algorithm also provides an $O(d log^2 d)$-approximate solution for explainable $k$-medians. This improves over the best known bound of $O(d log k)$ for low dimensions~cite{laber2021explainable}, and is a constant for constant dimensional spaces. To complement this, we show a nearly matching $Omega(d)$ lower bound. Next, we study the $k$-means problem in this context and provide an $O(k log k)$-approximation algorithm for explainable $k$-means, improving over the $O(k^2)$ bound of Dasgupta et al. and the $O(d k log k)$ bound of cite{laber2021explainable}. To complement this we provide an almost tight $Omega(k)$ lower bound, improving over the $Omega(log k)$ lower bound of Dasgupta et al. Given an approximate solution to the classic $k$-means and $k$-medians, our algorithm for $k$-medians runs in time $O(kd log^2 k )$ and our algorithm for $k$-means runs in time $ O(k^2 d)$.
Recently Cole and Gkatzelis gave the first constant factor approximation algorithm for the problem of allocating indivisible items to agents, under additive valuations, so as to maximize the Nash Social Welfare. We give constant factor algorithms for a substantial generalization of their problem -- to the case of separable, piecewise-linear concave utility functions. We give two such algorithms, the first using market equilibria and the second using the theory of stable polynomials. In AGT, there is a paucity of methods for the design of mechanisms for the allocation of indivisible goods and the result of Cole and Gkatzelis seemed to be taking a major step towards filling this gap. Our result can be seen as another step in this direction.
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of $n$ agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into $n$ bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. In settings with indivisible goods, such allocations are not guaranteed to exist, so we resort to approximation algorithms. Our main result is a $2/3$-approximation, that runs in polynomial time for any number of agents. This improves upon the algorithm of Procaccia and Wang, which also produces a $2/3$-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of their algorithm. Furthermore, motivated by the apparent difficulty, both theoretically and experimentally, in finding lower bounds on the existence of approximate solutions, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in relevant works. Finally, we provide further positive results for two special cases that arise from previous works. The first one is the intriguing case of $3$ agents, for which it is already known that exact maximin share allocations do not always exist (contrary to the case of $2$ agents). We provide a $7/8$-approximation algorithm, improving the previously known result of $3/4$. The second case is when all item values belong to ${0, 1, 2}$, extending the ${0, 1}$ setting studied in Bouveret and Lema^itre. We obtain an exact algorithm for any number of agents in this case.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
