Algorithms and Complexity for Economic Environments (ACEE)

该项目研究在经济环境中找到稳定和理想结果的计算复杂性。这类环境的例子是：-拍卖商品，例如诸如汽车、油画等的“传统”商品，或诸如资产或频谱的其他商品。-涉及多个买家和卖家的市场，例如消费品、资产或广告空间的市场。-在一组参与者之间公平分配一组资源的环境，这些参与者对这些资源有不同的偏好。例如，一个人可能感兴趣的是在企业员工之间分配任务，或者为他们在项目上的工作分配信用，在家庭成员之间分配租金或费用，或者在家庭成员之间分配遗产。稳定的结果是所有这些环境的参与者在某种意义上都认为可以接受或希望得到的结果。-在拍卖中，这样的结果是买家之间战略互动的纳什均衡。考虑到其他投标人的出价，这些是买家满意的货币出价。-对于市场来说，这些结果是竞争均衡，在每种商品的选定价格下，其供应等于其需求，参与者以给定的价格获得尽可能好的商品捆绑。-对于资源分配，稳定的结果是指每个参与者根据自己对可能的资源分配方式的偏好，对资源进行公平的分配。在上个世纪的大部分时间里，这些经济环境得到了一个跨学科的大型社区的广泛研究，这些社区横跨经济学、数学和计算机科学。经济学和数学的经典著作已经证明，对于非常一般的环境，这种稳定的结果总是存在的，即有可能同时满足环境的所有参与者。计算机科学的研究有助于形成和研究主要的后续问题：我们如何才能找到那些稳定的结果？简单地说，我们关心的是是否有可能设计出高效的算法来寻找这些结果，即在计算机上运行时在合理的时间内完成任务的算法。尽管如此，尽管社会各界做出了重大努力，但我们还没有有效的算法来在许多主要经济环境中找到稳定的结果，就像上面强调的那样，我们甚至不知道是否有可能设计这些算法。这个项目旨在为四个重要的经济环境提供具体的答案，即1)拍卖2)市场3)可分割资源的公平分割4)不可分割资源的公平分割具体而言，我们将设计高效的算法来为这些环境找到相应的稳定结果，或者我们将通过所谓的计算难度结果来证明这样的算法不太可能存在。我们的研究结果将告诉研究界，这些问题中哪些“容易”，哪些“难以”用计算机解决。它们将帮助研究人员和实践者：(A)了解试图为这些环境提出良好解决方案的内在挑战，(B)为这些环境制定适当的后续问题，以及(C)确定这种有效算法实际上可能存在的感兴趣的特殊情况。

The project studies the computational complexity of finding stable and desirable outcomes in economic environments. Examples of such environments are: - auctions of goods, for example "traditional" goods such as cars, paintings etc, or other goods such as assets or spectrum.- markets involving several buyers and sellers, for example markets for consumption goods, assets or advertising space.- settings where a set of resources are to be divided fairly among a set of participants, who have different preferences for those resources. For instance, one might be interested in distributing tasks between employees of an enterprise or assigning credit for their work on a project, splitting rent or fare between members of a household, or splitting inheritance between members of a family.Stable outcomes are outcomes that all the participants of these environments find acceptable or desirable in some sense. - In auctions, such outcomes are the Nash equilibria of the strategic interaction between the buyers. These are sets of monetary bids that the buyers are satisfied with, given the bids of the other bidders. - For markets, these outcomes are competitive equilibria, where at the chosen price for each good, its supply equals its demand, and the participants acquire the best possible bundles of goods at the given prices. - For division of resources, stable outcomes are partitions of the resources that each participant considers to be fair, according to their own preferences over the possible ways that the resources could be partitioned. These economic environments have been studied extensively by a large interdisciplinary community spread across economics, mathematics and computer science, over the better part of the last century. Classic works in economics and mathematics have proven that for very general environments, such stable outcomes always exist, i.e., it is possible to satisfy all the participants of the environment at the same time.The research in computer science has been instrumental in formulating and studying the main follow up question: "How can we find those stable outcomes?". In simple words, we are concerned with whether it is possible to design efficient algorithms for finding these outcomes, that is, algorithms that complete the task in a reasonable amount of time when run on a computer. Still, despite significant efforts from the community, we do not have efficient algorithms for finding stable outcomes in many of the major economic environments like the ones highlighted above, and we do not know if it is even possible to design them or not. This project aims to provide concrete answers to this very question, for the four major economic environments of interest, namely 1) auctions 2) markets 3) fair division of divisible resources4) fair division of indivisible resourcesSpecifically, we will design efficient algorithms for finding the corresponding stable outcomes for these environments, or we will prove that such algorithms are unlikely to exist, via so-called computational hardness results. Our results will inform the research community on which of these problems are "easy" and which are "hard" to solve by a computer. They will aid researchers and practitioners in (a) understanding the inherent challenges of trying to come up with good solutions for those environments, (b) formulating the appropriate follow-up questions for these environments, and (c) identifying the special cases of interest for which such efficient algorithms are actually possible.