This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||

teaching:ss19:vl-agt [2019/04/15 17:01] kesselheim |
teaching:ss19:vl-agt [2019/07/10 15:15] kesselheim [Lecture Notes] |
||
---|---|---|---|

Line 1: | Line 1: | ||

====== MA-INF 1301: Algorithmic Game Theory and the Internet ====== | ====== MA-INF 1301: Algorithmic Game Theory and the Internet ====== | ||

+ | |||

+ | ===== Next Semester ===== | ||

+ | Next semester, we will offer a [[teaching:ws19:seminar-agt|seminar]] and a [[teaching:ws1920:lab-kesselheim|lab]], which are both on topics of algorithmic game theory. Please contact [[staff:thomaskesselheim|Thomas Kesselheim]] if you are interested. The lab will probably much more fun with many participants. | ||

===== Lecture ===== | ===== Lecture ===== | ||

Line 11: | Line 14: | ||

|Thursday, 10:15-11:45 | 2.050 | April 11 | [[staff:matthiasbuttkus|Buttkus]] | | |Thursday, 10:15-11:45 | 2.050 | April 11 | [[staff:matthiasbuttkus|Buttkus]] | | ||

|Thursday, 14:15-15:45 | 2.050 | April 11 | [[staff:matthiasbuttkus|Buttkus]] | | |Thursday, 14:15-15:45 | 2.050 | April 11 | [[staff:matthiasbuttkus|Buttkus]] | | ||

+ | |||

+ | ===== Exams ===== | ||

+ | To be assigned a time slot for the exam, please send an e-mail to [[staff:thomaskesselheim|Thomas Kesselheim]]. In the first period, we still have a few slots available on July 22. In the second period, exams will be on September 11 and 12. Please specify your preferences in the e-mail. | ||

+ | |||

+ | One more thing: If you have been assigned a time slot but then decide to not take the exam, please remember to cancel it. It is very important for us to know that you will not show up because otherwise we will be waiting for you. In this case, send an e-mail to [[staff:thomaskesselheim|Thomas Kesselheim]]. Even a last-minute cancellation is better than a no-show. Of course, make sure that you also follow the official procedures (if applicable). | ||

===== Content ===== | ===== Content ===== | ||

Throughout the world of modern computer networks, there are environments in which participants act strategically. Just consider internet service providers, which strive to route packets as cheaply as possible. Another example are cloud-based services: End-users and service providers rent remote infrastructure for storage or computations, giving rise to huge markets. Last but not least, advertisers want to reach their audience as cheaply as possible. This is the foundation of the business models of the world’s largest companies. | Throughout the world of modern computer networks, there are environments in which participants act strategically. Just consider internet service providers, which strive to route packets as cheaply as possible. Another example are cloud-based services: End-users and service providers rent remote infrastructure for storage or computations, giving rise to huge markets. Last but not least, advertisers want to reach their audience as cheaply as possible. This is the foundation of the business models of the world’s largest companies. | ||

Line 34: | Line 42: | ||

* {{:teaching:ss19:vl-agt:lecturenotes04.pdf|Lecture Notes Apr 10, 2019 (Nash's Theorem)}} | * {{:teaching:ss19:vl-agt:lecturenotes04.pdf|Lecture Notes Apr 10, 2019 (Nash's Theorem)}} | ||

* {{:teaching:ss19:vl-agt:lecturenotes05.pdf|Lecture Notes Apr 15, 2019 (Complexity of Equilibria)}} | * {{:teaching:ss19:vl-agt:lecturenotes05.pdf|Lecture Notes Apr 15, 2019 (Complexity of Equilibria)}} | ||

- | * {{:teaching:ss19:vl-agt:lecturenotes06.pdf|Lecture Notes Apr 17, 2019 (Correlated Equilibria)}} (preview) | + | * {{:teaching:ss19:vl-agt:lecturenotes06.pdf|Lecture Notes Apr 17, 2019 (Correlated Equilibria)}} (update Apr 23: Corrected another typo in definition) |

- | * | + | * {{:teaching:ss19:vl-agt:lecturenotes07.pdf|Lecture Notes Apr 24, 2019 (Minimizing External Regret)}} (update May 16: fixed typo in proof of Proposition 7.6) |

+ | * {{:teaching:ss19:vl-agt:lecturenotes08.pdf|Lecture Notes Apr 29, 2019 (Price of Anarchy)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes09.pdf|Lecture Notes May 6, 2019 (Cost and Market Sharing Games)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes10.pdf|Lecture Notes May 8, 2019 (Introduction to Mechanism Design)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes11.pdf|Lecture Notes May 13, 2019 (Single-Parameter Mechanisms)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes12.pdf|Lecture Notes May 20, 2019 (Approximation Algorithms for Combinatorial Auctions)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes13.pdf|Lecture Notes May 22, 2019 (VCG Mechanism)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes14.pdf|Lecture Notes May 27, 2019 (Bayes-Nash equilibria)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes15.pdf|Lecture Notes May 29, 2019 (Smooth Mechanisms)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes16.pdf|Lecture Notes Jun 3, 2019 (Simple Combinatorial Auctions)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes17.pdf|Lecture Notes Jun 5, 2019 (Revenue Maximization)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes18.pdf|Lecture Notes Jun 17, 2019 (Revenue Maximization with Identical Distributions)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes19.pdf|Lecture Notes Jun 19, 2019 (Allocations without Money)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes20.pdf|Lecture Notes Jun 24, 2019 (Walrasian Equilibria)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes21.pdf|Lecture Notes Jun 26, 2019 (Posted Prices with Incomplete Information)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes22.pdf|Lecture Notes Jul 1, 2019 (Stable Matching)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes23.pdf|Lecture Notes Jul 3, 2019 (Cake Cutting)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes24.pdf|Lecture Notes Jul 8, 2019 (Voting)}} | ||

+ | * {{:teaching:ss19:vl-agt:lecturenotes25.pdf|Lecture Notes Jul 10, 2019 (Cost Sharing)}} (Corrected proof of Lemma 25.7 in comparison to lecture.) | ||

===== Exercises ===== | ===== Exercises ===== | ||

* {{:teaching:ss19:vl-agt:uebungsblatt01.pdf|Exercise Set 1, due Apr 10}} | * {{:teaching:ss19:vl-agt:uebungsblatt01.pdf|Exercise Set 1, due Apr 10}} | ||

* {{:teaching:ss19:vl-agt:uebungsblatt02.pdf|Exercise Set 2, due Apr 17}} | * {{:teaching:ss19:vl-agt:uebungsblatt02.pdf|Exercise Set 2, due Apr 17}} | ||

* {{:teaching:ss19:vl-agt:uebungsblatt03.pdf|Exercise Set 3, due Apr 24}} | * {{:teaching:ss19:vl-agt:uebungsblatt03.pdf|Exercise Set 3, due Apr 24}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt04.pdf|Exercise Set 4, due Apr 30}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt05.pdf|Exercise Set 5, due May 8}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt06.pdf|Exercise Set 6, due May 15}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt07.pdf|Exercise Set 7, due May 22}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt08.pdf|Exercise Set 8, due May 29}} (update May 21: fixed reference in exercise 5b) | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt09.pdf|Exercise Set 9, due June 5}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt10.pdf|Exercise Set 10, due June 19}} (updated due date) | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt11.pdf|Exercise Set 11, due June 26}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt12.pdf|Exercise Set 12, due July 3}} | ||

+ | * {{:teaching:ss19:vl-agt:uebungsblatt13.pdf|Exercise Set 13, due July 10}} | ||

===== Further Reading ===== | ===== Further Reading ===== |