Reshef Meir's course at IE&M next semester | |
|
חישוב, תורת המשחקים וכלכלה קורס מספר 096226 Tuesday 11:30-13:30 (tirgul Wednesday 9:30-10:30) The connections between computational and economic challenges are bi-directional. In the first direction, we want to perform some algorithmic task, such as computing a shortest path or optimal allocation when the input is based on strategic behavior. Tools from game theory may help us analyze and sometimes prevent such behavior. In the other direction, computational tools provide us with useful language to describe complicated utility functions, and metrics to evaluate economic notions such as welfare and stability. In the course we will see some prominent examples to both types of contibutions, and see how classic concepts in computer science such as LP duality and graph algorithms play a major role in the relatively new area of computational game theory. Who is it for? Students in semester 5+, with computational background (CS, OR, combinatorics, etc.) who are interested in game theory. Formal prequisites: a course in probablity (one of: 094411 094412 094481 104034 094417 104222, or another with approval) Grade will be based on a final exam + midterm exercise. Students will be able to do a final project instead if interested. Basics: NP-hardness, LP duality, Graph theory: flow, tree-width Classes 1-5. Games on graphs. Class 1: Read [Roughgarden and Tardos’02] The Braess paradox (rubber band experiment!) How bad can it get? Recall the question for later Nonatomic Routing games Price of Anarchy Computation of Wardrop equilibrium? Class 2-3: Read [Rosenthal’73] Atomic congestion games Prisoners’ dilemma Potential games Smoothness Class 4: Read [Kearns et al.’01] Graphical games https://www.cis.upenn.edu/~mkearns/papers/agt-kearns.pdf Class 5: Network Games and recurrent neural networks Tamuz: https://link.springer.com/article/10.1007/s10458-013-9230-4 Bruck: https://authors.library.caltech.edu/30372/1/BRUprocieee90.pdf Classes 6-13. Mechanism design. Class 6: Read [Monderer and Tennenholtz’04, sections 1-4] k-implementation Class 7-8: Implementation theory Gibbard-Satterthwaite Facility location mechanisms Implementation with money (VCG) Class 9-10: Read [Porter et al.’08] Fault tolerant mechcanisms Demand response Class 11-12: Mechanism design in routing games: Tolls, Bicriteria bound, biases Possible additional topic: Cooperative games. Read chapters from the book Representation, MC-nets |
| פורסם ב-10/2/2019, 15:45:19 Created on 10/2/2019, 15:45:19 Создано10/2/2019, 15:45:19 تم النشر ب-10/2/2019, 15:45:19 |
HW2 grades are online! | |
| The graded papers were handed to the secretariat |
| פורסם ב-5/2/2019, 15:15:41 Created on 5/2/2019, 15:15:41 Создано5/2/2019, 15:15:41 تم النشر ب-5/2/2019, 15:15:41 |
הרצאה ביום חמישי | |
|
Time+Place: Thursday 07/02/2019 14:30 room 337 Taub Bld. Speaker: Prof. Tim Roughgraden - SPECIAL DISTINGUISHED LECTURE - note unusual date Affiliation: Columbia University Title: Distribution-free models of social and information networks Abstract: The mathematical study of social and information networks has historically centered around generative models for such networks (preferential attachment, the Chung-Lu random graph model, Kronecker graphs, etc.). This talk proposes distribution-free models of social and information networks - novel classes of graphs that capture all plausible such networks. Our models are motivated by triadic closure, the property that vertices with one or more mutual neighbors tend to also be neighbors; this is one of the most universal signatures of social networks. We prove structural results on the clustering properties of such graphs, and give algorithmic applications to clustering and clique-finding problems. Includes joint work with Jacob Fox, Rishi Gupta, C. Seshadhri, Fan Wei, and Nicole Wein. Short Bio: ============ Tim Roughgarden is a Professor of Computer Science at Columbia University. Prior to joining Columbia, he spent 15 years on the Computer Science Faculty at Stanford, following a PhD at Cornell and a postdoc at UC Berkeley. His research interests include the many connections between computer science and economics, as well as the design, analysis, applications, and limitations of algorithms. For his research, he has been awarded the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Society's Tucker Prize, and the EATCS-SIGACT Goedel Prize. He was an invited speaker at the 2006 International Congress of Mathematicians, the Shapley Lecturer at the 2008 World Congress of the Game Theory Society, and a Guggenheim Fellow in 2017. His books include Twenty Lectures on Algorithmic Game Theory (2016) and the Algorithms Illuminated book series (2017-2019). ======================================= Refreshments will be served from 14:15 Lecture starts at 14:30 ---------------------------------------------------------- Visit our home page- http://www.cs.technion.ac.il/~colloq |
| פורסם ב-4/2/2019, 17:49:38 Created on 4/2/2019, 17:49:38 Создано4/2/2019, 17:49:38 تم النشر ب-4/2/2019, 17:49:38 |
HW3 postponement | |
|
Hi, You can submit HW3 until Thursday (25.1) at 16:30 to Ohad's cell at the 5th floor. Questions regarding the assignments please send to Ohad by email. If it will be necessary, Ohad will hold a reception hour regarding the assignment. |
| עדכון אחרון ב-17/1/2019, 12:32:11 Last updated on 17/1/2019, 12:32:11 Последняя модификация17/1/2019, 12:32:11 تمت الحتلنة الأخيرة ب-17/1/2019, 12:32:11 |
Tomorrow (Jan 14) | |
|
As discussed in class, tomorrow we will end the lecture a bit early. If you want to hear about "simple vs. optimal contracts", you're welcome to my talk at 11:30 at the Game Theory Seminar, Bloomfield 527 Industrial Engineering and Management (I'll be walking there after class). |
| עדכון אחרון ב-13/1/2019, 19:09:18 Last updated on 13/1/2019, 19:09:18 Последняя модификация13/1/2019, 19:09:18 تمت الحتلنة الأخيرة ب-13/1/2019, 19:09:18 |
Mid-term reports | |
|
The final project document is updated - please verify that you appear in green if you submitted or notified about special circumstances. If you haven't submitted the mid-term but plan on submitting the final report please contact Inbal. https://docs.google.com/document/d/1kXMpig2wg1XxgjfmfHUBHpXVsjlEJC2_P74CUcaC8kc/edit?usp=sharing |
| פורסם ב-7/1/2019, 22:37:19 Created on 7/1/2019, 22:37:19 Создано7/1/2019, 22:37:19 تم النشر ب-7/1/2019, 22:37:19 |
AGT-related theory lunch talk this Wed | |
|
On Wednesday Jan 9 at 12:30 there will be a talk on the following paper in Taub 201: https://arxiv.org/abs/1811.06114 Title: Prophet Inequalities for Independent Random Variables from an Unknown Distribution Speaker: Paul Duetting, London School of Economics Come at 12:15 for lunch. |
| פורסם ב-3/1/2019, 21:46:42 Created on 3/1/2019, 21:46:42 Создано3/1/2019, 21:46:42 تم النشر ب-3/1/2019, 21:46:42 |
HW3 and updated (final) schedule | |
|
For HW3 please solve the following (the same rules as for previous homework assignments apply, except you are allowed - but not required - to submit in pairs): Equilibrium concepts: Exercise 13.3 Smooth games: Exercise 14.5 No regret: Exercise 17.4, Problem 17.2 Zero-sum games: Exercise 18.6 Mixed Nash equilibrium computation: Problem 20.1 For bonus points: Problem 18.4 (requires familiarity with linear programming) Updated course schedule (with submission date): https://docs.google.com/document/d/1dXa00Yx5II10qLccs3clt0qzZLtrpMsZnqZZY-3qsZs/edit?usp=sharing |
| פורסם ב-30/12/2018, 23:27:43 Created on 30/12/2018, 23:27:43 Создано30/12/2018, 23:27:43 تم النشر ب-30/12/2018, 23:27:43 |
Project midterm report due Mon Jan 7 | |
|
As agreed upon in class you can submit the project midterm report by Mon Jan 7. Please note there will be NO extensions to the project final due date, so plan accordingly: Start the research part of the project ASAP (don't wait for feedback on the midterm report). Good luck! |
| פורסם ב-29/12/2018, 23:07:00 Created on 29/12/2018, 23:07:00 Создано29/12/2018, 23:07:00 تم النشر ب-29/12/2018, 23:07:00 |
תרגיל בית 2 Homework 2 Homework 2 Homework 2 | |
|
Dear all, We apologize for not being as available as we would have liked this week for questions regarding the homework. The deadline is extended until Monday 31st. Re Problem 6.1 (prophet inequality), solve 2 out of the 3 subsections for full credit and 3 out of 3 for extra credit. Re Problem 7.3(c), you can assume the auctioneer chooses the collection S. |
| פורסם ב-23/12/2018, 23:27:56 Created on 23/12/2018, 23:27:56 Создано23/12/2018, 23:27:56 تم النشر ب-23/12/2018, 23:27:56 |
HW 2 deadline extension and other announcements | |
|
Please submit HW 2 by or on Thursday 27th of December. Note we will be extra diligent about verifying *individual* work following issues arising in HW 1. The tex version of the final project template can be found here: https://docs.google.com/document/d/1r9_KmqskMaF8_2yRo9t8oBp4f-hWFa5kQKiK_AzUh5k/edit?usp=sharing See you on Monday! |
| פורסם ב-20/12/2018, 15:00:08 Created on 20/12/2018, 15:00:08 Создано20/12/2018, 15:00:08 تم النشر ب-20/12/2018, 15:00:08 |
Final project | |
|
Please make sure you are correctly listed in the Google doc: https://docs.google.com/document/d/1kXMpig2wg1XxgjfmfHUBHpXVsjlEJC2_P74CUcaC8kc/edit?usp=sharing |
| פורסם ב-10/12/2018, 15:10:48 Created on 10/12/2018, 15:10:48 Создано10/12/2018, 15:10:48 تم النشر ب-10/12/2018, 15:10:48 |
HW2 | |
|
For Homework 2 (out of 3), please solve the following from the course textbook (Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden). Note that the textbook has both "exercises" and "problems", make sure you're solving the right one! Please *work alone and independently* (don't use references besides the course textbook; you're allowed to use the hints at the end of the textbook if you're stuck), type up your solution in Latex, and submit your solution to Ohad’s box (#100) or in class on Monday November 24. Problem 5.1 + Problem 5.2 (Revenue) Exercise 6.1 + Problem 6.1 (Simple auctions) Problem 7.3 (Combinatorial auctions) Exercise 10.6 (Stable matching) |
| פורסם ב-10/12/2018, 15:08:42 Created on 10/12/2018, 15:08:42 Создано10/12/2018, 15:08:42 تم النشر ب-10/12/2018, 15:08:42 |
Course schedule (tentative) | |
|
Please see: https://docs.google.com/document/d/1dXa00Yx5II10qLccs3clt0qzZLtrpMsZnqZZY-3qsZs/edit?usp=sharing |
| פורסם ב-10/12/2018, 15:06:25 Created on 10/12/2018, 15:06:25 Создано10/12/2018, 15:06:25 تم النشر ب-10/12/2018, 15:06:25 |
Final project update | |
|
The final project list has been updated: https://docs.google.com/document/d/1kXMpig2wg1XxgjfmfHUBHpXVsjlEJC2_P74CUcaC8kc/edit?usp=sharing Deadline update: Please pick a topic by Monday Dec 3. |
| פורסם ב-30/11/2018, 14:14:02 Created on 30/11/2018, 14:14:02 Создано30/11/2018, 14:14:02 تم النشر ب-30/11/2018, 14:14:02 |
Final Project | |
|
We uploaded the final project requirements under the tab "תרגילי בית". Please read the instructions carefully. For any further questions regarding the project, please contact Inbal. The following link will be updated according to the paper allocation for the final project: https://drive.google.com/file/d/1u2GyFGS133kLY0x1jmvPTlNUUlWd8-So/view?usp=sharing The final project will be 55% of the final course grade (the other 45% will be for the assignments). Good Luck, Course Staff |
| עדכון אחרון ב-25/11/2018, 15:39:47 Last updated on 25/11/2018, 15:39:47 Последняя модификация25/11/2018, 15:39:47 تمت الحتلنة الأخيرة ب-25/11/2018, 15:39:47 |
AGT day at Weizmann Institute of Science | |
|
Weizmann Institute of Science will hold an AGT day at February 3rd. The conference will include several interesting lectures on AGT. We attach the information link regarding this conference. The registration is free. https://sites.google.com/view/israelagt/home?authuser=0 It is highly recommended for people who are interested in AGT to participate. |
| פורסם ב-25/11/2018, 15:20:51 Created on 25/11/2018, 15:20:51 Создано25/11/2018, 15:20:51 تم النشر ب-25/11/2018, 15:20:51 |
Hw1 submission | |
| Please submit hw1 to Ohad’s mailbox (cell 100) in the 5th floor. |
| פורסם ב-19/11/2018, 08:19:15 Created on 19/11/2018, 08:19:15 Создано19/11/2018, 08:19:15 تم النشر ب-19/11/2018, 08:19:15 |
HW1 and Course Book | |
|
+ https://www.cambridge.org/core/books/twenty-lectures-on-algorithmic-game-theory/A9D9427C8F43E7DAEF8C702755B6D72B This link is a link to the course book, it is available inside the Technion network. + In HW1, some of you claimed that the changes in problem 3.3 were incorrect - Thus, we will accept any answer to this question (the old version or the new version) as long as it is well-explained. Good Luck, Course Staff |
| פורסם ב-14/11/2018, 12:19:41 Created on 14/11/2018, 12:19:41 Создано14/11/2018, 12:19:41 تم النشر ب-14/11/2018, 12:19:41 |
HW1 mistake and deadline change | |
|
Hi, As some of you already noticed there is a mistake in the homework assignment. In Problem 3.2 the payment rule should be modified to a price of max(R/|S|, b_(k+1)) per bidder. In Problem 3.3 prove a weaker statement for the modified auction: -when the number of items k equals the number of bidders n, the Revenue Target Auction is group-strategyproof. Thanks to Shay, Hila and Lior for pointing that out. As a result, you can submit HW1 until November 19. Take into consideration that the 2nd assignment should be published on that day. Good Luck! |
| פורסם ב-6/11/2018, 14:30:53 Created on 6/11/2018, 14:30:53 Создано6/11/2018, 14:30:53 تم النشر ب-6/11/2018, 14:30:53 |
HW1 | |
|
For Homework 1 (out of 3), please solve the following from the course textbook (Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden). Note that the textbook has both "exercises" and "problems", make sure you're solving the right one! Please *work alone and independently* (don't use references besides the course textbook; you're allowed to use the hints at the end of the textbook if you're stuck), type up your solution in Latex, and submit your solution to Ohad at the class of Monday November 12. Exercise 2.3 + Problem 3.2 (k-unit auctions) Exercise 2.8 + Exercise 3.4 (sponsored search – for Exercise 3.4 wait till after the lesson on Monday November 5) Problem 2.2 + Problem 3.3 (collusion) |
| עדכון אחרון ב-30/10/2018, 12:53:19 Last updated on 30/10/2018, 12:53:19 Последняя модификация30/10/2018, 12:53:19 تمت الحتلنة الأخيرة ب-30/10/2018, 12:53:19 |
Late Registration | |
|
If you're an undergrad who wants to take the course for credit but isn't registered, and you signed up during the first lesson, please email Inbal to confirm you're still interested. |
| עדכון אחרון ב-30/10/2018, 12:35:51 Last updated on 30/10/2018, 12:35:51 Последняя модификация30/10/2018, 12:35:51 تمت الحتلنة الأخيرة ب-30/10/2018, 12:35:51 |
Welcome to Algorithmic Game Theory! | |
|
+ Lecture Notes from Stanford course - https://theory.stanford.edu/~tim/notes.html + Online books - - https://www.cambridge.org/files/3914/7629/0049/Algorithmic_Game_Theory.pdf - http://jasonhartline.com/MDnA/ + We encourage you to write the assignments using latex or word. Some helpful links: - Latex Template - http://agttau-2017.wdfiles.com/local--files/scribe-notes/agt2017-template.tex - Latex tutorial - https://tobi.oetiker.ch/lshort/lshort.pdf - great place to start latex - https://www.overleaf.com/ Good Luck, Course Staff |
| פורסם ב-20/10/2018, 19:05:37 Created on 20/10/2018, 19:05:37 Создано20/10/2018, 19:05:37 تم النشر ب-20/10/2018, 19:05:37 |