# Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 51 references that are in the map.
- First posted on arXiv 6 Jul 2024.

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

- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [The Sample Complexity of Revenue Maximization](https://mlsanity.com/paper/1502.00963/) (2015)
- [Learning Prices for Repeated Auctions with Strategic Buyers](https://mlsanity.com/paper/1311.6838/) (2013)
- [Dynamic Incentive-aware Learning: Robust Pricing in Contextual Auctions](https://mlsanity.com/paper/2002.11137/) (2020)
- [Sample Complexity of Automated Mechanism Design](https://mlsanity.com/paper/1606.04145/) (2016)
- [Learning Optimal Reserve Price against Non-myopic Bidders](https://mlsanity.com/paper/1804.11060/) (2018)
- [Online Learning Demands in Max-min Fairness](https://mlsanity.com/paper/2012.08648/) (2020)
- [Sequential Mechanisms with ex-post Participation Guarantees](https://mlsanity.com/paper/1603.07229/) (2016)
- [Reserve Pricing in Repeated Second-Price Auctions with Strategic Bidders](https://mlsanity.com/paper/1906.09331/) (2019)

## Abstract (arXiv)

We study a multi-round mechanism design problem, where we interact with a set of agents over a sequence of rounds. We wish to design an incentive-compatible (IC) online learning scheme to maximize an application-specific objective within a given class of mechanisms, without prior knowledge of the agents' type distributions. Even if each mechanism in this class is IC in a single round, if an algorithm naively chooses from this class on each round, the entire learning process may not be IC against non-myopic buyers who appear over multiple rounds. On each round, our method randomly chooses between the recommendation of a weakly differentially private online learning algorithm (e.g., Hedge), and a commitment mechanism which penalizes non-truthful behavior. Our method is IC and achieves O(T^frac1+h2) regret for the application-specific objective in an adversarial setting, where h quantifies the long-sightedness of the agents. When compared to prior work, our approach is conceptually simpler,it applies to general mechanism design problems (beyond auctions), and its regret scales gracefully with the size of the mechanism class.