ACM通信
研究突出了
技术视角:设计算法及其应满足的公平标准
算法越来越多地被用于确定稀缺、高价值资源的分配。例如，政府用来分配无线电频谱的频谱拍卖需要算法来确定哪些出价组合可以并且应该被接受。肾脏交换允许需要肾脏移植的患者和有意愿但在医学上不兼容的供体者交换他们的供体，其中一些交换现在使用算法来确定谁与谁匹配。这是两个非常不同的应用领域，在前者，资金转移发挥着重要作用，但在后者，它们是非法的。其他应用程序有不同的功能，因此每个应用程序都有自己的需求。
尽管缺乏单一的、通用的解决方案，但按算法分配资源有几个明显的好处。在上述两个例子中，可能备选方案的空间都出现了组合爆炸，计算机在这些空间中搜索的能力要强得多。如果事先明确指定了算法，这也可以提高整个过程的信任。另一方面，在算法设计的过程中，往往会出现目标不明确的问题。政府在进行频谱拍卖时，应该关注频谱的有效分配，还是创收?在肾脏交换中，我们是应该简单地最大限度地增加移植的数量，还是应该优先考虑某些特定的病人，例如那些未来由于血型而难以匹配的病人?
没有这些问题的答案，很难设计算法;即使我们避免明确地回答这些问题，任何算法的选择都隐含地对应着一个关于每个方面的优先级的决定。最重要的是，不同的目标通常需要在本质上完全不同的算法，即使在相同的应用领域，一些目标不允许足够高效的算法。因此，在设计算法的计算机科学家和确定优化目标的其他人(政策制定者、经济学家、医生、伦理学家)之间有一个明确的劳动分工通常是不可实现的。他们需要互相交谈。
如果说有一个目标通常既重要又难以精确，那就是公平。优化一些直接的标准通常会导致人们直觉上认为不公平的结果。更糟糕的是，他们往往很难确切指出是什么导致了这些结果的不公平。他们也许能在某种程度上用语言表达出来，但通常都达不到精确的数学标准。
下面的论文主要是针对租金划分的具体问题，我们有n人们一起租一间公寓B租金。有n卧室要分配给他们，房间也不都一样，所以不平均分摊租金可能是有意义的。然而，租客们对每个房间值多少钱意见不一。考虑到每个人对每个房间的估价，租金应该如何分配?这就是作者着手解决的问题。他们的动机部分来自Spliddit网站，该网站是由一些作者开发的，为各种公平划分问题提供工具，包括租金划分，广泛使用。虽然租金划分问题本身就很重要，但在我看来，这篇论文的更大贡献在于它是一个很好的案例研究，帮助我们解决前面讨论的问题类型。租金划分公平意味着什么?是否有计算这种租金划分的有效算法?
这篇论文的突出之处在于它运用了各种各样的技术来解决问题。作者以理论为指导，包括数学经济学中的第二福利定理。但他们也做了一项用户研究，以Spliddit用户为研究对象。当然，他们为这个问题设计了一个有效的算法，现在已经在Spliddit上部署了。
如果说有一个目标通常既重要又难以精确，那就是公平。
越来越多的关于资源分配的决策由算法做出，以及其他影响人们生活的决策，例如，机器学习分类器决定某人是否被保释。以下论文中的多学科方法结合了经济理论、行为科学和计算机科学的技术，对于引导这些发展向最有利的方向发展是必不可少的。
数字图书馆是由计算机协会出版的。版权所有©2018 ACM, Inc.
没有发现记录