Optimal Anonymous Independent Reward Scheme Design
Abstract
We consider designing reward schemes that incentivize agents to create high-quality content (e.g., videos, images, text, ideas). The problem is at the center of a real-world application where the goal is to optimize the overall quality of generated content on user-generated content platforms. We focus on anonymous independent reward schemes (AIRS) that only take the quality of an agent's content as input. We prove the general problem is NP-hard. If the cost function is convex, we show the optimal AIRS can be formulated as a convex optimization problem and propose an efficient algorithm to solve it. Next, we explore the optimal linear reward scheme and prove it has a 1/2-approximation ratio, and the ratio is tight. Lastly, we show the proportional scheme can be arbitrarily bad compared to AIRS.
Cite
Text
Chen et al. "Optimal Anonymous Independent Reward Scheme Design." International Joint Conference on Artificial Intelligence, 2022. doi:10.24963/IJCAI.2022/24Markdown
[Chen et al. "Optimal Anonymous Independent Reward Scheme Design." International Joint Conference on Artificial Intelligence, 2022.](https://mlanthology.org/ijcai/2022/chen2022ijcai-optimal/) doi:10.24963/IJCAI.2022/24BibTeX
@inproceedings{chen2022ijcai-optimal,
title = {{Optimal Anonymous Independent Reward Scheme Design}},
author = {Chen, Mengjing and Tang, Pingzhong and Wang, Zihe and Xiao, Shenke and Yang, Xiwang},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2022},
pages = {165-171},
doi = {10.24963/IJCAI.2022/24},
url = {https://mlanthology.org/ijcai/2022/chen2022ijcai-optimal/}
}