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.