Optimal Anonymous Independent Reward Scheme Design

Mengjing Chen; Pingzhong Tang; Zihe Wang; Shenke Xiao; Xiwang Yang

IJCAI 2022poster2 citations

Optimal Anonymous Independent Reward Scheme Design

Mengjing Chen, Pingzhong Tang, Zihe Wang, Shenke Xiao, Xiwang Yang

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.

Agent-based and Multi-agent Systems: Algorithmic Game Theory

BibTeX

@inproceedings{ijcai2022p24,
  title     = {Optimal Anonymous Independent Reward Scheme Design},
  author    = {Chen, Mengjing and Tang, Pingzhong and Wang, Zihe and Xiao, Shenke and Yang, Xiwang},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Lud De Raedt},
  pages     = {165--171},
  year      = {2022},
  month     = {7},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2022/24},
  url       = {https://doi.org/10.24963/ijcai.2022/24},
}