摘要翻译：
我们考虑n个agent集合上的有向图，其中边（i,j）表示agent i支持或信任agent j。给定这样一个图和一个整数k\leqn，我们希望选择使indegrees之和最大化的k个代理的子集，即k个最受欢迎或最受信任的代理的子集。同时，我们假设每个个体代理只对被选择感兴趣，并可能为此错误地报告其输出边缘。这个问题描述抓住了代理在他们之间进行选择的现实场景，这些场景可以在互联网搜索、像Twitter这样的社交网络或像Epinions这样的声誉系统的上下文中找到。我们的目标是设计无支付机制，将每个图映射到待选代理的k-子集，并满足以下两个约束：策略证明性，即代理不能从错误报告其输出边中受益；近似最优性，即所选代理子集的indegrees之和总是接近最优。我们的第一个主要结果是一个令人惊讶的不可能：对于k\in{1,...,n-1}，没有任何确定性策略证明机制能够提供有限的近似比。我们的第二个主要结果是一个随机策略证明机制，它的逼近比对任何k值都是以4为界的，并且随着k的增长接近1。
---
英文标题：
《Sum of Us: Strategyproof Selection from the Selectors》
---
作者：
Noga Alon, Felix Fischer, Ariel D. Procaccia, Moshe Tennenholtz
---
最新提交年份：
2009
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Computer Science and Game Theory        计算机科学与博弈论
分类描述：Covers all theoretical and applied aspects at the intersection of computer science and game theory, including work in mechanism design, learning in games (which may overlap with Learning), foundations of agent modeling in games (which may overlap with Multiagent systems), coordination, specification and formal methods for non-cooperative computational environments. The area also deals with applications of game theory to areas such as electronic commerce.
涵盖计算机科学和博弈论交叉的所有理论和应用方面，包括机制设计的工作，游戏中的学习（可能与学习重叠），游戏中的agent建模的基础（可能与多agent系统重叠），非合作计算环境的协调、规范和形式化方法。该领域还涉及博弈论在电子商务等领域的应用。
--
一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  We consider directed graphs over a set of n agents, where an edge (i,j) is taken to mean that agent i supports or trusts agent j. Given such a graph and an integer k\leq n, we wish to select a subset of k agents that maximizes the sum of indegrees, i.e., a subset of k most popular or most trusted agents. At the same time we assume that each individual agent is only interested in being selected, and may misreport its outgoing edges to this end. This problem formulation captures realistic scenarios where agents choose among themselves, which can be found in the context of Internet search, social networks like Twitter, or reputation systems like Epinions.   Our goal is to design mechanisms without payments that map each graph to a k-subset of agents to be selected and satisfy the following two constraints: strategyproofness, i.e., agents cannot benefit from misreporting their outgoing edges, and approximate optimality, i.e., the sum of indegrees of the selected subset of agents is always close to optimal. Our first main result is a surprising impossibility: for k \in {1,...,n-1}, no deterministic strategyproof mechanism can provide a finite approximation ratio. Our second main result is a randomized strategyproof mechanism with an approximation ratio that is bounded from above by four for any value of k, and approaches one as k grows.
---
PDF链接：
https://arxiv.org/pdf/0910.4699