# Adaptive maximization of social welfare

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 65 references that are in the map.
- First posted on arXiv 14 Oct 2023.

## Builds on (most cited first, 19 of 19)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Online learning in repeated auctions](https://mlsanity.com/paper/1511.05720/) (2015)
- [Learning to Bid Without Knowing your Value](https://mlsanity.com/paper/1711.01333/) (2017)
- [Optimal No-regret Learning in Repeated First-price Auctions](https://mlsanity.com/paper/2003.09795/) (2020)
- [Learning to Bid Optimally and Efficiently in Adversarial First-price Auctions](https://mlsanity.com/paper/2007.04568/) (2020)
- [Bilateral Trade: A Regret Minimization Perspective](https://mlsanity.com/paper/2109.12974/) (2021)
- [Learning in Auctions: Regret is Hard, Envy is Easy](https://mlsanity.com/paper/1511.01411/) (2015)
- [Auctions Between Regret-Minimizing Agents](https://mlsanity.com/paper/2110.11855/) (2021)
- [Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics](https://mlsanity.com/paper/2301.13306/) (2023)
- [A Regret Analysis of Bilateral Trade](https://mlsanity.com/paper/2102.08754/) (2021)
- [Learning in repeated auctions](https://mlsanity.com/paper/2011.09365/) (2020)
- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations](https://mlsanity.com/paper/2307.09478/) (2023)
- [Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions](https://mlsanity.com/paper/2009.06136/) (2020)
- [Fast Rate Learning in Stochastic First Price Bidding](https://mlsanity.com/paper/2107.01835/) (2021)
- [A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex Optimization](https://mlsanity.com/paper/2208.06720/) (2022)
- [Regret Analysis of Dyadic Search](https://mlsanity.com/paper/2209.00885/) (2022)

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

- [Market Making without Regret](https://mlsanity.com/paper/2411.13993/) (2024)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)

## Abstract (arXiv)

We consider the problem of repeatedly choosing policies to maximize social welfare. Welfare is a weighted sum of private utility and public revenue. Earlier outcomes inform later policies. Utility is not observed, but indirectly inferred. Response functions are learned through experimentation. We derive a lower bound on regret, and a matching adversarial upper bound for a variant of the Exp3 algorithm. Cumulative regret grows at a rate of T2/3. This implies that (i) welfare maximization is harder than the multi-armed bandit problem (with a rate of T1/2 for finite policy sets), and (ii) our algorithm achieves the optimal rate. For the stochastic setting, if social welfare is concave, we can achieve a rate of T1/2 (for continuous policy sets), using a dyadic search algorithm. We analyze an extension to nonlinear income taxation, and sketch an extension to commodity taxation. We compare our setting to monopoly pricing (which is easier), and price setting for bilateral trade (which is harder).