# Fair Allocation in Dynamic Mechanism Design

arXiv: https://arxiv.org/abs/2406.00147 · HTML: https://mlsanity.com/paper/2406.00147/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 78 references that are in the map.
- First posted on arXiv 31 May 2024.

## Builds on (most cited first, 30 of 34)

- [Bridging Machine Learning and Mechanism Design towards Algorithmic Fairness](https://mlsanity.com/paper/2010.05434/) (2020)
- [Fair Algorithms for Learning in Allocation Problems](https://mlsanity.com/paper/1808.10549/) (2018)
- [Fair Public Decision Making](https://mlsanity.com/paper/1611.04034/) (2016)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [Online Fair Division: analysing a Food Bank problem](https://mlsanity.com/paper/1502.07571/) (2015)
- [ProportionNet: Balancing Fairness and Revenue for Auction Design with Deep Learning](https://mlsanity.com/paper/2010.06398/) (2020)
- [Fair Dynamic Rationing](https://mlsanity.com/paper/2102.01240/) (2021)
- [Fairness and Utilization in Allocating Resources with Uncertain Demand](https://mlsanity.com/paper/1906.09050/) (2019)
- [Online Fair Division: A Survey](https://mlsanity.com/paper/1911.09488/) (2019)
- [Sequential Fair Allocation: Achieving the Optimal Envy-Efficiency Tradeoff Curve](https://mlsanity.com/paper/2105.05308/) (2021)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Fairness-Efficiency Tradeoffs in Dynamic Fair Division](https://mlsanity.com/paper/1907.11672/) (2019)
- [Democratic Fair Allocation of Indivisible Goods](https://mlsanity.com/paper/1709.02564/) (2017)
- [Best-of-Both-Worlds Fair-Share Allocations](https://mlsanity.com/paper/2102.04909/) (2021)
- [Fair Assortment Planning](https://mlsanity.com/paper/2208.07341/) (2022)
- [Comparing Approximate Relaxations of Envy-Freeness](https://mlsanity.com/paper/1806.03114/) (2018)
- [Fair and Efficient Online Allocations with Normalized Valuations](https://mlsanity.com/paper/2009.12405/) (2020)
- [On Truthful Mechanisms for Maximin Share Allocations](https://mlsanity.com/paper/1605.04026/) (2016)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Almost Group Envy-free Allocation of Indivisible Goods and Chores](https://mlsanity.com/paper/1907.09279/) (2019)
- [Individual Fairness in Advertising Auctions through Inverse Proportionality](https://mlsanity.com/paper/2003.13966/) (2020)
- [Truthful Allocation Mechanisms Without Payments: Characterization and Implications on Fairness](https://mlsanity.com/paper/1705.10706/) (2017)
- [Fair Division: The Computer Scientist's Perspective](https://mlsanity.com/paper/2005.04855/) (2020)
- [Fair-Share Allocations for Agents with Arbitrary Entitlements](https://mlsanity.com/paper/2103.04304/) (2021)
- [Weighted Fairness Notions for Indivisible Items Revisited](https://mlsanity.com/paper/2112.04166/) (2021)
- [Asymptotic Existence of Fair Divisions for Groups](https://mlsanity.com/paper/1706.08219/) (2017)
- [Diversity-Preserving K-Armed Bandits, Revisited](https://mlsanity.com/paper/2010.01874/) (2020)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [New Fairness Concepts for Allocating Indivisible Items](https://mlsanity.com/paper/2206.01710/) (2022)
- [Fair Division via Quantile Shares](https://mlsanity.com/paper/2312.01874/) (2023)

## Built on by (most cited first, 1 of 1)

- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)

## Abstract (arXiv)

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.