ACM通信

评论文章

基于多主体偏好的决策

由文森特Conitzer
ACM通信，2010年3月，53卷第3期，84-94页
10.1145/1666420.1666442
评论

人们经常必须共同做出决定，即使他们对备选方案的偏好有冲突。例子从平凡的(比如在家庭成员之间分配家务)到崇高的(比如选举一个政府，从而为一个国家指明道路)都有。联合决定可以通过非正式谈判进程或通过一项仔细指定的议定书来达成。

哲学家、数学家、政治学家、经济学家和其他人几个世纪以来一直在研究各种协议的优点。最近，特别是在过去的十年里，计算机科学家也深入参与了这项研究。计算机科学家在这一领域的意外出现可能是由于多种原因，包括以下几点:

1. 计算机网络为交流喜好提供了一个新的平台。例子包括拍卖网站，在那里，偏好以出价的形式进行交流，以及允许人们对从产品质量到一个人的吸引力等方方面面进行评价的网站。
2. 在计算机科学领域，越来越多的情况下，决策必须基于多方相互冲突的偏好。示例包括确定谁的作业首先在机器上运行，谁的网络流量沿特定链接路由，或者在搜索结果页面旁边显示什么广告。
3. 更强大的计算能力和更好的算法，以及公众更注重计算的思维模式，使得运行计算要求高的协议成为可能，从而产生更好的结果。一个例子是拍卖，竞标者可以对任意一组项目进行竞标，而不仅仅是单个项目(我将在后面详细讨论这种拍卖)。这些协议曾经被认为是理论上的细微之处，永远不可能在实践中运行(在它们被设想的程度上)，但现在它们实际上是实际的。
4. 计算机科学的范式为经济学和相关学科的一些经典问题提供了不同的和有用的视角。例如，经济学上的各种结果证明了均衡的存在，但没有提供达到这种均衡的有效方法。

在这篇文章中，我对计算机科学家在这个领域中正在研究的主题进行了(不一定是不完整的)调查。我讨论了投票和排名聚合、任务和资源分配、肾脏交换、拍卖和交换、慈善捐赠和预测市场。我研究了代理按照自己的最佳利益行事的问题，这贯穿了大多数应用程序。我还穿插了一些关于未来研究方向的观点和预测。

在这里，我们感兴趣的偏好并不总是人;它们也可以是机器人、软件代理或公司。^一个正如在计算机科学和经济学中所做的那样，我使用术语“代理”来指代任何一方。

回到顶部

设置没有支付

我将讨论各种设置，因此对它们进行分类是有帮助的。一个重要的方面是设置是否允许代理相互支付(用某种货币)。例如，在投票环境中，我们通常不会想象选民之间的金钱交易(不考虑不道德行为)。另一方面，在拍卖中，我们自然希望中标者为她的所得买单。首先，我将讨论不进行金钱交易的各种情况。

投票和排名聚合。在多个备选方案中做出决定的一种自然而普遍的方法是投票。在投票的一般理论中，代理人可以做的不仅仅是投票给一个单一的选项:通常，他们可以对所有的选项进行排序。例如，如果一群人决定一起去哪里吃饭，其中一个人可能喜欢美国菜而不喜欢巴西菜，巴西菜而不喜欢中国菜。这个人的投票可以表示为A > B > C。

根据大家的投票，应该选哪种菜呢?答案远非显而易见。我们需要一个投票规则它将选票集合作为输入，并作为输出返回获胜的备选方案。一个简单的规则被称为多数票规则，它通常会选择排在第一位的备选方案。在这种情况下，代理并不真的需要给出一个完整的排名:它足以表明一个人最喜欢的选择，所以每个代理实际上只是为一个单一的选择投票。

另一个规则是anti-plurality规则，它会选择被排序的选项最后的的至少经常。现在，代理人只需报告他们最后的选择，即他们投票反对另一种选择。这两条规则哪一条更好?这很难说。前者试图使满意选择的代理数量最大化;后者试图尽量减少不快乐的人数。另一个规则，被称为Borda规则，试图达到一种平衡:当有三个选项时，如果一个选项排名第一，它将给它两分，如果它排名第二，它将给它一分，如果它排名最后，它将给它零分。已经提出了许多其他规则，其中大多数不依赖于这种基于积分的方案;社会选择理论家分析了这些规则的可取性和不可取性。

除了选择一个胜出的方案，这些规则中的大多数还可以用于找出所有方案的总排名。例如，我们可以根据Borda评分对备选方案进行排序，从而不仅决定“最佳”备选方案，还决定次优备选方案，以此类推。这有许多与计算机科学家相关的应用:作为一个说明性的例子，可以向多个搜索引擎提出相同的查询，并将产生的页面排名组合成一个聚合排名。

