More Like this

1. Approximation Algorithms for the Weighted Nash Social Welfare via Convex and Non-Convex Programs

   Brown, A; Laddha, A; Pittu M; Singh, M. (January 2024, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   In an instance of the weighted Nash Social Welfare problem, we are given a set of m indivisible items, G, and n agents, A, where each agent i in A has a valuation v_ij ≥ 0 for each item j in G. In addition, every agent i has a non-negative weight w_i such that the weights collectively sum up to 1. The goal is to find an assignment of items to players that maximizes the weighted geometric mean of the valuation received by the players. When all the weights are equal, the problem reduces to the classical Nash Social Welfare problem, which has recently received much attention. In this work, we present an approximation algorithm whose approximation depends on the KL-divergence between the weight distribution and the uniform distribution. We generalize the convex programming relaxations for the symmetric variant of Nash Social Welfare presented in [CDG+17, AGSS17] to two different mathematical programs. The first program is convex and is necessary for computational efficiency, while the second program is a non-convex relaxation that can be rounded efficiently. The approximation factor derives from the difference in the objective values of the convex and non-convex relaxation. 

   more » « less
2. The Degree of Fairness in Efficient House Allocation

   https://doi.org/10.3233/FAIA240920  

   Hosseini, Hadi; Kumar, Medha; Roy, Sanjukta (October 2024, IOS Press)

   The classic house allocation problem is primarily concerned with finding a matching between a set of agents and a set of houses that guarantees some notion of economic efficiency (e.g. utilitarian welfare). While recent works have shifted focus on achieving fairness (e.g. minimizing the number of envious agents), they often come with notable costs on efficiency notions such as utilitarian or egalitarian welfare. We investigate the trade-offs between these welfare measures and several natural fairness measures that rely on the number of envious agents, the total (aggregate) envy of all agents, and maximum total envy of an agent. In particular, by focusing on envy-free allocations, we first show that, should one exist, finding an envy-free allocation with maximum utilitarian or egalitarian welfare is computationally tractable. We highlight a rather stark contrast between utilitarian and egalitarian welfare by showing that finding utilitarian welfare maximizing allocations that minimize the aforementioned fairness measures can be done in polynomial time while their egalitarian counterparts remain intractable (for the most part) even under binary valuations. We complement our theoretical findings by giving insights into the relationship between the different fairness measures and by conducting empirical analysis. 

   more » « less
3. Computing welfare-Maximizing fair allocations of indivisible goods

   https://doi.org/10.1016/j.ejor.2022.10.013  

   Aziz, Haris; Huang, Xin; Mattei, Nicholas; Segal-Halevi, Erel (January 2022, European journal of operational research)

   We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents’ utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx). 

   more » « less
4. A General Framework for Fair Allocation under Matroid Rank Valuations

   https://doi.org/10.1145/3728367  

   Viswanathan, Vignesh; Zick, Yair (April 2025, ACM Transactions on Economics and Computation)

   We study the problem of fairly allocating a set of indivisible goods among agents with matroid rank valuations: every good provides a marginal value of 0 or 1 when added to a bundle and valuations are submodular.We present a simple algorithmic framework, calledGeneral Yankee Swap, that can efficiently compute allocations that maximize any justice criterion (or fairness objective) satisfying some mild assumptions. Along with maximizing a justice criterion, General Yankee Swap is guaranteed to maximize utilitarian social welfare, ensure strategyproofness and use at most a quadratic number of valuation queries. We show how General Yankee Swap can be used to compute allocations for five different well-studied justice criteria: (a) Prioritized Lorenz dominance, (b) Maximin fairness, (c) Weighted leximin, (d) Max weighted Nash welfare, and (e) Max weightedp-mean welfare.In particular, this framework provides the first polynomial time algorithms to compute weighted leximin, max weighted Nash welfare and max weightedp-mean welfare allocations for agents with matroid rank valuations. We also extend this framework to the setting of binary chores — items with marginal values -1 or 0 — and similarly show that it can be used to maximize any justice criteria satisfying some mild assumptions. 

   more » « less
5. Minimum Wages, Efficiency, and Welfare

   https://doi.org/10.3982/ECTA21466  

   Berger, David; Herkenhoff, Kyle; Mongey, Simon (January 2025, Econometrica)

   Many argue that minimum wages can prevent efficiency losses from monopsony power. We assess this argument in a general equilibrium model of oligopsonistic labor markets with heterogeneous workers and firms. We decompose welfare gains into anefficiencycomponent that captures reductions in monopsony power and aredistributivecomponent that captures the way minimum wages shift resources across people. The minimum wage that maximizes the efficiency component of welfare lies below $8.00 and yields gains worth less than 0.2% of lifetime consumption. When we add back in Utilitarian redistributive motives, the optimal minimum wage is $11 and redistribution accounts for 102.5% of the resulting welfare gains, implying offsetting efficiency losses of −2.5%. The reason a minimum wage struggles to deliver efficiency gains is that with realistic firm productivity dispersion, a minimum wage that eliminates monopsony power at one firm causes severe rationing at another. These results hold under an EITC and progressive labor income taxes calibrated to the U.S. economy. 

   more » « less