Aims

  • To provide an understanding of the inefficiency arising from uncontrolled, decentralised resource allocation.

  • To provide a foundation for modelling various mechanism design problems together with their algorithmic aspects.

  • To provide the tools and paradigms for the design and analysis of efficient algorithms/mechanisms that are robust in environments that involve interactions of selfish agents.

  • To review the links and interconnections between algorithms and computational issues with selfish agents.

  • To provide an in-depth, systematic and critical understanding of selected significant topics related to algorithmic game theory and mechanism design, together with the related research issues.

Learning outcomes

  • A critical awareness of current problems, important concepts and research issues in the field of algorithmic game theory and mechanism design. For example, algorithmic efficiency, incentive compatibility, maximization of social welfare, and their impact on the revenue raised by the auction.

  • Systematic knowledge and ability to quantify the inefficiency of equilibria.

  • The ability to formulate mechanism design models or network games for the purpose of modelling particular applications.

  • Detailed understanding and the ability to use, describe and explain appropriate algorithmic paradigms and techniques in context of a particular game-theoretic or mechanism design problem.

  • The ability to read, understand and communicate research literature in the field of algorithmic game theory and mechanism design.

  • The ability to recognise potential research opportunities and research directions in the field of algorithmic game theory and mechanism design.

Outline

  • Introduction to Game Theory - Network Games(Ch. 1, Ch. 17)

  • Load-Balancing Games (Ch. 20)

  • Routing Games (Ch. 18)

  • Formation Games (Ch.19)

  • Introduction to Mechanism Design (Ch. 9)

  • Mechanisms Without Money (Ch. 10)

  • Combinatorial Auctions (Ch. 11)

  • Profit Maximization (Ch. 13)

  • Current Trends on Algorithmic Mechanism Design (Research Papers)

Mechanism Design

  • Reverse engineering in Game Theory

Auctions

  • Goal: Give the object to the player with maximum value.

Algorithmic Game Theory

  • It is an area in the intersection of game theory and algorithm design, whose objective is to design algorithms in strategic environments. [Nisan et al. 2007]

  • It is multidiscriplinary:

    1. AI -> Multi Agent Systems -> Algprithmic Game Theory

    2. Economics

    3. Theoretical Computer Science