这类设置的一个特别好的规则是Kemeny规则，它找到了一个与输入排名“最低程度不一致”的备选方案的总排名。更准确地说，我们说，当总排名把一个选项排在另一个前面，但有一个选民把后一个选项排在前一个前面时，就发生了分歧。凯梅尼规则产生了一个将这种分歧的总数最小化的排名(对选民和对备选方案的总和)。

---

虽然允许使用需要计算的投票规则是有价值的，但我相信在不久的将来，计算机科学家将对投票的理论和实践做出更大的贡献。

---

凯梅尼规则有许多可取的性质。例如，如果我们假设存在一个未观察到的备选方案的“正确”排名(反映了它们的真实质量)，并且每个选民根据一个特定的噪声过程对这个正确排名做出估计，那么Kemeny规则就会产生正确排名的最大似然估计。⁴⁰

不幸的是，找到Kemeny规则的输出排名在计算上是很难的(形式上，NP-hard)。^3.然而，在实践中通常有算法可以解决这个问题。⁸例如，在杜克大学(Duke University)的计算机科学系，我们使用凯梅尼规则(Kemeny rule)找到了我们最优秀的博士申请者的总排名(基于招生委员会成员的个人排名);使用CPLEX求解器，我们发现凯梅尼在一分钟内就排了100多名申请者。

虽然启用像Kemeny规则这样需要计算的投票规则是有价值的，但我相信，在不久的将来，计算机科学家(特别是计算社会选择团体)将对投票的理论和实践做出更大的贡献。现实世界的组织通常需要做出的不仅仅是一个决定，而是关于许多相互关联的问题的决定。在我们的用餐示例中，代理不仅需要决定餐厅，还需要决定用餐的时间;特工的首选餐厅可能取决于晚餐的时间。例如，一个特工可能不喜欢在睡觉前吃一顿丰盛的巴西牛排。

从某种意义上说，处理这个问题的“正确”方法是把一种时间和一种菜肴的选择组合起来，这样代理人就可以说:“我喜欢早一点的巴西菜，而不是晚一点的中国菜……”然而，随着更多问题的合并，这种直接的方法很快就变得不切实际，因为备选方案的数量经历了组合爆炸。理想情况下，代理应该有一种表达性的语言，可以自然而简洁地表示他们的偏好。一种很好的表达这种偏好的语言是cp -net⁴(这与贝叶斯网络有些相似)。cpnet允许选民指定她对某一议题的偏好取决于对其他议题的决定，例如，“如果我们吃得早，我喜欢巴西菜;否则，我更喜欢中文。”给定一种语言，我们必须设计新的投票规则，这些规则能够操作用这种语言表示的首选项，以及运行这些规则的算法。

而这种组合投票^20.，38在它的初期，很容易看到它的潜在价值，考虑到我们今天在这些类型的情况下使用的方法是多么特别。例如，国会成员必须对涉及许多不同问题的法案进行投票，他们通常更喜欢表达对个别问题的偏好。不幸的是，对个别问题单独投票很容易导致不希望的结果，因为不能保证问题以一致的方式得到解决。例如，在用餐的例子中，可能会发生大多数特工，一般来说，更喜欢在巴西牛排馆吃饭;而且，一般来说，大多数特工都喜欢晚吃;但大多数探员都不想在深夜去巴西牛排馆吃饭。如果他们分别就这些问题进行投票，结果很可能是在巴西牛排餐厅吃一顿迟到的晚餐。这就是为什么表达首选项的语言需要允许代理指定问题之间的一些交互。

分配任务和资源。投票方案允许代理对备选方案提交任意偏好。虽然这种通用性很好，但在许多情况下，它是不需要的，因为我们可以有把握地对代理的偏好做一些假设。让我们再次考虑在家庭中分配家务的例子。另一种选择可能是:“爱丽丝会用吸尘器吸尘并倒垃圾，鲍勃会洗碗。”似乎可以肯定的是，Bob会更喜欢这个方案而不是另一个方案:“Alice会倒垃圾，Bob会吸尘和洗碗”，因为后一个方案给了Bob额外的任务。另一方面，如果我们分配的是想要的资源而不是繁琐的任务，那么多可能比少好。例如，如果代理共同拥有一辆汽车，那么另一种选择可能是:“Alice在周五使用这辆车，Bob在周六和周日使用它，”Bob可能更喜欢这种选择，而不是“Alice在周五和周六使用这辆车，Bob在周日使用它。”在这里，在某一天使用汽车是一种“资源”。这些关于偏好的假设，接受更多的任务或更少的资源是从来没有首选，通常被称为单调性假设。

