Research map / Learning theory and algorithms / Submodular and game algorithms
Fair Allocation in Dynamic Mechanism Design
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Characterizes revenue-maximizing dynamic auctions that satisfy group-wise minimum average allocation constraints, via backward induction over residual allocations, and gives approximation schemes.
Problem
Revenue-maximizing repeated auction of an indivisible good to two buyer groups under a discounted minimum-allocation fairness constraint, with strategic (truthful-incentive) buyers over T rounds.
Approach
Static optimal fair mechanism is a virtual-value subsidy rule; in the dynamic case, backward induction over residual minimum allocations yields recursive value functions, with a participation bonus and entry fee ensuring truthfulness, and an oracle-based approximation scheme.
Key results
- Static optimal fair allocation subsidizes the under-allocated group via a virtual-value shift gamma and reserve reductions eta1, eta2 (Theorem 1, Proposition 2).
- Dynamic optimal mechanism includes a participation bonus and entry fee; the expected deficit of bonuses over entry fees is O(1/n) (Proposition 4).
- Approximation scheme with O(eps^{-1/log(1/delta)}) oracle calls gives fairness (1-eps)(alpha_i-eps) with seller utility at least the optimum; exact computation for delta=1 needs O(T^2) oracle calls (Fact 3, Proposition 5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the fairness constraints after they begin to bind | Optimal fair allocation · Numerical experiment, T = 2, 3, 4 | seller utility | Hurt |
| Increase α2 while holding α1 fixed | Optimal fair allocation · Numerical experiment, group one | buyer utility | Hurt |
| Increase α1 while holding α2 fixed | Optimal fair allocation · Numerical experiment, group two | buyer utility | No clear effect |
| Increase the number of buyers | Dynamic fair mechanism · Dynamic auction | participation bonuses minus entry fees: O(1/n) | Helped |
Surprising findings
- The expected utility of a buyer can decrease as their group's fairness constraint increases, so net utility of not winning can be negative (Remark 1).
- With few buyers (n=1) the seller may have to pay participation bonuses out of pocket since entry fees are zero.
Limitations
- Exact dynamic solution has computational complexity growing exponentially in T for delta<1.
- Assumes regular value distributions (relaxed only via ironing in appendix) and requires an integral oracle in approximation schemes.
- Numerical experiments are limited to n=1, T up to 4, and uniform distributions.
Experimental setup
Metrics: seller utility difference relative to unconstrained optimum buyer group utility difference
Baselines: unconstrained optimal (second-price with reserve) allocation
Builds on: Myerson optimal auction Vickrey second-price auction with reserve Pai and Vohra fair mechanism design
Closest papers by meaning
- Robust Pricing in Dynamic Mechanism Design (ICML 2020 · similarity 0.89)
- Computational Dynamic Mechanism Design (NeurIPS 2026 · similarity 0.88)
- A Unified Framework for Uniform-Price Resource Allocation Mechanisms (NeurIPS 2026 · similarity 0.87)
- On the Power of Randomization for Obviously Strategy-Proof Mechanisms (AAAI 2025 · similarity 0.87)
- Mechanism Design via the Interim Relaxation (NeurIPS 2025 · similarity 0.86)
- Double Auction on Diffusion Network (AAAI 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.