AF: Small: Problems in Algorithmic Game Theory for Online Markets

四分之一个世纪以前，理论计算机科学的研究被互联网的出现所改变。这个新的和关键的计算工件需要一个新的数学建模、思想和技术库来研究。由于市场和激励在新的计算环境的功能和演变中发挥着重要作用，博弈论和微观经济学的计算分支最终在互联网的启发下发展起来。这一新领域被称为算法博弈论，它将算法思维与经济考虑相结合，对当今复杂的计算环境产生了至关重要的见解，其中包括互联网和人工智能（AI）。该项目的目标是解决算法博弈论中近年来出现的新一代开放性问题。这项研究的结果可能会对理论计算机科学以外的经济学和博弈论以及机器学习产生影响。本项目将探索的研究方向包括：(1)基于游戏的动态性，开发与游戏新应用更相关、对计算更友好的新解概念；并解决一些关于博弈和市场均衡的基本开放性问题的复杂性。(2)研究在线市场和平台中的新公式和问题，以及解决与在匹配市场中实现各种均衡概念相关的某些计算问题。(3)研究在线市场和机器学习系统中与公平和不公平相关的一些新问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A quarter of a century ago, research in Theoretical Computer Science was transformed by the advent of the Internet. This new and crucial computational artifact requires for its study a new arsenal of mathematical modeling, ideas and techniques. Since markets and incentives play an important role in the function and evolution of the new computational environment, computational branches of Game Theory and Microeconomics were eventually developed, inspired by the Internet. The new field thus created, dubbed Algorithmic Game Theory, combined algorithmic thinking with economic considerations, and has produced crucial insights into today's complex computational environment, which encompasses both the Internet and artificial intelligence (AI). The goal of this project is to address a new generation of open questions in Algorithmic Game Theory that have emerged in recent years. Results from this research are likely to have an impact beyond Theoretical Computer Science to Economics and Game Theory, as well as Machine Learning. The research directions that will be explored in this project include the following: (1) Develop new solution concepts that are more pertinent to the new applications of games and more friendly to computation, based on the dynamics of games; and address the complexity of some basic open questions regarding equilibria in games and markets. (2) Investigate novel formulations and problems in on-line markets and platforms, as well as address certain computational problems related to achieving various notions of equilibrium in matching markets. (3) Study certain novel problems related to fairness and inequity in online markets and machine learning systems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.