关于首选项的另一个合理假设是，代理只关心分配给她的任务或资源。例如，爱丽丝可能对“爱丽丝在周五取车，鲍勃在周六取车，卡罗尔在周日取车”和“爱丽丝在周五取车，鲍勃在周六和周日取车，卡罗尔从不取车”这两种情况漠不关心。在经济学中，假设一个代理人，给定她自己的资源和任务，不关心剩余的资源和任务如何分配给其他代理人，这被称为no-externalities假设。这并不总是完全准确的，爱丽丝可能不喜欢卡罗尔永远不会得到车的选择稍微多一点，例如，因为卡罗尔会让爱丽丝为她跑腿，在这种情况下，但这通常是假设的。

诸如此类的合理假设使我们能够摆脱投票模型的通用性，并以一种更具体于任务和资源分配的方式做出决策。顺便提一下，在计算机科学中有许多任务和资源分配的应用。例如，我们可能会把时间分配在超级计算机(或其他计算资源)上，而不是花在汽车上。此外，我们可以把工作分配给机器，而不是把家庭的杂活分配给住户。

那么，我们应该如何分配任务和资源呢?到目前为止，对此最常见的方法是假设代理可以用某种货币进行支付或接收支付，这将导致我们使用拍卖和交换机制。我将在后面更详细地讨论这种机制，但是现在，我首先考虑不需要支付的方法。这些方法通常会试图找到一个在某种意义上“公平”的分配。

一个公平标准是envy-freeness:我们应该找到这样一个分配:每个代理都喜欢自己的包(即分配给她的任务或资源)，而不是其他代理的包。当资源不可分割时，不受嫉妒的分配并不总是可能的，而决定是否存在这样的分配是NP-hard。²²此外，有人会说，仅仅没有嫉妒是不够的:即使一个分配是没有嫉妒的，重新分配任务或资源也有可能使每个人都过得更好，在这种情况下，我们说原始的分配不是帕累托效率。例如，考虑这样一种情况:一个代理拥有两只左脚的鞋子，而另一个代理拥有两只右脚的鞋子。双方都不嫉妒对方的处境，但双方都可以通过用左脚的鞋子交换右脚的鞋子而得到更好的结果。帕累托效率通常被认为是最重要的。已经有工作描述了寻找一个既无嫉妒又帕累托效率的分配的计算复杂性。⁵

在每个资源最初都由其中一个代理拥有的上下文中，使用交换是有意义的，即使由于某种原因无法支付。下面是一个不支付交易的例子。

肾脏的交流。在大多数交易所中，参与者可以互相付款，这方便了交易。然而，也有一些交易是不能支付的，所以只有物品易手。这被称为易货交换。肾脏交换就是一个例子。²⁷

买卖肾脏在大多数国家都是非法的;然而，换肾就不是这样了。例如，假设一个病人需要肾移植，有一个捐献者愿意为这个病人放弃她的肾，但不幸的是，他们不兼容。在相同的情况下可能有第二个患者-供体对;此外，也可能出现第二个病人与第一个供体兼容，而第一个病人与第二个供体兼容的情况。在这种情况下，两个患者-捐赠者对交换他们捐赠者的肾脏是有益的。

---

使用拍卖的主要好处是，资源最终会分配给最重视它的代理(或者任务最终会分配给最不介意做它的代理)。在这种情况下，我们说拍卖的结果是有效分配。

---

将每一对患者供体看作一个单一的供体是有帮助的，这样每个供体都有一个肾脏并且需要另一个肾脏。这使我们更容易看到更复杂的交易是有益的:代理人1的肾可以到代理人2，代理人2的肾可以到代理人3，代理人3的肾可以到代理人1，这被称为长度为3的循环。当然，我们也可以有长度为4的循环，等等，但最好不要有很长的循环(一个循环中的所有操作必须同时执行，这样就没有人会退出，这就给长周期带来了一个后勤问题;此外，如果最后一刻的测试发现了周期中的不兼容性，整个周期就会崩溃)。

肾脏交换已经成为现实，计算机科学家也参与其中。¹事实上，他们已经开始研究清算交换的计算问题:输入描述哪些患者与捐赠者的哪个肾脏兼容，输出指定将使用哪个循环。使用匹配算法，如果不限制循环的长度，或者只允许长度为2的循环，则可以在多项式时间内解决问题。但是，如果最大循环长度是3或更多，那么问题是NPhard。然而，在实践中，通过使用包括列生成和分支价格搜索在内的优化技术，可以解决大型交易所的最优性问题。¹

回到顶部

设置与支付

现在我们继续讨论代理可以进行或接收付款的设置。支付是有用的，因为它允许我们量化代理的偏好。非正式地说，经纪人现在需要把钱用在嘴上。支付还允许我们将幸福(效用)从一个代理转移到另一个代理。

拍卖和交流。在许多需要我们决定任务或资源分配的问题中，还需要确定一些代理应该向其他代理支付的费用。回到我们分配家务的例子，想象这些居民是室友，他们每人支付一部分房租，我们最终分配给其中一个室友不成比例的家务。这个室友应该支付更小份额的租金，这似乎是公平的，这实际上代表了其他室友向这个室友的货币转移。这种安排可能对每个人都有好处，例如，如果这个室友失业了，有足够的时间完成家务，但很少有钱花在房租上。

