Selecting the most influential agent in a network has huge practical value in applications. However, in many scenarios, the graph structure can only be known from agents' reports on their connections. In a self-interested setting, agents may strategically hide some connections to make themselves seem to be more important. In this paper, we study the incentive compatible (IC) selection mechanism to prevent such manipulations. Specifically, we model the progeny of an agent as her influence power, i.e., the number of nodes in the subgraph rooted at her. We then propose the Geometric Mechanism, which selects an agent with at least 1/2 of the optimal progeny in expectation under the properties of incentive compatibility and fairness. Fairness requires that two roots with the same contribution in two graphs are assigned the same probability. Furthermore, we prove an upper bound of 1/(1+\ln 2) for any incentive compatible and fair selection mechanisms.


翻译:选择网络中最有影响力的代理物在应用中具有巨大的实际价值。 但是, 在许多情形下, 图表结构只能从代理物有关其联系的报告中得知。 在自我利益的环境中, 代理物可能从战略上隐藏某些连接物, 使自己显得更加重要 。 在本文中, 我们研究激励兼容( IC) 选择机制, 以防止这种操纵。 具体地说, 我们将一个代理物的后代作为她的影响力, 即植根于她的子宫节点的数目来模型。 我们然后提议几何机制, 选择一个至少拥有1/2最佳后代的代理物, 在激励兼容性和公平性下, 。 公平要求两个图形中具有相同贡献的两个根子具有相同的可能性。 此外, 我们证明任何激励兼容性和公平选择机制的上限为1(1 ⁇ ⁇ ln 2 ) 。

0
下载
关闭预览

相关内容

专知会员服务
18+阅读 · 2021年7月11日
专知会员服务
56+阅读 · 2021年1月26日
专知会员服务
74+阅读 · 2020年9月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
LibRec 精选:AutoML for Contextual Bandits
LibRec智能推荐
7+阅读 · 2019年9月19日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
A spatially adaptive phase-field model of fracture
Arxiv
0+阅读 · 2021年9月21日
Arxiv
7+阅读 · 2021年5月25日
Arxiv
5+阅读 · 2020年6月16日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
VIP会员
Top
微信扫码咨询专知VIP会员