A Unified Framework for Balancing Robustness, Effectiveness, and Fairness in Online Mechanism Design

互联网作为计算和通信的全球平台的出现已经引发了许多大规模联网系统（例如，云计算、智能电网和拼车平台）。通常，这些系统可以被建模为相互作用的网络，自私的代理人，在不同形式的动态和不确定性下共享和竞争有限的资源。研究如何在动态、不确定和战略环境中顺序分配资源，称为顺序多智能体资源分配（SMARA），是计算机科学、经济学和运筹学中具有重要科学意义的课题。也许不足为奇的是，SMARA的研究面临着两个相互关联的挑战：i）观察在线或顺序输入的因果性质表明当前的决策影响未来，ii）战略和自利行为的存在意味着没有代理人是独立的，因为它们都影响彼此的决策。在线机制设计（online mechanism design，online MD）将在线算法（机制设计）的理论推广到战略（动态）环境中，这为开发在线机制提供了一种严格的方法，可以在同一框架内解决这两个挑战。换句话说，在线机制在在线算法的意义上不知道未来的情况下运行，并且在激励机制的意义上也促进了自利代理人的期望行为模式。 然而，尽管在过去的几十年里取得了巨大的进步，在线MD的研究通常采用最坏情况的分析框架，这往往导致在线机制过于悲观，效率较低，在某些情况下甚至完全无用（因为最坏情况很少发生在现实中）。此外，各种学科从截然不同的角度研究了在线MD，这阻碍了系统的、合作的和一致的努力来解决现有的和新出现的挑战（例如，在SMARA的背景下，公平性问题。为了解决在线MD中的这些基本挑战，该计划致力于建立一个统一的框架，用于开发在线算法和机制，打破“最坏的设计”和“最好的希望”的诅咒，并遵循可解释性和可解释性的原则，允许人类用户理解，信任并最终受益。作为一个高度跨学科的计划，该计划的理论成果将在包括计算机科学，运筹学，经济学和控制在内的各个学科产生基本的科学影响。此外，该计划致力于缩小理论与应用之间的差距，旨在为许多具有大规模社会经济，环境和工程影响的新兴网络系统的设计和运营提供新的见解，例如电动汽车充电网络，乘车平台和智能电网。

The emergence of the Internet as a global platform for computation and communication has sparked the development of many large-scale networked systems (e.g., cloud computing, smart grid, and ridesharing platforms). Often these systems can be modelled as networks of interacting, self-interested agents, sharing and competing for limited resources under different forms of dynamics and uncertainty. The study of how to sequentially allocate resources in such dynamic, uncertain, and strategic environments, termed Sequential Multi-Agent Resource Allocation (SMARA), is a topic with basic scientific importance in computer science, economics, and operations research. Perhaps unsurprisingly, the study of SMARA faces two interrelated challenges: i) the causal nature of observing online or sequential inputs indicates that current decisions influence the future, and ii) the existence of strategic and self-interested behaviors implies that no agent is independent as they all influence each other's decisions. Online mechanism design (online MD) generalizes the theory of online algorithms (mechanism design) to apply to strategic (dynamic) environments, which provides a rigorous approach to developing online mechanisms that address these two challenges within the same framework. In other words, an online mechanism operates without knowledge of the future in the sense of online algorithms, and also promotes desired behavioral patterns from self-interested agents in the sense of incentive mechanisms. However, despite the tremendous progress made over the past decades, the study of online MD typically adopts the worst-case analysis framework, which often leads to online mechanisms that are overly pessimistic, less effective, and in some cases even totally useless (since worst-case rarely happens in reality). In addition, online MD has been studied by various disciplines from vastly different perspectives, hindering a systematic, cooperative, and coherent effort to address existing and emerging challenges (e.g., fairness concerns) in the context of SMARA. To address these foundational challenges in online MD, this program strives to establish a unified framework for developing online algorithms and mechanisms that break the curse of "design for the worst" and "hope for the best," and follow the principles of interpretability and explainability that allows human users to comprehend, trust, and eventually, benefit from. As a highly interdisciplinary program, the theoretical results of this program will yield fundamental scientific impacts in various disciplines including computer science, operations research, economics, and control. In addition, this program strives to close the gap between theory and applications, and aims to develop new insights into the design and operation of many emerging networked systems with large-scale socio-economic, environmental, and engineering impacts, such as electric vehicle charging networks, ridesharing platforms, and smart grids.