一旦我们开始考虑任务和资源分配中的支付，我们很快就会陷入拍卖理论。(一篇关于拍卖和计算机科学的文章发表在2008年8月的通信。³⁵大多数人都熟悉英式拍卖的形式，即出售一件物品(或一大堆物品)，投标者不断提高出价，直到没有人愿意出更高的价。还有许多其他的拍卖形式，如荷兰式拍卖，一开始价格很高，竞价者在价格逐渐下降时保持沉默，直到竞价者宣布她想以这个价格购买物品，这时拍卖立即结束。

还有一种形式是密封投标形式，即竞标者在一张纸上写下出价，把它放在一个信封里，然后交给拍卖人;拍卖师打开信封，宣布出价最高者为获胜者。因为在这一点上，我们最关心的是如何根据代理人的偏好做出决定，而不是这些偏好是如何沟通的，所以我们现在最容易考虑的是密封投标格式。

如果我们分配任务而不是分配资源，我们可以使用反向拍卖。在这里，对一个任务出价10美元表明投标人希望通过完成该任务获得10美元;在这种情况下，出价最低的胜出。一般来说，在拍卖中，有一个从中标者那里收到付款的卖方(或者，在反向拍卖中，有一个向中标者付款的买方)。然而，卖方并不总是在场:例如，如果代理试图决定谁在某一天获得驾驶汽车的权利，他们可以为这一权利举行拍卖，但在这种情况下，获胜代理的付款自然会流向失败代理。最近的一些工作致力于设计将拍卖收入重新分配给代理人的机制。

使用拍卖(或反向拍卖)的主要好处是，通常情况下，资源最终会分配给最重视它的代理(或者任务最终会分配给最不介意做它的代理);在这种情况下，我们说拍卖的结果是有效分配。如果分配是低效的，那么可以通过重新分配一些任务/资源和一些钱，让每个人都过得更好。根据这个论点，效率和帕累托效率在这个背景下是同一个概念。

当需要分配多个资源(或任务)时，一种简单的方法是为每个资源举行单独的拍卖。然而，这种方法有一个显著的缺点，这与以下观察结果有关:一个资源对代理的价值通常取决于该代理接收到的其他资源。

例如，如果Alice已经有权在周五开车，那么在周四开车对她来说可能没有太大的价值，因为她已经可以在周五完成她的差事。相反，如果她在其他任何一天都没有车，那么在周四拥有它对她来说可能非常有价值。当一种资源使另一种资源的价值降低时，我们就说这些资源是替代品。另一方面，Alice可能想要进行一次两天的旅行，在这种情况下，除非她周五也有车，否则周四有车毫无意义。当拥有一种资源使拥有另一种资源更有价值时，我们就说这些资源是互补的。

可替代性和互补性使得在单独拍卖中出售资源不是最优选择，原因如下。如果先拍卖周四的汽车使用权，在某种意义上，爱丽丝不知道她对这辆车的价值，因为她还不知道她是否会赢得其他几天的拍卖。这种不确定性会导致低效的分配。

组合拍卖¹²提供一个解决方案。在(密封竞价)组合拍卖中，竞标者的出价不仅表明竞标者对每件拍卖品的估价;相反，竞标者为每个非空子集(包)表示一个值。例如，Alice的出价可以这样说:“对我来说，周四拥有这辆车值5美元，周五拥有它值6美元，周四和周五同时拥有它值8美元。”给定所有这些信息(对于所有的竞标者)，一个算法可以搜索所有将物品分配给竞标者的可能性，并找到最有效的一种，即使代理人的估值之和最大化的分配。

类似地，在组合反向拍卖中，每个竞标者都表示她希望从分配给她的每一组任务中获得多少报酬。还有一种变体是组合交易，在这种交易中，代理人既可以扮演卖方的角色，也可以扮演买方的角色，他们为这些更复杂的交易表达组合估值。这些变体面临许多与组合拍卖相同的问题。¹²

一旦组合拍卖中的物品数量超过几件，每个竞标者明确表示每捆物品对她来说价值多少的直接方法就完全不切实际了，因为捆绑物的数量是指数级的。相反，我们可以让投标人使用一种表达性的投标语言，这种语言允许他们简洁地表达自然估值函数(类似于我在组合投票中提到的cp -net)。

一个简单的例子是XOR语言，在该语言中，投标者显式地表示一些(但通常不是所有)捆绑包的估值。例如，如果出售的物品是{a, b, c}，出价人可以出价({一个}， 5) xor ({)b, c}, 10)。这表明她对bundle{有价值一个在5};包{b, c在10};包{a、b}，因为它没有显式列出，但它包含包{一个};和bundle {a, b, c}，因为它包含的最高值的列表包是{b, c}(使用XOR而不是OR表示我们不能简单地将列出的两个bundle的值相加得到15)。

