Grant: Discovery Grants Program - Individual
University of Alberta
$29,000.00
A Unified Framework for Balancing Robustness, Effectiveness, and Fairness in Online Mechanism Design
FY 2023-24
Summary
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.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-03646
Name nom
Tan, Xiaoqi
Department département
Department of Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2022
Award amount
29000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2715
Research subject group en
Information technology
Research subject group fr
Optimization
Research subject en
Technologie de l'information
Research subject fr
Optimisation
Application title
A Unified Framework for Balancing Robustness, Effectiveness, and Fairness in Online Mechanism Design
Keyword
Beyond Worst Case Analysis; Competitive Analysis; Fairness; Mechanism Design; Online Algorithms; Resource Allocation
Application summary
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.