cs715: Advanced Topics in Algorithmic Game Theory and Mechanism Design

Summary:

Contents:

Game theory is a mathematical model to analyse and predict behavior of strategic agents. In the modern world, where

every individual has access to the Internet and immense computing power, game theory has become an important, useful

and relevant tool in day to day life to design protocols in various contexts, analyze negotiations or induce cooperation.

Mechanism Design Theory, an important branch in game theory, is a design of games with the participants having

private information based on which certain decisions are to be made that are optimal in some sense. These mechanisms

pose interesting algorithmic challenges. Often the underlying problems can not be solved exactly by an

efficient algorithm. Hence, these problems need to be solved approximately while ensuring that the game theoretic properties are

still maintained. This leads to Algorithmic Mechanism Design. This course is intended for doctoral students who have basic

knowledge in game theory, optimization theory and algorithm design. The course will cover some of the recent advances

in algorithmic mechanism design which lie on the interface between economics and computer science: Econ-CS. In

particular, the following topics will be covered:

1. Introduction to Game Theory, Mechanism Design and Algorithmic Mechanism Design (3hrs)

2. Optimal Bayesian Mechanism Design (9hrs)

3. Algorithms for Truthful Multi-item Combinatorial Auctions (Monograph by Noam Nisan) (7.5hrs)

4. Online Mechanism Design (1.5-3hrs)

5. Mechanism Design without Money. (3hrs)

6. Presentations by the participants

Each participant is required to present one recent paper, published in a reputed international conference, related to game

theory and mechanism design. Apart from the presentation, the participants are expected to submit a report on the paper,

that was presented. The report should be self-explanatory with detailed explanation of proofs from the paper.

Learning Outcomes:

1. Explain Truthfulness, Bayesian Incentive Compatibility and Individual Rationality of an algorithm

involving strategic and rational agents

2. Define an Optimal Bayesian Auction for selling multiple units of multiple items in additive value settings

3. Define Competitive Ratio for an online algorithm to sell items to dynamically arriving agents

4. Define mechanisms for exchanging objects or matching agents when monetary transfers are not allowed

5. Define and analyse Separating Oracle (SO) and Corner Oracle (CO) for designing optimal Bayesian Auctions

6. Analyse a given algorithm and verify properties such as truthfulness, Bayesian incentive compatibility

7. Evaluate various truthful algorithms for multi-unit auctions for approximation ratio

8. Design and analyse mechanism without money for stability and efficiency

9. Characterize the Bayesian Incentive Compatible mechanisms in various settings

10. Design new algorithms catering to strategic and dynamic behaviour of the participating agents in various contexts

such as auctions, object allocation, resource exchange etc.

11. Present and explain recent algorithms and results to the specific audience comfortable in the topic

12. Write a scientific or a technical report

==================

Outcomes:

1-4 are Low-level cognitive outcomes

5-6 are Med-level cognitive outcomes

7-10 are Higher cognitive outcomes

11-12 are Transversal Skills

Slides:

Lecture 1

Lecture 2

Lecture 3

Lecture 4 No Slides

Lecture 5

Lecture 6

Lecture 7

Remaining Lectures: Class notes. No slides.