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 4 No Slides
Remaining Lectures: Class notes. No slides.