 Award ID(s):
 1637418
 NSFPAR ID:
 10139078
 Date Published:
 Journal Name:
 Web and Internet Economics
 Page Range / eLocation ID:
 340
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

We consider the problem of allocating divisible items among multiple agents, and consider the setting where any agent is allowed to introduce {\emph diversity constraints} on the items they are allocated. We motivate this via settings where the items themselves correspond to user ad slots or task workers with attributes such as race and gender on which the principal seeks to achieve demographic parity. We consider the following question: When an agent expresses diversity constraints into an allocation rule, is the allocation of other agents hurt significantly? If this happens, the cost of introducing such constraints is disproportionately borne by agents who do not benefit from diversity. We codify this via two desiderata capturing {\em robustness}. These are {\emph no negative externality}  other agents are not hurt  and {\emph monotonicity}  the agent enforcing the constraint does not see a large increase in value. We show in a formal sense that the Nash Welfare rule that maximizes product of agent values is {\emph uniquely} positioned to be robust when diversity constraints are introduced, while almost all other natural allocation rules fail this criterion. We also show that the guarantees achieved by Nash Welfare are nearly optimal within a widely studied class of allocation rules. We finally perform an empirical simulation on realworld data that models ad allocations to show that this gap between Nash Welfare and other rules persists in the wild.more » « less

null (Ed.)Mechanisms with money are commonly designed under the assumption that agents are quasilinear, meaning they have linear disutility for spending money. We study the implications when agents with nonlinear (specifically, convex) disutility for payments participate in mechanisms designed for quasilinear agents. We first show that any mechanism that is truthful for quasilinear buyers has a simple best response function for buyers with nonlinear disutility from payments, in which each bidder simply scales down her value for each potential outcome by a fixed factor, equal to her target return on investment (ROI). We call such a strategy ROIoptimal. We prove the existence of a Nash equilibrium in which agents use ROIoptimal strategies for a general class of allocation problems. Motivated by online marketplaces, we then focus on simultaneous secondprice auctions for additive bidders and show that all ROIoptimal equilibria in this setting achieve constantfactor approximations to suitable welfare and revenue benchmarks.more » « less

A public decisionmaking problem consists of a set of issues, each with multiple possible alternatives, and a set of competing agents, each with a preferred alternative for each issue. We study adaptations of market economies to this setting, focusing on binary issues. Issues have prices, and each agent is endowed with artificial currency that she can use to purchase probability for her preferred alternatives (we allow randomized outcomes). We first show that when each issue has a single price that is common to all agents, market equilibria can be arbitrarily bad. This negative result motivates a different approach. We present a novel technique called "pairwise issue expansion", which transforms any public decisionmaking instance into an equivalent Fisher market, the simplest type of private goods market. This is done by expanding each issue into many goods: one for each pair of agents who disagree on that issue. We show that the equilibrium prices in the constructed Fisher market yield a "pairwise pricing equilibrium" in the original public decisionmaking problem which maximizes Nash welfare. More broadly, pairwise issue expansion uncovers a powerful connection between the public decisionmaking and private goods settings; this immediately yields several interesting results about public decisions markets, and furthers the hope that we will be able to find a simple iterative voting protocol that leads to nearoptimum decisions.more » « less

We study the problem of approximating maximum Nash social welfare (NSW) when allocating
m indivisible items amongn asymmetric agents with submodular valuations. TheNSW is a wellestablished notion of fairness and efficiency, defined as the weighted geometric mean of agentsâ€™ valuations. For special cases of the problem with symmetric agents and additive(like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with a factor independent ofm was known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations before this work.In this article, we extend our understanding of the
NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of highvalued items are done separately by unmatching certain items and rematching them by different processes in both algorithms. We show that these approaches achieve approximation factors ofO (n ) andO (n logn ) for additive and submodular cases, independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree up to one item (EF1 ).Furthermore, we show that the
NSW problem under submodular valuations is strictly harder than all currently known settings with an factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of\(\frac{\mathrm{e}}{\mathrm{e}1}\) , hence resolving it completely.\(\frac{\mathrm{e}}{\mathrm{e}1}\) 
We study the problem of approximating maximum Nash social welfare (NSW) when allocating m indivisible items among n asymmetric agents with submodular valuations. The NSW is a wellestablished notion of fairness and efficiency, defined as the weighted geometric mean of agents' valuations. For special cases of the problem with symmetric agents and additive(like) valuation functions, approximation algorithms have been designed using approaches customized for these specific settings, and they fail to extend to more general settings. Hence, no approximation algorithm with factor independent of m is known either for asymmetric agents with additive valuations or for symmetric agents beyond additive(like) valuations. In this paper, we extend our understanding of the NSW problem to far more general settings. Our main contribution is two approximation algorithms for asymmetric agents with additive and submodular valuations respectively. Both algorithms are simple to understand and involve nontrivial modifications of a greedy repeated matchings approach. Allocations of high valued items are done separately by unmatching certain items and rematching them, by processes that are different in both algorithms. We show that these approaches achieve approximation factors of O(n) and O(n log n) for additive and submodular case respectively, which is independent of the number of items. For additive valuations, our algorithm outputs an allocation that also achieves the fairness property of envyfree up to one item (EF1). Furthermore, we show that the NSW problem under submodular valuations is strictly harder than all currently known settings with an e/(e1) factor of the hardness of approximation, even for constantly many agents. For this case, we provide a different approximation algorithm that achieves a factor of e/(e1), hence resolving it completely.more » « less