As with everything else, the schedule listed below is subject to change. Check back often for updates.
Note: you are expected to participate by visibly staying engaged in class, asking questions, and contributing to class discussion, as well as by posting your questions/comments to the forums on the class moodle page.
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
1 |
Mon
|
Meeting 1: Overview of algorithmic game theory (Braess’ paradox, quantifying inefficiency of equilibria, cake cutting) |
HW1 (due with exercise submission via moodle on Wed, Jan 24 by 10:00 am): 1. Read entire syllabus. Post any questions you have about it to moodle and/or bring them to class on Thurs. 2. Read 1.1 and 1.2 of this Binmore handout. 3. Reach out to at least one other person in class to see if they want to meet to work on the HW together. You can work with as many people on HW as you want. Since HW will be due each class, arrange to meet once between Mon and Wed and another time between Wed and Monday. If you don’t know who you want to work on HW with, email me and I will connect you with another person who has also emailed me for the same reason. 4. Complete the following exercises (using pen/pencil and paper) to be uploaded (as an image file or pdf file) to the HW 1 moodle submission link by 10:00 am on Wed: A. Review pages 5-6 of the slides from our first class meeting (as well as the corresponding pear deck activity). Recall that the goal here was to minimize max latency. Modify/change this congestion network, or find/draw/create a different one, where the POA is worse (greater) than 4/3. See how bad you can make the POA! (Hint: POA doesn’t necessarily increase with the size/complexity of the network. It’s always best to try to keep things small and simple!) Be sure you fully explain/show/describe what is the optimal solution vs the worst Nash equilibrium. B. Read sections 5.1-5.6 of David Lippman’s textbook to learn about a few more cake-cutting algs. Do the “try now” exercises in each section and verify your answers (after you have written them down in your HW first). Note down in your HW write-up whether you answered correctly or whether you needed to make corrections/edits. C. Generalize the 3-person “successive pairs”/”lone chooser” cake-cutting algorithm that we discussed in class to 4 players. Then to n players. To write down the n-player version, you may wish to think recursively. |
|
|
|
Wed |
Meeting 2: Game theory fundamentals (sequential games, extensive form, backwards induction, “rollback” equilibrium) |
HW2 (due by 10:00 am on Mon, Jan 29) o Note that all page numbers below are for the 3rd edition of Dixit, not the 4th edition. If you have the 4th edition, you can check how the page numbers line-up by looking at the 3rd edition copies on reserve in the library/in the back cabinet of the research lab NLH209. o Read pages 3-5 (which is an intro plus chapter 1.1), then also read section 1.2B, C, E (i.e. pages 7-11). o Skim chapter 2 (read according to your interest-level) starting on page 17 o But actually read sections 2.3A-E (pages 27-33) closer since they are relevant and helpful here o Read 3.1-3.5.A (pp 47-65), skim 3.5.B,C, and the rest of 3 is nice but optional... o Reach out to at least one other person in class to see if they want to meet to work on the HW together. You can work with as many people on HW as you want. Since HW will be due each class, arrange to meet once between Mon and Wed and another time between Wed and Monday. If you don’t know who you want to work on HW with, email me and I will connect you with another person who has also emailed me for the same reason. o Complete these exercises from Chapter 3 (starting on page 80): S1, U2 (jumping to page 85 here), U3, U4, and U8 o To earn extra credit for the pirate problem, you must write up your solution with a complete and clear explanation and submit it in hard copy. I will accept extra credit submissions at any time during the semester. You can and should discuss all HW including extra credit with others, as extensively as you wish, but you have to ultimately write up the explanation yourself and the clarity of that write-up will be the true test of your own understanding. =) |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
2 |
Mon |
Meeting 3: Game theory fundamentals (simultaneous games, normal form, best response, Nash equilibria, dominant strategies) |
HW3 (due Wed, Jan 31): · Note that all page numbers below are for the 3rd edition of the Dixit-Skeath text. If you have the a different edition, you can check how the page numbers line-up by looking at the 3rd edition copies on reserve in the library, or in the back cabinet of the research lab NLH209, or the copy in the back corner cabinet of NLH214. Please leave these copies in the labs so that all students can share them. · Read all of chapter 4. (Well, 4.2B and 4.6 are technically optional…) · Complete chapter 4 exercises (do these in collaboration with another classmate or a HW group if possible): S5, S6, U3, U4, U5, U7 · Also complete this exercise: o Consider the following game. We have $10 to split between two players. Each player asks for an amount of money between $1 and $10. If their requested amounts sum to $10 or less, they each get what they asked for. If their amounts sum to more than $10, the person who asked for less gets what they asked for, the other person gets the rest (except if they tie, then they each get $5). o Do a best response analysis of the game to find the NE. Hint: draw a big 10 x 10 payoff matrix for the game and analyze it like any other game’s payoff matrix. |
|
|
|
Wed |
Meeting 4: Game theory fundamentals (mixed strategies and mixed NE) |
HW4 (due Mon, Feb 5) · As always, the page numbers below are for the 3rd edition of the Dixit-Skeath text. If you have the a different edition, you can check how the page numbers line-up by looking at the 3rd edition copies on reserve in the library, or in the back cabinet of the research lab NLH209, or the copy in the back corner cabinet of NLH214. Please leave these copies in the labs so that all students can share them. o Read…
o Complete these exercises… · Find the mixed NE when the matching pennies game (from class) is modified by replacing all payoffs of -1 with 0.
· Chapter 8: exercises U1, U2 |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
3 |
Mon |
Meeting 5: Game theory fundamentals (repeated prisoner’s) |
HW5 (due Wed, Feb 7) · Read the sample solutions for HW4 and bring any questions to class or post them to the moode forum! · Read Chapter 11, Sections 1 & 2. (This is Chapter 10 in the 4th edition of the text.) · Complete exercise S3. (Check your solution! Solved exercises have published solutions on the website specified in the text; I have also posted them to the moodle page.) · Complete Chapter 11 exercises: U1, U2, U3, and U5. (Same numbering but in Chapter 10 for the 4th edition.) |
|
|
|
Wed |
Meeting 6: Game theory fundamentals (social choice) [Chapter 16 of Dixit, and/or Chapter 9 of AGT text] |
HW6 (due Monday, Feb 12) o Read Chapter 16 (all) as well as this nice online piece. (This is chp 15 in the 4th edition.) o Also read https://archive.siam.org/news/news.php?id=674 o Complete Chapter 16 exercises: U1, U2, U3, U4, U5. (This is chp 15 in the 4th edition.) o Submit your work for the Harry Potter example from our class notes that illustrates that Borda Count does not satisfy the property of Independence of Irrelevant Alternatives (IIA). Show the social ranking from executing Borda Count on all 4 candidates, then remove Snape from the set of candidates, updating each voters ranking accordingly (you can use ranking points from 1-3 after Snape is removed instead of 0-3), and then show the new social ranking of the candidates. o Finally do at least one (or both) of the following: 1. Find a video or article that you like about Arrow’s Impossibility Theorem, or Voting Theory more generally, and post it to the class forum with a sentence or two about why people should read/watch it. OR 2. Watch a video or article that another student has already posted and reply to their post with your own opinion/reflection on what they posted. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
4 |
Mon |
Meeting 7: Metric Distortion in Voting |
HW 7 (due Wed Feb 14) · Work to answer this pressing (yet simple?) research question: Is there a set of voters and candidates that can be placed on the real number line (aka a “one dimensional metric space”) in a way that the winning candidate under the STV voting rule has “social cost” more than 3 times worse than the optimal candidate? Recall that the social cost of a candidate is the total distance of all voters to the candidate, and that the optimal candidate is the one with minimum social cost. The ratio of the social cost of the winning candidate to the optimal candidate is called its distortion. If you can find an example instance where the winning candidate has distortion worse than 3, then you will be added as a co-author on our paper. A final average grade bump of some form is also likely for those who can find such an example. · In case you are interested, the slides from class of the summer research students are posted to moodle. I can also post the video of their presentation as well once I get their permission to. · Also here are links to some relevant papers if you are interested o Like the one that shows STV has a distortion of at most 15 (on page 12-13 or so, Theorem 3.1) o And another that shows STV has logarithmic distortion in a general metric space (when not confined a 1D line metric, see Theorem 19 on page 45). |
|
|
Wed |
Meeting 8: Quantifying Inefficiency of Equilibria (price of anarchy and price of stability): POA in the non-atomic routing game (see Roughgarden-Tardos paper), and POS in the Shapley network design game (also see chp 17 of agt text) |
HW 8 (due Mon, Feb 19): Read the Forward (page xiii) of the agt text. Scan through the papers posted to the left (Roughgraden-Tardos and Anshelevich et al). Recall from class the Network Design Game with Fair Cost sharing. (See class handouts.) · In class we learned that there are instances of the Shapley Network Design Game on directed graphs with POS of H_n = 1+1/2+1/3+…+1/n =~ ln(n), where H_n is known as the “harmonic number,” ln stands for the natural log, and n is the number of players. · It turns out that the POS for the game on any directed graph is at most ln(n)! This means there are no instances of the game where POS is ever worse than ln(n), and, as we saw in class (see slides 6--10), there exists an instance where it is exactly ln n. But this is fact is only true for directed graphs. The POS of undirected graphs in the Network Design Game is still an open question. There is a simple, small instance of the game on an undirected graph where POS = 4/3. [Hint, you can find such an instance with just two nodes and three edges and two players.] See if you can construct the instance and explain how/why it has POS = 4/3. · In class we also learned (see slides) that the Network Design Game on directed graphs can sometimes have a price of anarchy (POA) of n. Recall that the example we saw with n players on two parallel links has its worst NE with cost n times worse than the optimal solution (worst NE cost n while the optimal solution only cost 1). Do you think POA could sometimes be even worse than n for some inputs? Why or why not? |
||
|
5 |
Mon |
Meeting 9: Load Balancing games and some evolutionary game theory (stochastic stability and price of stochastic anarchy). See slides posted on Moodle. |
HW 9 (due Wed, Feb 21): 1. Complete midterm project partnering form. 2. Begin to brainstorm ideas for your midterm project. If you have already decided on a partner, you can/should brainstorm a bit together. 3. Recall from class the game of load balancing on unrelated machines. (See class handouts.) · We stopped on this slide of the handouts in class… we wrote down the probability of proceeding from the circled state in the Markov Process to the two possible next states drawn below it (using imitation dynamics with a sample size of 3 and memory of 4). Review and explain how we got the probability of proceeding to each of the two successive states shown from the circled state. How would the probabilities change if the sample size was 2 instead of 3? Explain/justify your answers. Challenge bonus question (due by the end of the semester, worth an automatic A in the class, and possibly a research publication): construct an instance of the Network Design game on an undirected graph with POS > 348/155 ~= 2.245. (Here is the paper where they found an instance with POS = 348/155 if you are interested in checking it out!) Extra credit question (also due by the end of the semester, worth some smaller, but non-trivial amount): construct an instance of the game on an undirected graph with POS > 4/3. |
|
|
Wed |
Meeting 10: PSA cont’d. Altruists, Egoists, Hooligans (see the paper) |
HW 10 (due Monday, Feb 26): · Recall from class that in the paper we discussed, we worked through an example on the board where an Egoist surrounded by two altruists will stay an egoist in the next round, and its two altruist neighbors will flip to Egoist. In fact there are only two local neighborhood configurations where an altruist will remain an altruist from one round to the next. Can you find them? Explain why in each situation an the altruist remains an altruist. Also try to explain why these are the only two scenarios where altruism. (One way to do this is to show/explain how/why that in all other situations, altruists in one round become egoists in the next.) [See page 161 of the paper I handed out, or your class notes, for hints.] · We saw from these slides in class that to find a Stochastically Stable State we can find the absorbing set of the Markov Process with minimum stochastic potential. We saw on slide 28 that to find stochastic potential of an absorbing set we can build a complete directed graph where each vertex is an absorbing set, then label each edge (u,v) of the graph with the minimum number of “mistakes” (or epsilon-edges) in any path in the Markov process from a state in vertex u to a state in vertex v. We labeled two of these edges together on slide 28. Slides 29-31 give labels for some other edges, but without explanation. Pick 2 or 3 of these labeled edge weights and show/explain the sequence of mistakes in order to verify that they are correct. Please explain at least one of the edges labeled with a 2. |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
6 |
Mon |
Meeting 11: PSA cont’d. Altruists, Egoists, Hooligans (see the paper) |
HW 11 (due Wed, Feb 28): Submit your midterm project proposal (one per team, see last week’s moodle announcement for your assigned partners) by sharing it with me as a google doc. Be sure to grant me commenting or editing permissions on the document. |
|
|
Wed |
Midterm project proposals due. Work on midterm projects with partners |
· Revise your midterm project proposals as needed and re-share them with me for further review. · Meet with project partners to work on your projects! Get in those hours on it now, especially if you don’t plan to work over the break. |
||
|
|
|
|
||
|
Work on your midterm projects with your partners for 5 to 10 hours this week. |
||||
|
7 |
Mon
|
Meeting 13. Midterm Projects: meet NLH214 |
||
|
Wed |
Meeting 14. Midterm Projects: meet in NLH214 |
Work on midterm projects with your partners. Begin preparing for your midterm project presentations. |
||
|
March 12-27 SPRING BREAK |
||||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
8 |
Mon |
Meeting 15. Midterm Projects: meet in NLH214 |
For Wed, Mar 27: · Finish midterm projects. Put all your files into a google drive folder and share the folder with me. (While an initial submission with the main body of work complete is required via google drive by Wednesday, Mar 27, you can continue to tweak and make updates to your shared submission folder if you wish during the presentation period.) · Prepare your midterm project presentations. See presentation schedule.
For Mon, April 1: · Touch up your midterm projects if needed, and · If you haven’t presented yet, finalize your project presentations. · See presentation schedule. |
|
|
|
Wed Mar 27 |
Meeting 16: Midterm project presentations commence back in NLH304 |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
9 |
Mon |
Meeting 17: Midterm project presentations continue |
· Touch up your midterm projects if needed, and make sure all required components are present. See the sample rubric that is posted from the project page for details and also review the project page requirements.
|
|
|
|
Wed Apr 3 |
Meeting 17: Midterm project presentations continue |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
10 |
Mon |
Meeting 19: Auction Mechanisms for welfare maximization In the NRTV AGT text: half of chapter 9 (through 9.3). |
HW 12 (see related reading to the left), due Wednesday (April 10): · Recall that we learned in class about how Vickrey’s 2nd price auction (giving the item to the highest bidder and charging them the second highest price) is incentive compatible (aka “truthful”). See reading if you want a review and more details (in the NRTV AGT text: half of chapter 9 (through 9.3).) · Write down an argument for how you know this auction mechanism is truthful. Refer to the claim we wrote down in class. You can follow this outline to make the explanation/argument you write completely thorough if you wish! · Now suppose you are auctioning 2 identical items to n bidders who each have a private value for receiving one of the items. Assume n > 2. Each item will go to a different bidder. Devise an incentive compatible mechanism that allocates the 2 items to the 2 players who have the highest valuation for receiving an item. (You can see the reading for hints on this…) |
|
|
|
Wed |
Meeting 20: Combinatorial
auctions and the Case of Single Minded Bidders
(chapter 11 and 11.1 of agt) Characterization of Incentive Compatibility for Single-parameter Settings (chapter 11.1-11.2 of agt). |
HW 13 (see related reading
to the left), due Mon April 15: · Complete
the final project partnering
survey here: https://forms.gle/2WfKqw9iZGnGQiL18 · First, a review
question: In class we learned about the Single-minded Bidders auction
problem, a special case of combinatorial auctions. We mentioned that
the problem of allocating items to maximize “social welfare” (i.e., the total
valuation of the winners) is NP-hard. We considered a few greedy
approximation algorithms, the first greedy by v*_i and
the second greedy by |S*_i|. Find (perhaps
from your class notes) and write down clearly an “extreme” example instance
for each algorithm that “defeats” the algorithm (i.e., instances that make
the alg fail badly at the goal of maximizing social
welfare). In each case, show/give the ratio of the welfare of opt to
the welfare of the alg and see how high you can
make this ratio. · The Greedy3 algorithm from class chose winners in order of descending valuation per item. Can you find an input instance that demonstrates Greedy3 is suboptimal? · As we discussed in class, an auction mechanism is incentive compatible (in a single-parameter settings like single-minded bidders or single-item auctions) if it satisfies two criteria: 1. Monotonicity, and 2. Critical value payments. Recall that the critical value if a winning bidder is the bid-value below which they would become a loser instead of a winner. This is why in a single-time auction, Vickrey says to charge the highest bidder the second highest bid value. a. Under
the Greedy 1 mechanism for single-minded bidders, who will be the winners in
the following instance and what should their payments be to ensure
truthfulness? Player 1: (S*_1={A,B},v*_1=301);
Player 2: (S*_2={C,D},v*_2=300); Player 3: (S*_3={B},
v*_3=299). [Hint: winners don’t necessarily need positive
payments…] b. What
if now we added a second item to the set of Player 3 to make it {B,D} but left everything else the same? Extra credit questions from class (due whenever): · Show Greedy 1 (sorting by descending value) is a n-approximation. That is, prove/argue that it always earns at least 1/n th of the optimal social welfare in any instance. · For
the algorithm Greedy 2, which sorts bidders by ascending bundle size, we
discussed an instance that gives a ratio of v_max/v_min, where v_max is the
highest bidder’s valuation and v_min is the lowest
bidder’s value. (In theory this is an unboundedly high/bad
ratio.) Can you prove that Greedy 2 always guarantees a ratio no worse
than v_max/v_min?
(Or if not, can you find an instance to make the ratio even worse?) |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
11 |
Mon |
Meeting 21: Cascading Behavior in Networks (Chapter 24 of AGT text) Slides used in class:
Leskovec, Hartline/Immorlica. (Slides are also posted to moodle.) |
HW 14 (Due Wed, April 17) · Start brainstorming ideas for your final project. Project teams will be posted by Wed. · Summary of class: recall
that we defined a “contagious set” to be an initial subset of nodes in a
graphical game that, when endowed with the “new behavior,” causes all nodes
in the graph to eventually adopt the new behavior (and stay that way). Remember that we used q to refer to the
payoff to a node/player for an interaction with the old behavior, and that q
also turned out to be exactly the fraction of neighbors needed to take on the
new behavior before a node prefers (i.e. earns
higher payoff for) switching to the new behavior from the old one. The “contagion threshold” was then defined
as the max-possible q
for which there exists a finite contagious set. ·
Consider
a path graph (imagine it drawn in a
straight line) which
goes on infinitely in either direction, with node names: …-3, -2,-1, 0, 1, 2, 3… (similar in layout to a number line with
integer values labeled and nodes at those integer locations). Suppose q < 1/2 and the initial set of
adopters S = {0}. Is S a “contagious
set”? Why or why not? o If not, find a set S of initial adopters that is a contagious set for that line graph. · Bonus (can be submitted whenever, as with all other bonuses): We also learned that there is a theorem that tells us the contagion threshold is never more than q=1/2 for any graph. Explain/argue why the contagion threshold is not above q=½ on the line graph. |
|
|
|
Wed |
Meeting 22: Reputation
Functions and Transitive Trust (Chapter 27.5) |
HW15 (due on Mon, April 22) ·
Draft up and submit to me
your final project
proposals (submitted as a
shared Google Doc with permission granted to me to make suggestions). · Determine the reputation ranking of all nodes in this graph, first using the PathRank algorithm and then the MaxFlow algorithm. For each one, list the nodes of the graph in rank order from most trusted to least trusted. Submitted via moodle before class as usual. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
12 |
Mon |
Meeting 23: Manipulation
Resistant Reputation Functions |
Revise
your final project proposals based on my feedback, and begin work on your final projects. Try to put in at
least 2-5 hours of background research and/or design/coding for your final
projects by the end of the week. HW 16 (due Wed, 4/24): Using the same graph as from HW15 above, show how Max Flow is not rank-sybilproof by finding a node that can use a Sybil attack to improve its ranking. (Start by reviewing/giving the current ranking of each node in the graph under the MaxFlow reputation function, then show how the ranking changes after the Sybil attack.) |
|
|
|
Wed |
Sybilproofness |
Work on your final projects! Let me know if you still have any questions about your proposals/plans for the project. Make a project management plan and timeline with checkpoints and deadlines for getting various pieces of the project done. Remember that presentations begin May 6, so plan to get some piece your projects done by then to be able to give us an idea of what your project will ultimately be/do! |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
13 |
Mon |
Meeting 24: lab day for final projects (meet in NLH214) |
Work on your final projects. Presentations
begin Monday, May 6. |
|
|
|
Wed |
Meeting 25: lab day for final projects (meet in NLH214) |
Work on your final projects and prepare your presentations If you did not ask a question in class during today’s presentations, post one to moodle. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
14 |
Mon |
Final Project Presentations |
If you did not ask a question in class during today’s presentations, post one to moodle. |
|
|
Wed |
Final Project Presentations |
Wrap up all final projects and code with documentation. Make sure all folders are shared with me via google drive. Final deadline for everything is noon on May 15, unless you are a graduating senior. |
||
|
|
May |
Review Days and Final Exam Period |
||
|
|
|
All work must be submitted by May 15 for most students, but by May 13 for graduating seniors!! |
||
|
|
|
|
||
|
|
|
|
||