Incentive-Compatible Selection for One or Two Influentials

Incentive-Compatible Selection for One or Two Influentials

Yuxin Zhao, Yao Zhang, Dengji Zhao

Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2931-2938. https://doi.org/10.24963/ijcai.2023/327

Selecting influentials in networks against strategic manipulations has attracted many researchers' attention and it also has many practical applications. Here, we aim to select one or two influentials in terms of progeny (the influential power) and prevent agents from manipulating their edges (incentive compatibility). The existing studies mostly focused on selecting a single influential for this setting. Zhang et al. [2021] studied the problem of selecting one agent and proved an upper bound of 1/(1+ln2) to approximate the optimal selection. In this paper, we first design a mechanism to actually reach the bound. Then, we move this forward to choosing two agents and propose a mechanism to achieve an approximation ratio of (3+ln2)/(4(1+ln2)) (approx. 0.54).
Keywords:
Game Theory and Economic Paradigms: GTEP: Mechanism design