投标语言的选择会影响一些问题，如确定获胜者问题的计算复杂性，即在给定的投标条件下，找到项目的有效分配的问题。即使每个竞标者只对一个包出价，组合拍卖赢家的确定问题也是np困难的²⁸和inapproximable。²⁹另一方面，已知在一定的投标条件下，中标人的确定问题可以在多项式时间内求解。²³例如，如果竞标者只对最多两件物品的捆绑进行投标，那么胜利者的确定问题可以通过匹配算法在多项式时间内解决。通常，运行时在很大程度上取决于如何生成竞价:在某些情况下，可以扩展到数十万项和数万个竞价，而在其他情况下，当前技术在扩展到超过数十项和数百个竞价时存在困难。^30.

与其让竞标者只出价一次，也就是说，要求他们一次性提供所有的估值信息，还可以采用迭代(或偏好诱导)的形式，即竞标者反复回答有关其估值的问题。^25，32在单一物品的设置中，这对应于密封竞价拍卖和英式拍卖之间的区别，在密封竞价拍卖中，每个出价人只出价一次，而在英式拍卖中，拍卖师反复向出价人询问更高的估价。在组合拍卖中使用偏好诱导有可能大大减少竞标者需要沟通的估价信息总量，同时仍能找到有效的分配。这就导致了以下固有的计算问题:如何设计查询投标者的程序，以减少所需的通信量?

组合拍卖不仅仅是一种理论上的新奇事物:它们在实际应用中被应用在物品显示出显著互补性的环境中。著名的例子包括无线电频谱拍卖，以及战略采购的反向拍卖(在这种拍卖中，大公司与供应商签订合同)。^12，31，35

在一个对大多数计算机科学家来说可能更接近家庭的背景下，拍卖现在也被领先的搜索引擎用来分配搜索结果页面上的广告空间。这是有多个资源出售的拍卖的另一个例子:用户执行的任何搜索都会导致多个广告位置可用。这些拍卖被称为赞助搜索拍卖，他们推出了各种各样的新问题。例如，在一个典型的赞助搜索拍卖中，广告商只在用户点击她的广告时付费，而不是每次她的广告显示时付费。赞助搜索拍卖在使用此类拍卖的公司的商业模式中占据着重要地位，这有助于推动近年来对此类拍卖的研究出现爆炸式增长;¹⁹一个彻底的讨论很容易形成一篇文章。

虽然拍卖和交易是最吸引计算机科学家关注的支付设置，但还有许多其他更专业的应用。这里将讨论其中一些。

慈善捐赠。让我们设想一个人正在考虑向慈善事业捐赠一些钱(比如说100美元)。似乎潜在的捐赠者应该只评估她会用这笔钱做什么，以及这对她来说是否比看到慈善机构收到100美元更有价值。虽然这是一种合理的方式，但如果有多个潜在捐赠者，还有其他选择。

假设有第二个捐献者也在做同样的决定。此外，让我们假设每个捐赠者都得出结论，她宁愿花100美元在其他事情上，也不愿看到慈善机构收到100美元。因此，使用前面描述的直接决策程序，任何捐赠者都不会提供任何资金。然而，很有可能，即使有这些偏好，每个捐助者都更喜欢结果这两个捐助者给。也就是说，每个捐赠者可能更喜欢慈善机构收到200美元的结果，而她只捐出其中的100美元。这是因为，在其他条件相同的情况下，他们希望另一个捐赠者给慈善机构尽可能多的钱。(与本文前面讨论的设置不同，这本质上是一种具有外部性的设置:一个捐赠者对另一个捐赠者如何使用她的钱有偏好。)然而，在直接的决策过程中，任何一方都没有能力影响另一方的捐赠。这就是为什么没有捐赠者给慈善机构。

事实上，一个捐赠者可以通过某种方式影响另一个捐赠者的决定。假设两个捐赠者中的一个可以做出具有约束力的匹配出价，承诺捐赠与另一个捐赠者相同的金额。在这种情况下，另一个捐赠者可以选择捐赠100美元，从而为慈善机构贡献200美元，或者不捐赠，从而为慈善机构贡献0美元。根据我们假设的偏好，捐赠者实际上会捐出100美元，从而迫使另一个捐赠者也捐出100美元。值得注意的是，双方捐赠者(以及慈善机构)都更喜欢这种结果，而不是他们各自做出决定时的结果(即双方都捐出0美元)。

