AF: Small: Fair Division at Scale

对公平分配的数学研究可以追溯到20世纪40年代。现在的文献包含了各种各样问题的可证明的公平解决方案，其中许多与整个社会有关。但是，迄今为止，很少有公平的划分方法得到实施。在其丰富的历史基础上，公平分配领域准备在更大的规模上影响社会，例如，通过Spliddit（www.spliddit.org），一个由PI创建的公平分配网站。该提案的总体主题是，大规模公平性的出现带来了新的算法挑战，围绕着实用，广泛适用和可证明公平的方法的设计。这些挑战的解决方案需要理论计算机科学和微观经济理论的综合思想。Spliddit的发展在该项目中起着关键作用：从研究中产生的见解将被实施，以改善Spliddit的公开访问方法。此外，还将增加新的应用程序，以进一步扩大网站的覆盖面。该项目还包括计划通过制作教学视频来加强Spliddit的教育内容，从而使该网站成为一个宝贵的学习和教学资源。最后，该项目还计划产生超越Spliddit的社会影响。特别是，PI将与加州学区合作，制定一个公平的方法来分配未使用的空间。(i)分割不可分割的货物：作为Spliddit上目前可用的五个应用程序之一，从公平分割的角度来看，不可分割商品的分割是一个众所周知的难题。为了获得一个可证明的公平方法，Spliddit依赖于最小共享（MMS）保证的概念。虽然精确的MMS分配可能是不可行的，该项目探讨了几个近似的概念。该项目还探讨了MMS分配的可行性边界。基础算法挑战是这些研究方向的核心。(ii)分享信用：Spliddit的信用计算器使用de Clippel等人开发的方法公平地确定每个人对团队项目的贡献。也许该方法最令人信服的保证是公正性：玩家的报告不会影响她自己的信用份额。为科学论文划分学分，目的是根据贡献公平地对作者进行排序，这是一个特别有吸引力的潜在应用;但不能保证玩家不会影响他们在最终排名中的位置。该项目旨在通过随机化和近似来规避这一障碍。

The mathematical study of fair division dates back to the 1940s. Nowadays the literature encompasses provably fair solutions for a wide variety of problems, many of them relevant to society at large. But, to date, very few fair division methods have been implemented. Building on its rich history, the field of fair division is poised to impact society on a grander scale, for example, via Spliddit (www.spliddit.org), a fair division website created by the PI. The overarching theme of this proposal is that the advent of fairness at scale gives rise to novel algorithmic challenges, revolving around the design of methods that are practical, widely applicable, and provably fair. Solutions to these challenges call for a synthesis of ideas from theoretical computer science and microeconomic theory. The evolution of Spliddit plays a key role in the project: Insights arising from the research will be implemented to improve Spliddit's publicly accessible methods. Moreover, new applications will be added in order to further widen the website's reach. The project also includes plans to enhance Spliddit's educational content through the creation of instructive videos, thereby making the website a valuable learning and teaching resource. Finally, the project contains plans to make a societal impact that extends beyond Spliddit. In particular, the PI will work with California school districts to develop a fair method for allocating unused space.On a technical level, the thrust of the project is twofold. (i) Dividing indivisible goods: One of five applications currently available on Spliddit, the division of indivisible goods is a notoriously difficult problem from a fair division perspective. To obtain a provably fair method, Spliddit relies on the notion of maximin share (MMS) guarantee. While exact MMS allocations may be infeasible, the project explores several notions of approximation. The project also explores the feasibility boundary of MMS allocations. Foundational algorithmic challenges lie at the heart of these research directions. (ii) Sharing credit: Spliddit's credit calculator fairly determines the contribution of each individual to a group project, using a method developed by de Clippel et al. Perhaps the method's most compelling guarantee is impartiality: a player's report does not affect her own share of the credit. Dividing credit for a scientific paper, with the goal of fairly ordering the authors by contribution, is an especially attractive potential application; but there is no guarantee that players will not be able to affect their position in the resultant ranking. The project aims to circumvent this obstacle via randomization and approximation.