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 ) 。