在实践中，配对捐赠通常是由一个大捐赠者提出，并提出匹配多个小捐赠者的捐赠。正如我们刚才看到的，简单的匹配报价可以带来更好的结果，但它们仍然具有限制性。如果多个捐赠者希望将他们的捐赠附加在其他人的捐赠上，该怎么办呢?这种表达方式可以带来更好的结果，但你必须小心避免循环。例如，考虑这样一种情况一个将匹配B的贡献,B将匹配一个的贡献。

我们提出了一个系统，在这个系统中，每个捐赠者的捐款可以以所有捐赠者捐赠给慈善机构的总额加起来为条件。¹⁰事实上，该框架允许捐赠以捐赠给多个慈善机构的总金额为条件。我们还设计了基于每个人的出价来确定最终结果的算法，这在一般情况下是np困难的，但在特殊情况下是可处理的。我们用这个系统为印度洋海啸的受害者，以及后来为卡特里娜飓风的受害者收集捐款。虽然从这些活动中收集到的总金额很少(约1000美元)，但这些活动让人们对捐助者如何使用该系统有了一些了解。大约75%的捐赠者将他们的捐款与收集到的总金额挂钩，这表明捐赠者对能够这样做感到高兴。一个有趣的观察是，这个系统的有效性(就参与者愿意捐赠多少而言)显然取决于捐赠者与谁的捐赠相匹配。海啸事件是在一个研讨会的参与者之间进行的，因此在某种程度上，每个人都认识彼此;相比之下，飓风活动对任何人都开放。海啸活动比较成功，也许是因为参与者知道他们匹配的是谁的捐款。在考虑到社会网络结构的情况下，最近的系统还允许捐赠者将他们的捐赠只与选定的捐赠者的捐赠相关联。¹⁴我相信这种创新有潜力使这类系统更加成功。

---

代理是否有动力如实交流他们的喜好和信仰，或者他们能从错误的报告中获益?

---

预测市场。到目前为止，我所考虑的市场通常会产生有形的结果，例如资源的分配。参与的主体对可能的结果有不同的偏好，而市场是为这些偏好找到一个好的结果的机制。我接下来要讨论的市场类型有点不同。

预测市场³⁷关注一个特定的未来事件，其结果目前是不确定的。例如，事件可以是即将到来的体育比赛，或选举。在预测市场上进行交易的代理人通常无法(显著)影响事件的结果;市场的目标仅仅是根据参与主体的集体信息和推理来预测事件的结果。通常情况下，市场预测是以概率的形式出现的:例如，市场的评估可能是那个团队的概率一个将击败团队B是43%。预测市场在网上很受欢迎:例子包括爱荷华电子市场和Intrade。每个机构都对各种事件进行预测;似乎政治事件(例如，预测选举的获胜者)是最受欢迎的。

运行预测市场的一种常见方法如下。我们创建一个证券，如果一个团队支付(比如说)1美元一个获胜，团队则0美元一个不赢。然后我们让代理人交易这些证券。最终，这将导致一个相对稳定的市场价格:例如，证券交易价格可能在0.43美元左右。这可以解释为，市场(即集合代理)目前相信该概率的团队一个获胜几率约为43%。

如果一个代理人不同意这个评估，那么她应该买进或卖出一些证券。例如，如果一个代理人认为概率是46%(即使在观察当前0.43美元的市场价格后)，那么她可以以0.43美元的价格购买其中一个证券，她对该证券的预期支付将是46%·1美元= 0.46美元。随着她购买更多的证券，市场价格最终将上升到0.46美元。

如果经纪人认为这个概率是40%，那么她应该卖出一些证券。如果她目前不拥有任何证券，她可以卖空，这样她实际上拥有的证券是负数;或者，她可以为互补的结果购买证券:例如，如果两者之间匹配一个而且B是保证有赢家，她可以买一个证券，支付如果B赢了。这些证券的价格是相关的:如果比赛保证有赢家，那么支付1美元的证券的当前价格之和一个赢了，还有支付1美元的证券B赢，必须总是等于1美元。如果不是，那么就会有套利的机会:一种交易组合，导致无风险的利润。具体来说，如果当前价格的总和是(比如说)0.9美元，那么一个人可以买两个证券，并有一个0.1美元的利润保证，因为其中一个必须支付。如果总额是(比如说)1.1美元，那么一个人可以卖出这两种证券，这同样会保证获得0.1美元的利润。

标准预测市场的一个复杂之处在于，许多现实世界的事件都有指数级多的可能结果。例如，考虑美国总统选举。从某种意义上说，每个州(以及哥伦比亚特区)的选举结果都是不同的，因此即使有两个总统候选人，也会有两个⁵¹选举的可能结果。^b当然，我们可以为每个州设置单独的市场，但这仍然会导致一些错失的机会。

