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