References for Algorithmic Game Theory

Computational Social Choice (CSC) may be defined as:

an interdisciplinary field of study at the interface of social choice theory and computer science, promoting an exchange of ideas in both directions.

The field intersects computer science, economics, and operations research and focuses on algorithmic aspects of group decision making and resource allocation. This page summarizes relevant resources for researchers in CSC and its umbrella discipline of Algorithmic Game Theory.

About Computational Social Choice

Textbooks

Springer book series – Synthesis Lectures on Artificial Intelligence and Machine Learning:

More COMSOC

Applications of AGT: Simulations and Online Programs

Data and Github Repositories

Tools and Techniques

Courses

Important Computer Science Conferences

Conference Name Rating* Link Approx. Deadline Conference Dates
AAAI Conference on Artificial Intelligence A* link August February
International Joint Conference on Artificial Intelligence (IJCAI) A* link January August
Conference on Neural Information Processing Systems (NeurIPS) A* link May December
Conference on Uncertainty in Artificial Intelligence (UAI) A link February July-Aug
International Symposium on Algorithmic Game Theory (SAGT) B link May September
European Conference on Artificial Intelligence (ECAI) A link April Sept-Oct
ACM Conference on Economics and Computation (EC) A* link January July
Conference On Web And Internet Economics (WINE)   link July December
International Conference on Autonomous Agents and Multiagent Systems (AAMAS) A* link October May-June$^{+1}$
International Workshop on Computational Social Choice (COMSOC)   link March July
The Web Conference (WWW) A* link October May$^{+1}$

*Ratings per Computing Research and Education Association of Australasia, CORE Inc.

Open Repositories of Ongoing Research

  • CS rankings for ranking US graduate programs in computer science

Key Concepts from EconCS

A collection of models and concepts showing how collective patterns and order emerge from interactions among self-interested, adaptive agents, spanning equilibria, learning, networks, and social choice. It highlights the mechanisms behind emergent stability, coordination, and cascading effects. Inspired in part by Scott Page’s class on Model Thinking. [Coursera Link]

Game Theory

  • Equilibrium concepts:
    • Nash equilibrium
    • Subgame perfect equilibrium
    • Correlated equilibrium
    • Evolutionary stable strategy
    • Minimax theorem
  • Strategic interactions:
    • Prisoner’s dilemma
    • Tit-for-tat
    • Public goods games
    • Graphical games (Kearns, Littman, and Singh (2001))
    • Shapley values
  • Mechanisms and Market designs:
    • Vickrey–Clarke–Groves auction
    • Price of Anarchy
    • Bayesian persuasion
    • Arrow’s impossibility theorem
    • Gibbard-Satterthwaite impossibility theorem
    • Myerson–Satterthwaite impossibility theorem
    • Median voter theorem
    • Revelation principle
  • Dynamic systems and complexity:
    • Lotka-Volterra predator-prey system
    • Poincaré–Bendixson theorem
    • Conway’s game of life
    • Lyapunov function; potential games
    • Finite improvement property
    • Network formation games (see e.g., Jackson and Wolinsky (1996))

Economics and Computer Science

  • Learning and online decision-making:
    • Multiplicative Weights Update (aka Hedge) (Littlestone and Warmuth (1992))
    • Mirror descent algorithm
    • Boosting (Sharpe (1997); Freund and Scharpe (1997))
    • Replicator dynamics (see Krichene, Drighes, and Bayen (2014))
    • Fictitious Play (Brown (1951); Foster and Young (1998))
    • Regret matching / no-regret learning (Hart and Mas-Colell (2000))
    • Logit response
    • Follow the Regularized Leader
  • Ranking and voting:
    • Bradley-Terry-Luce model of pairwise comparisons (in general, Plackett-Luce)
    • Kemeny-Young method
    • Condorcet’s jury theorem
  • Matching and networks:
    • Gale-Shapley algorithm for stable matching
    • PageRank (Brin and Page (1998)); HITS (Kleinberg (1998))
    • Influence Maximization (Kempe, Kleinberg, and Tardos (2003))
      • Independent Cascade Model
      • Linear Threshold Model (Granovetter (1978))
  • Bandits and exploration:
    • Upper Confidence Bound (UCB) for the multi-armed bandit problem
    • Thompson Sampling
    • Stochastic games
    • Partially Observable Markov Decision Process

Complex Systems and Cognitive Science

  • Cognitive and Behavioral:
    • Prospect theory (Kahneman and Tversky (1979))
    • Cognitive Hierarchy Models (Camerer, Ho, and Chong (2004))
    • Cognitive architectures (ACT-R, Soar, CLARION, EPIC)
    • Standing Ovation Model (Miller and Page (2004))
    • Schelling’s model of segregation (Schelling (1971))
  • Statistical physics and emergent phenomena:
    • Kuramoto model
    • Information cascades (Bikhchandani, Hirshleifer, and Welch (1992))
    • SIR model
    • Interacting Particle Systems (Liggett (1985))
    • Ising model
    • Boltzmann machine
    • Hopfield networks
    • Abelian Sandpile Model
    • Percolation theory
    • Sensitivity analysis
  • Network theory
    • Watts-Strogatz small-world networks
    • Erdős–Rényi random graphs
    • Barabási-Albert model
Written on July 10, 2023