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.
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?
Atomic congestion games
Read [Kearns et al.’01]
Network Games and recurrent neural networks
Classes 6-13. Mechanism design.
Read [Monderer and Tennenholtz’04, sections 1-4]
Facility location mechanisms
Implementation with money (VCG)
Read [Porter et al.’08]
Fault tolerant mechcanisms
Mechanism design in routing games:
Tolls, Bicriteria bound, biases
Possible additional topic: Cooperative games.
Read chapters from the book
HW2 grades are online!
|The graded papers were handed to the secretariat|
הרצאה ביום חמישי
|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
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.
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
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.
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).
|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.
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:|
Title: Prophet Inequalities for Independent Random Variables from an Unknown Distribution
Speaker: Paul Duetting, London School of Economics
Come at 12:15 for lunch.
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):
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).
|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.
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:
See you on Monday!
|Please make sure you are correctly listed in the Google doc:|
|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)
Course schedule (tentative)
Final project update
|The final project list has been updated:|
Deadline update: Please pick a topic by Monday Dec 3.
|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:
The final project will be 55% of the final course grade (the other 45% will be for the assignments).
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.
It is highly recommended for people who are interested in AGT to participate.
|Please submit hw1 to Ohad’s mailbox (cell 100) in the 5th floor.|
HW1 and Course Book
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.
HW1 mistake and deadline change
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.
|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)
|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.|
Welcome to Algorithmic Game Theory!
|+ Lecture Notes from Stanford course - https://theory.stanford.edu/~tim/notes.html|
+ Online books -
+ 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/