Mechanism Design for Delagated Resource Allocation
Abstract
We study delegation in resource allocation. Specifically, we study a problem in which agents do not participate directly in a mechanism. Instead, each agent has a representative (who represents potentially many agents) that participates in the mechanism on their behalf. The mechanism decides on an allocation of items for each representative, which the representative then splits among the agents it represents in a way that maximizes some p-mean objective (e.g., maximizes the minimum utility/egalitarian welfare, the social welfare, or the geometric mean/Nash welfare). We are motivated by numerous real-world scenarios, e.g., how Feeding America allocates food to food-insecure individuals, where the representatives are the food banks, bidding in Feeding America's so-called Choice System.
Our contribution: We focus on the case where the mechanism is an auction with artificial currency, and the amount of currency each representative gets is proportional to the number of agents it represents. We analyze the behavior of each auction at the worst-case Nash equilibrium, with respect to the optimal (global) p-mean objective.
We prove that the trading post mechanism, which fractionally splits each item j among the agents that bid for it in a proportional manner, coupled with an all-pay payment rule, achieves a good price of anarchy, under a low-rank/incoherence assumption, for all p-mean objectives simultaneously (Thm 1). For the notable case of Nash welfare, the low-rank/incoherence assumption is not necessary. However, for the case of egalitarian welfare and social welfare, we prove that the low-rank/incoherence assumption is necessary (Thm 2). Next, we show that the first price auction, a very popular auction format, and the current auction Feeding America runs, has a terrible price of anarchy, even with the aforementioned incoherence assumption, for all p-mean objectives (Thm 3).
Our contribution: We focus on the case where the mechanism is an auction with artificial currency, and the amount of currency each representative gets is proportional to the number of agents it represents. We analyze the behavior of each auction at the worst-case Nash equilibrium, with respect to the optimal (global) p-mean objective.
We prove that the trading post mechanism, which fractionally splits each item j among the agents that bid for it in a proportional manner, coupled with an all-pay payment rule, achieves a good price of anarchy, under a low-rank/incoherence assumption, for all p-mean objectives simultaneously (Thm 1). For the notable case of Nash welfare, the low-rank/incoherence assumption is not necessary. However, for the case of egalitarian welfare and social welfare, we prove that the low-rank/incoherence assumption is necessary (Thm 2). Next, we show that the first price auction, a very popular auction format, and the current auction Feeding America runs, has a terrible price of anarchy, even with the aforementioned incoherence assumption, for all p-mean objectives (Thm 3).