例如，我可能会以80%的概率相信，民主党候选人将赢得佛罗里达州、俄亥俄州和北卡罗来纳州中的至少一个州。目前还不清楚这种信念将如何转化为单个州的证券交易策略。我宁愿直接买一种证券，只要民主党候选人至少赢得佛罗里达州、俄亥俄州和北卡罗来纳州中的一个州，它就会赔钱。现在，假设有另一个交易者相信共和党候选人将以30%的概率赢得佛罗里达州、俄亥俄州、北卡罗莱纳州和密苏里州的所有州，并愿意购买一种证券，这种证券恰好在这些条件下支付。理想情况下，预测市场可以自动创建这两种证券，我的收0.79美元，另一个交易者的收0.29美元。我们双方都会接受这些协议;此外，由于我们的两种证券中最多有一种会支付，预测市场可以保证至少0.08美元的无风险利润。这种组合预测市场最近开始受到关注。⁶运营这样的市场需要解决计算难度大的问题:例如，确定是否存在可以创建的无风险证券组合通常是np难度大的。

---

我(推测地)想象，在未来，更多基于web的机制将围绕社交网络网站，如Facebook和MySpace. ...计算机科学的范式为经济学中的一些经典问题提供了不同而有用的视角。

---

回到顶部

战略行为:博弈论与机制设计

到目前为止，我一直专注于允许代理交流他们的偏好(或者，在预测市场的情况下，他们的信念)，理想情况下，以一种富有表现力和自然的方式，以及基于交流的内容做出良好的决定。不过，我忽略了一个关键方面:代理是否有动力如实传达自己的喜好和信念，或者他们能从错误的报告中获益?

例如，在选举中，代理人的真实偏好可能是一个>b>c．但是，如果代理意识到这一点一个没有获胜的机会，她会选择投票吗b>一个>c，从而至少使…的机会最大化b获胜。类似地，在拍卖中，估价为10美元的代理人可能只出价5美元，希望支付更低的价格。虽然这样的战略行为可能对参与其中的代理有益，但它通常会使整体结果的质量变差，因为现在它的选择是基于输入，而不是反映真正的偏好。

这些考虑将我们引入机制设计。非正式地说，机制设计的目标是设计选择结果的规则，即使在代理具有战略意义的情况下，也会导致良好的结果，也就是说，如果这符合其最大利益，代理会在其偏好上撒谎。机制设计主要(直到最近，几乎完全)在经济学中被研究。^c评估一个机制的质量并不简单:它需要能够预测多个战略主体在彼此存在的情况下将如何行动。博弈论为做出这样的预测提供了工具。^d(一篇关于计算机科学和博弈论的文章发表在2008年8月的通信．³⁴）

机制设计的标准方法很简单，就是确保代理人在自己的偏好上撒谎是永远不会有好处的。一个被称为启示原则的结果表明，从战略行为的角度来看，这种方法不会失去最优性。一种说谎永远无益的机制叫做诚实的。不幸的是，根据Gibbard-Satterthwaite不可能定理的结果，在一般的投票环境中，不存在良好的真实机制。^15，33

对于拍卖和交易等可以进行支付的设置，效果要积极得多。首先，如果我们的目标是有效地分配资源，就会有规则规定代理应该支付多少钱，从而使整个机制真实。

这种支付规则的一个简单例子是单一物品的二次价格密封竞价拍卖。在这种拍卖中，出价最高的竞拍者胜出，但只支付第二高的出价。因此，中标人的出价不影响她支付的价格;因此，虚报道具价值的唯一影响可能是她无法获胜，这将使她的处境更糟。同样，对一个失败的竞标者来说，误报可能产生的唯一影响是，她最终以对她来说过高的价格获胜，这将使她的处境更糟。所以，出价人最好报告她对物品的真实估价，也就是说，第二价格的密封竞价拍卖是真实的。该方案可以推广到组合拍卖和交换(和其他设置)，产生了vickrey - clark - groves (VCG)机制类。^7，16，36

机制设计中研究的问题与我之前讨论的计算问题以微妙的方式相互作用。例如，假设我们想要使用VCG机制运行一个组合拍卖。从技术上讲，这意味着我们应该总是解决最优胜者决定问题，也就是说，找到最有效的分配，我们知道这是NP-hard。如果我们不能总是成功地找到最有效的分配，那么由此产生的机制通常是不真实的。大量的研究已经解决了设计多项式时间近似算法的问题，结合正确的支付规则，是真实的。²¹更普遍地说，设计高效的、可实现真实的算法是算法机制设计的主要课题。²⁴这方面的研究还扩展到没有可信中心的分布式环境。¹³

我们不仅可以用计算机运行现有的机制，还可以从头开始设计新的机制。也就是说，对于一个给定的设置，我们让算法在所有可能的真实机制空间中搜索一个最优的机制。⁹这种方法被称为自动机制设计。找到一个最优机制在计算上比运行一个现有机制要困难得多，因此自动化机制设计到目前为止只在小实例上成功过。然而，一些实际实例实际上很小，即使对于较大的实例，求解简化版本也可以提供一些有用的直观感受。自动化机构设计也可以用来解决一些小实例的一般机构设计问题;然后，人类机制设计师可以尝试在这些小的解决方案中识别一个模式，推测一般的解决方案，并分析地证明它。通过这种方式，自动化机制设计可以为微观经济学理论做出贡献。这种方法最近被用来设计一种机制，以真实的方式将拍卖收入重新分配给竞标者(例如，郭和康策)¹⁷)，该方法正开始被更广泛地采用。

