Algorithms and Complexity for Economic Environments (ACEE)

经济环境的算法和复杂性 (ACEE)

• 批准号: EP/Y003624/1
• 负责人: Aris Filos-Ratsikas
• 金额: $ 50.27万
• 依托单位: University of Edinburgh
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FY003624%2F1
• 关键词: Algorithms; Complexity; Economic; Environments; ACEE

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.

该项目研究了在经济环境中找到稳定和理想结果的计算复杂性。此类环境的示例是： - 商品拍卖，例如“传统”商品，例如汽车，绘画等，或其他商品，例如资产或频谱。-涉及几个买卖双方的市场，例如用于消费商品，资产或广告空间的市场。-在这些资源中，一组资源是在这些资源中的一组资源，这些资源都在这些资源中，这些资源是不同的，这些资源是不同的，这些资源是不同的。例如，一个人可能有兴趣在企业的员工之间分配任务，或者为他们在项目上的工作，分配租金或家庭成员之间的票价或在家庭成员之间分裂继承而分配信用。 - 在拍卖中，这种结果是买家之间战略互动的纳什均衡。考虑到其他投标人的竞标，这些是买家对买家感到满意的货币投标集。 - 对于市场而言，这些结果是竞争性的平衡，在每个商品的价格上，其供应等于其需求，并且参与者以给定的价格获得了最佳的商品捆绑。 - 对于资源划分，稳定的结果是每个参与者认为是公平的资源的分区，他们根据自己对资源可以分配的可能方式的偏好。在上个世纪的大部分时间里，跨越经济学，数学和计算机科学的大型跨学科社区对这些经济环境进行了广泛的研究。经济学和数学方面的经典作品已经证明，对于非常笼统的环境，这种稳定的结果始终存在，即，有可能同时满足所有环境的所有参与者。计算机科学的研究在制定和研究主要后续问题方面发挥了作用：“我们如何找到这些稳定的态度？”简而言之，我们关心的是是否可以设计有效的算法来查找这些结果，即在计算机上运行时在合理的时间内完成任务的算法。尽管如此，尽管社区付出了巨大的努力，但我们没有有效的算法来在许多主要的经济环境中找到稳定的成果，例如上面突出显示的经济环境，而且我们不知道是否有可能设计它们。该项目旨在为这个问题的四个主要经济环境提供具体的答案，即1）拍卖2）市场3）公平的分配资源4）公平的资源分配了不可分割的资源，我们将设计有效的算法，以设计这些环境的相应稳定性，我们将不得算法构成算法的效果，或者我们不得依靠这些算法来实施验证效果。我们的结果将为研究社区提供有关这些问题“简单”，哪些问题“很难”解决的研究社区。他们将帮助研究人员和从业人员（a）理解试图为这些环境提出良好解决方案的固有挑战，（b）为这些环境提出适当的后续问题，以及（c）确定实际上可能有可能有效的算法的特殊案例。