Fair Allocation in Dynamic Mechanism Design

• URL: http://arxiv.org/abs/2406.00147v3
• Date: Thu, 03 Oct 2024 17:05:51 GMT
• Title: Fair Allocation in Dynamic Mechanism Design
• Authors: Alireza Fallah, Michael I. Jordan, Annie Ulichney,
• Abstract summary: We consider a problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group.
• Score: 57.66441610380448
• License:
• Abstract: We consider a dynamic mechanism design problem where an auctioneer sells an indivisible good to groups of buyers in every round, for a total of $T$ rounds. The auctioneer aims to maximize their discounted overall revenue while adhering to a fairness constraint that guarantees a minimum average allocation for each group. We begin by studying the static case ($T=1$) and establish that the optimal mechanism involves two types of subsidization: one that increases the overall probability of allocation to all buyers, and another that favors the groups which otherwise have a lower probability of winning the item. We then extend our results to the dynamic case by characterizing a set of recursive functions that determine the optimal allocation and payments in each round. Notably, our results establish that in the dynamic case, the seller, on the one hand, commits to a participation bonus to incentivize truth-telling, and on the other hand, charges an entry fee for every round. Moreover, the optimal allocation once more involves subsidization, which its extent depends on the difference in future utilities for both the seller and buyers when allocating the item to one group versus the others. Finally, we present an approximation scheme to solve the recursive equations and determine an approximately optimal and fair allocation efficiently.

Related papers

• Online Fair Allocation of Perishable Resources [1.4952056744888913]
  We consider a practically motivated variant of the canonical online fair allocation problem. A decision-maker has a budget of perishable resources to allocate over a fixed number of rounds. The goal is to construct a sequence of allocations that is envy-free and efficient.
  arXiv  Detail & Related papers  (2024-06-04T15:14:10Z)
• Sampling Individually-Fair Rankings that are Always Group Fair [9.333939443470944]
  A fair ranking task asks to rank a set of items to maximize utility subject to satisfying group-fairness constraints. Recent works identify uncertainty in the utilities of items as a primary cause of unfairness. We give an efficient algorithm that samples rankings from an individually-fair distribution while ensuring that every output ranking is group fair.
  arXiv  Detail & Related papers  (2023-06-21T01:26:34Z)
• Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics [53.62091043347035]
  We study a game between autobidding algorithms that compete in an online advertising platform. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret.
  arXiv  Detail & Related papers  (2023-01-30T21:59:30Z)
• Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
  An auction mechanism that maximizes the auctioneer's revenue while minimizes bidders' ex-post regret is an important yet intricate problem in economics. Remarkable progress has been achieved through learning the optimal auction mechanism by neural networks.
  arXiv  Detail & Related papers  (2022-10-11T16:13:25Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  We consider a multi-armed bandit setting where, at the beginning of each round, the learner receives noisy independent evaluations of the true reward of each arm. We derive different algorithmic approaches and theoretical guarantees depending on how the evaluations are generated.
  arXiv  Detail & Related papers  (2021-12-13T09:48:54Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  We study a multi-round welfare-maximising mechanism design problem in instances where agents do not know their values. We first define three notions of regret for the welfare, the individual utilities of each agent and that of the mechanism. Our framework also provides flexibility to control the pricing scheme so as to trade-off between the agent and seller regrets.
  arXiv  Detail & Related papers  (2020-04-19T18:00:58Z)
• Individual Fairness in Advertising Auctions through Inverse Proportionality [12.861470300253329]
  We study the design of ad auctions that, given fair bids, are guaranteed to produce fair outcomes. We introduce a new class of allocation algorithms that achieve a tradeoff between fairness and social welfare.
  arXiv  Detail & Related papers  (2020-03-31T06:10:07Z)
• Generalization Guarantees for Multi-item Profit Maximization: Pricing, Auctions, and Randomized Mechanisms [86.81403511861788]
  We study multi-item profit when there is an underlying distribution over buyers' values. For any set of buyers' values, profit is piecewise linear in the mechanism's parameters. We prove new bounds for mechanism classes not yet in the sample-based mechanism design literature.
  arXiv  Detail & Related papers  (2017-04-29T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.