Aarhus University Seal

Algorithmic Game Theory

Algorithmic Game Theory (AGT) is a field that combines concepts from algorithm design and game theory to examine the interplay between incentives and computation. It is particularly relevant in settings where diverse entities, such as individuals, organizations, or industries, with varying and sometimes conflicting objectives interact in open, decentralized environments like the Internet. Their strategic behavior is typically modeled as participation in games, where outcomes are determined by their interactions. AGT tackles several key challenges, three of which are briefly outlined below:

  • Mechanism design, which develops algorithms that encourage participants to reveal their private information truthfully.
  • The price of anarchy, a measure of the inefficiency caused by selfish or non-cooperative behavior.
  • The computational complexity of equilibria explores which equilibrium concepts can be efficiently computed and which involve inherent algorithmic difficulties.

Our group contributes to a wide range of AGT topics, including mechanism design for auctions, matching markets, and voting systems; analysis of the price of anarchy in various games; and the study of equilibrium computation and related fixed-point problems.

Social Impact

The modern interconnected environment offers access to vast sources of knowledge, a wide array of services such as AI agents, web search, social media, and cloud computing, and an immense pool of computational and storage resources. New applications emerge continuously, leveraging these capabilities, attracting users, and driving further growth of the digital ecosystem. Yet, these applications face significant challenges. Infrastructures and services are owned and managed by diverse stakeholders: individuals, corporations, and institutions. Access to these resources often depends on the incentives of their owners and users, who may behave strategically and not in the way anticipated during the system design phase. 

While incentive-aware design is well-established in applications with explicit economic goals, such as online marketplaces and advertising platforms that rely on auction mechanisms—the relevance of incentives extends far beyond purely economic contexts. Strategic behavior is pervasive in today’s interconnected systems and must be considered in the design of virtually any digital application. This is where algorithmic game theory plays a pivotal role. By combining tools from computer science and economics, it enables the systematic study and design of systems that are robust to strategic behavior. As digital infrastructure becomes more complex and interdependent, the societal impact of this line of research grows—ensuring fairness, efficiency, and resilience in the systems that shape our daily lives.

Key publications

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender
PPAD-Membership for Problems with Exact Rational Solutions: A General Approach via Convex Optimization (STOC'24)

Ioannis Caragiannis, Zhile Jiang
Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming (STOC'23)

Volkan Cevher, Ashok Cutkosky, Ali Kavis, Georgios Piliouras, Stratis Skoulakis, Luca Viano
Alternation makes the adversary weaker in two-player games (NeurIPS'23) 

Aris Filos-Ratsikas, Kristoffer Arnsfelt Hansen, Kasper Høgh, Alexandros Hollender
FIXP-membership via Convex Optimization: Games, Cakes, and Markets (FOCS'21) 

Constantinos Daskalakis, Stratis Skoulakis, Manolis Zampetakis
The complexity of constrained min-max optimization (STOC'21)