# Socially-Optimal Mechanism Design for Incentivized Online Learning

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 35 references that are in the map.
- First posted on arXiv 29 Dec 2021.

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

- [Combinatorial Sleeping Bandits with Fairness Constraints](https://mlsanity.com/paper/1901.04891/) (2019)
- [Multi-armed Bandits with Compensation](https://mlsanity.com/paper/1811.01715/) (2018)
- [Fairness Incentives for Myopic Agents](https://mlsanity.com/paper/1705.02321/) (2017)
- [Context-Aware Hierarchical Online Learning for Performance Maximization in Mobile Crowdsourcing](https://mlsanity.com/paper/1705.03822/) (2017)
- [Cooperative Edge Caching in User-Centric Clustered Mobile Networks](https://mlsanity.com/paper/1710.08582/) (2017)
- [Spectrum Sharing for Internet of Things: A Survey](https://mlsanity.com/paper/1810.04408/) (2018)
- [Providing Long-Term Participation Incentive in Participatory Sensing](https://mlsanity.com/paper/1501.02480/) (2015)
- [Air-Ground Integrated Vehicular Network Slicing with Content Pushing and Caching](https://mlsanity.com/paper/1806.03860/) (2018)
- [Incentivized Bandit Learning with Self-Reinforcing User Preferences](https://mlsanity.com/paper/2105.08869/) (2021)
- [An Online Approach to Dynamic Channel Access and Transmission Scheduling](https://mlsanity.com/paper/1504.01050/) (2015)

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

- [Repeated Principal-Agent Games with Unobserved Agent Rewards and Perfect-Knowledge Agents](https://mlsanity.com/paper/2304.07407/) (2023)
- [Estimating and Incentivizing Imperfect-Knowledge Agents with Hidden Rewards](https://mlsanity.com/paper/2308.06717/) (2023)

## Abstract (arXiv)

Multi-arm bandit (MAB) is a classic online learning framework that studies the sequential decision-making in an uncertain environment. The MAB framework, however, overlooks the scenario where the decision-maker cannot take actions (e.g., pulling arms) directly. It is a practically important scenario in many applications such as spectrum sharing, crowdsensing, and edge computing. In these applications, the decision-maker would incentivize other selfish agents to carry out desired actions (i.e., pulling arms on the decision-maker's behalf). This paper establishes the incentivized online learning (IOL) framework for this scenario. The key challenge to design the IOL framework lies in the tight coupling of the unknown environment learning and asymmetric information revelation. To address this, we construct a special Lagrangian function based on which we propose a socially-optimal mechanism for the IOL framework. Our mechanism satisfies various desirable properties such as agent fairness, incentive compatibility, and voluntary participation. It achieves the same asymptotic performance as the state-of-art benchmark that requires extra information. Our analysis also unveils the power of crowd in the IOL framework: a larger agent crowd enables our mechanism to approach more closely the theoretical upper bound of social performance. Numerical results demonstrate the advantages of our mechanism in large-scale edge computing.