Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBudget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free
144
0
0.0
(
0
)
Added by
Xiaowei Wu
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
Incentive compatibility (IC) is one of the most fundamental properties of an auction mechanism, including those used for online advertising. Recent methods by Feng et al. and Lahaie et al. show that counterfactual runs of the auction mechanism with different bids can be used to determine whether an auction is IC. In this paper we show that a similar result can be obtained by looking at the advertisers envy, which can be computed with one single execution of the auction. We introduce two metrics to evaluate the incentive-compatibility of an auction: IC-Regret and IC-Envy. For position auction environments, we show that for a large class of pricing schemes (which includes e.g. VCG and GSP), IC-Envy $ge$ IC-Regret (and IC-Envy = IC-Regret when bids are distinct). We consider non-separable discounts in the Ad Types environment of Colini-Baldeschi et al. where we show that for a generalization of GSP also IC-Envy $ge$ IC-Regret. Our final theoretical result is that in all these settings IC-Envy be used to bound the loss in social welfare due advertiser misreports. Finally, we show that IC-Envy is useful as a feature to predict IC-Regret in auction environments beyond the ones for which we show theoretical results. In particular, using IC-Envy yields better results than training models using only price and value features.
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.
We consider the problem of allocating a set of divisible goods to $N$ agents in an online manner, aiming to maximize the Nash social welfare, a widely studied objective which provides a balance between fairness and efficiency. The goods arrive in a sequence of $T$ periods and the value of each agent for a good is adversarially chosen when the good arrives. We first observe that no online algorithm can achieve a competitive ratio better than the trivial $O(N)$, unless it is given additional information about the agents values. Then, in line with the emerging area of algorithms with predictions, we consider a setting where for each agent, the online algorithm is only given a prediction of her monopolist utility, i.e., her utility if all goods were given to her alone (corresponding to the sum of her values over the $T$ periods). Our main result is an online algorithm whose competitive ratio is parameterized by the multiplicative errors in these predictions. The algorithm achieves a competitive ratio of $O(log N)$ and $O(log T)$ if the predictions are perfectly accurate. Moreover, the competitive ratio degrades smoothly with the errors in the predictions, and is surprisingly robust: the logarithmic competitive ratio holds even if the predictions are very inaccurate. We complement this positive result by showing that our bounds are essentially tight: no online algorithm, even if provided with perfectly accurate predictions, can achieve a competitive ratio of $O(log^{1-epsilon} N)$ or $O(log^{1-epsilon} T)$ for any constant $epsilon>0$.
We study a participatory budgeting problem of aggregating the preferences of agents and dividing a budget over the projects. A budget division solution is a probability distribution over the projects. The main purpose of our study concerns the comparison between the system optimum solution and a fair solution. We are interested in assessing the quality of fair solutions, i.e., in measuring the system efficiency loss under a fair allocation compared to the one that maximizes (egalitarian) social welfare. This indicator is called the price of fairness. We are also interested in the performance of several aggregation rules. Asymptotically tight bounds are provided both for the price of fairness and the efficiency guarantee of aggregation rules.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