并不总是机制设计者或运行机制的一方面临困难的计算问题。在某些机制下，智能体很难在计算上找到要采取的最优战略行动。这不是真实机制的情况，在真实机制中，战略上的最佳行为仅仅意味着说真话。然而，没有一个合理的投票规则在足够普遍的情况下是真实的(根据上面提到的Gibbard-Satterthwaite定理)。研究表明，在各种各样的投票设置中，即使其他代理人的投票已经已知，也很难找到要投的战略最优选票(例如Bartholdi，²Conitzer,¹¹和Hemaspaandra¹⁸)。在这种情况下，计算难度是可取的:可以说，如果一个选民找不到一种对她有利的错误报告她的偏好的方法，那么她大概就会说出真相。目前，这类结果的影响受到一个事实的限制，即np硬度是最坏情况下的衡量标准，而且很可能很容易找到一种有效的方法来错误地报告一个人的偏好大多数时候．

另一个重要问题是，传统机制设计的机制主要防止单一类型的操作:错误报告个人偏好。然而，运行在高度匿名环境(如Internet)中的机制很容易受到其他类型的操作。具体来说，一个代理常常可以假装成多个代理(称为假名操作或Sybil攻击)。防止误报的标准机制，如VCG机制，通常对虚假名称操作并不健壮。这是一种稳健的机制，也就是说，在这种机制下，任何代理都不会从使用所谓的防假名多重身份中获益，³⁹越来越多的研究试图设计这样的机制。

机制设计的最后一个方向是将其技术扩展到动态环境中，在动态环境中，随着附加信息进入系统，必须随着时间的推移做出决策。近年来，在将机构设计技术从静态设置推广到动态设置方面取得了快速进展。²⁶例如，赞助搜索拍卖在原则上是这类技术的一个很好的应用领域:特定搜索结果旁边的广告位置的需求和供应随着时间的推移而变化，但分配决策必须现在就做出。

回到顶部

结论

在本文中，我考虑了许多需要根据多个代理的首选项做出决策的设置，以及实现决策的机制。几千年来，人们一直在使用这种机制，并对其进行了几个世纪的正式研究(尽管他们的博弈论分析主要发生在最近50年)。然而，计算机科学家正在从根本上改变这些机制和它们的使用方式。

计算能力的提高和更好的算法使得曾经被认为不切实际的机制，如凯梅尼投票规则和组合拍卖，得以使用。此外，Internet为这些机制提供了一个很好的平台:它使空间分布的用户很容易向机制传达他们的喜好，而且他们通常会被迫以精确的方式传达他们的喜好(例如，出价者必须在Web站点上输入一个号码，而不是通过电话模糊地传达她的喜好)，这使得自动运行机制成为可能。我(推测地)想象，在未来，更多基于网络的机制将以Facebook和MySpace等社交网站为导向;慈善捐赠起作用了¹⁴是如何使用这种社交网络结构的一个很好的例子。计算机科学家在自己的工作中也会遇到机制设计问题，例如，当共享计算资源需要分配给用户时。最后，计算机科学的范式为经济学中的一些经典问题提供了一个不同的和有用的视角。

本文总结了计算机科学家已经参与到市场设计和基于多个代理的偏好进行决策的其他协议中的一些应用。我预计，这类申请的数量和重要性将在未来几年急剧增长。其中一个主要原因是，近年来，对市场设计感兴趣的计算机科学家和经济学家的关系越来越密切，而且现在可以看到他们更频繁地合作(这是由赞助搜索拍卖等高价值应用所必需的)。计算机科学家已经掌握了微观经济学理论文献中发展起来的许多关键技术。另一方面，经济学家越来越熟悉现代计算机科学的技术。这是一个很好的例子，“计算思维”被输出到另一个学科(这当然不是说经济学家以前没有计算思维的例子)。

回到顶部

致谢

这项工作得到了美国国家科学基金会奖项编号iss -0812113的支持，Alfred P. Sloan基金会的研究奖学金，以及Yahoo!教师研究基金会资助。我感谢审阅人员非常详细和有帮助的反馈。我还要感谢Tuomas Sandholm对肾脏交换部分的反馈，以及David Pennock对预测市场部分的反馈。所有的错误和遗漏都是我自己的(当然，我也面临篇幅和引用次数的限制)。

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2010 ACM, Inc。

---

没有发现记录