Incentive-Compatible Selection for One or Two Influentials
Abstract
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).
Cite
Text
Zhao et al. "Incentive-Compatible Selection for One or Two Influentials." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/327Markdown
[Zhao et al. "Incentive-Compatible Selection for One or Two Influentials." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/zhao2023ijcai-incentive/) doi:10.24963/IJCAI.2023/327BibTeX
@inproceedings{zhao2023ijcai-incentive,
title = {{Incentive-Compatible Selection for One or Two Influentials}},
author = {Zhao, Yuxin and Zhang, Yao and Zhao, Dengji},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {2931-2938},
doi = {10.24963/IJCAI.2023/327},
url = {https://mlanthology.org/ijcai/2023/zhao2023ijcai-incentive/}
}