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 
AFTERCLASS 

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 56 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.15.6 of David Lippman’s textbook to learn about a few more cakecutting 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 writeup whether you answered correctly or whether you needed to make corrections/edits. C. Generalize the 3person “successive pairs”/”lone chooser” cakecutting algorithm that we discussed in class to 4 players. Then to n players. To write down the nplayer 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 3^{rd} edition of Dixit, not the 4^{th} edition. If you have the 4^{th} edition, you can check how the page numbers lineup by looking at the 3^{rd} edition copies on reserve in the library/in the back cabinet of the research lab NLH209. o Read pages 35 (which is an intro plus chapter 1.1), then also read section 1.2B, C, E (i.e. pages 711). o Skim chapter 2 (read according to your interestlevel) starting on page 17 o But actually read sections 2.3AE (pages 2733) closer since they are relevant and helpful here o Read 3.13.5.A (pp 4765), 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 writeup will be the true test of your own understanding. =) 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

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 3^{rd} edition of the DixitSkeath text. If you have the a different edition, you can check how the page numbers lineup by looking at the 3^{rd} 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 3^{rd} edition of the DixitSkeath text. If you have the a different edition, you can check how the page numbers lineup by looking at the 3^{rd} 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 
AFTERCLASS 

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 4^{th}
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 4^{th} 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 4^{th} 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 4^{th} 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 13 after Snape is removed instead of 03), 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 
AFTERCLASS 

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 coauthor 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 1213 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 nonatomic routing game (see RoughgardenTardos 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 (RoughgradenTardos 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 610), 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 nontrivial amount): construct an instance of the game on an undirected graph with POS > 4/3. 

Wed 
Meeting 9: 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 epsilonedges) 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 2931 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 
AFTERCLASS 

5 
Mon 
Meeting 9: PSA cont’d. Altruists, Egoists, Hooligans (see the paper) 
HW 9 (due Wed, Feb 28): Submit your midterm
project proposal (one per team)
by sharing it with me as a google doc. Be sure to grant me editing or
commenting permissions on the document. Attend at least one talk/tutorial/session of the sigecom winter meeting (see link above) on Wed, Feb 23. Then post to the moodle forum any thoughts you had about the session you attended. A short, informal paragraph will suffice. If someone already posted about the session you attended you can reply to their post with your response to their reflection, and some additional thoughts you had. 

Wed 
Meeting 10: Altruists, Egoists, Hooligans cont’d (see the paper) 
HW 10 (due Tues, Mar 1) · Submit your midterm project proposal (one per team) by sharing it with me as a google doc. Be sure to grant me editing or commenting permissions on the document. · Recall from class that in the paper we discussed, there are only two situations where altruists remain altruists from one round to the next when following the imitation rule. Prove it. (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 or your class notes for a review of what I’m talking about.] · We saw from these slides in class that to find SSS we can find the absorbing set with minimum stochastic potential. We saw on slide 28 that to find stochastic potential of an absorbing set that we built a complete directed graph where each vertex was an absorbing set, then labeled each edge (u,v) of the graph with the minimum number of “mistakes” (or epsilonedges) needed to have a path in the Markov process from a state in vertex u to a state in vertex v. We labeled two of these edges together. Slides 2931 give more edges with more labels without explanation. Pick 2 or 3 of these labeled edge weights and show the sequence of mistakes in order to verify that they are correct. Please explain at least one of the edges labeled with a 2. 

6 
Mon Feb 26 
Midterm project proposals due.
Meeting 11: Auction Mechanisms for welfare maximization
In the NRTV AGT text: half of chapter 9 (through 9.3). 
HW 11 (see related reading to the left), due Thursday: · Complete the proof we started in class that Vickrey’s 2^{nd} price auction (giving the item to the highest bidder and charging them the second highest price) is incentive compatible (aka “truthful”). · 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…) · Revise your midterm project proposals as needed. If your proposal has been approved you can begin working on your projects! 

7 
Wed 
Meeting 12: Combinatorial auctions and the Case of Single Minded Bidders (chapter 11 and 11.1 of agt)
Next time? Characterization of Incentive Compatibility for Singleparameter Settings (chapter 11.111.2 of agt) 
HW 12 (see related reading to the left, also review chapter 9 reading above), due Tuesday: 0. Work on your midterm projects. Also: 1. In class we learned about the singleminded bidders auction problem, a special case of combinatorial auctions. We mentioned that the problem of allocating items to maximize social welfare is NPhard. We considered two greedy algorithms, one greedy by and the other greedy by . Find (perhaps in 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. 2. 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? How bad can you make it? Extra credit questions from class (due whenever): · Show Greedy 1 (sorting by descending value) is a napproximation. 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?) 


Mon

Meeting 13. Midterm Projects: meet in Shain Library, “PC classroom,” downstairs 

Wed 
Meeting 14. Midterm Projects: meet in Shain Library, “PC classroom,” downstairs 
· Work on midterm projects for at least 5 to 10 hours this week. Begin preparing for your midterm project presentations. 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

March 1227 SPRING BREAK 
· 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 Tuesday, 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. 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

8 
Mon 
Meeting 15. Midterm Projects due at the start of class, midterm project presentations start. See presentation schedule. 
· AFTERCLASS · 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 continue 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

9 
Mon 
Meeting 17: Midterm project presentations conclude 
HW 13 (due Tues, April 12) 0. Show (i.e. prove/argue), as we discussed in class, that Vickrey’s second price auction mechanism is
incentive compatible by using the characterization of incentive compatibility
for singleparameter settings. (1. Monotonicity, 2. Critical value
payments.) 1.
Using
the payment setting algorithm we specified in class
for Greedy 3 to figure out each winner’s critical value, write down what the
analogous payment setting algorithm would be for Greedy 1. 


Wed Apr 3 
Meeting 18: Characterization of Incentive Compatibility for Singleparameter Settings (chapter 11.111.2 of agt). If time: profit maximization. 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

10 
Mon 
Meeting 19: Auction mechanisms for profit maximization: digital goods. (See chapter 13, mostly 13.4, of the agt text, or the corresponding original paper 
HW 14 (Due Thurs, April 14) 1. In class we defined the optimal omnicient fixed price profit, and discussed how to find it. We wrote down its formula as . Write some code/pseudocode to compute this value (without calling a “builtin” max function to do it for you). Have your code also return/compute the price that achieves this optimal fixed price profit. 2. Construct an input
instance for a digital goods auction with 3 bidders (where all the bids are
different – no ties) where the optimal fixed price OPT_F(v)
is… b. …the bottom bidder’s
bid. c. …a middle bidder’s bid. 


Wed 
Meeting 20: Profit maximization with digital goods, cont’d. (Proof that deterministic truthful auctions can’t compete with OPT_F2); A randomized auction that is 4competitive for the digital goods setting. 
HW 15 (Due Tues, April 19): · Complete the final project partnering survey here: https://forms.gle/5kb4bAbJY6GiRmum9 · In class we learned about an auction mechanism called Deterministic Optimal Price (DOP). We then saw an input instance that demonstrated that it only earned a small fraction of the optimal fixed price profit (OPT_F). [Recall that you wrote the alg for computing OPT_F for HW 14.] For the bad instance from class, the profit of DOP was only 1/10^{th} of OPT_F. Then, we learned about an impossibility theorem that tells us in fact, no deterministic mechanism can hope to have a profit guarantee better than even OPT_F/n. See if you can find a bad input instance that makes DOP only return a profit of OPT_F/n. (You can refer to the proof we started to write at the end of class for the theorem.) · One hint is that such bad input will echo the same idea of the one we already saw in class that earned 1/10^{th} the profit of OPT_F. The values are just made even more extreme. For further hints you can refer to the proof of the theorem that we began to write in class. (I have now posted some class notes in a moodle announcement too.) The full proof can be found in the original paper on the topic, or in section 13.4, of the agt text. · Extra credit 1: finish the proof we started writing in class of the impossibility theorem. If you can’t figure it out, you can again refer to the above readings, which contain the proof. You just have to show you understand the proof by convincingly explaining it. Extra credit 2: in class we saw a randomized mechanism (called the Random Sampling Optimal Price (RSOP) auction) that guarantees an expected profit of 1/4^{th} OPT_F2. Another way to say this is that the mechanism RSOP is “4competitive.” Jack asked in class whether it might yield a competitiveratio even better 4 if we split the bidders into 3 groups instead of 2 groups. (Excellent research question!) Read about the RSOP auction in the paper linked above to understand why it is 4competitive, and then try to answer Jack’s question. =) 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

11 
Mon 
Meeting 21: Cascading Behavior in Networks (Chapter 24 of AGT text) Slides used in class: Leskovec, Hartline/Immorlica 
HW16 (due on Thursday, April 21) · Work on your final project proposals (due as a shared Google Doc by Thurs night, but Friday sometime would be okay too.) Project teams will be posted by Wed morning. · At the end of class we looked at a line graph with 0 < q < 1/2 and saw that when the initial set of adopters S = {0}, S is not a “contagious set.” Find a set S 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 that we saw in class. 


Wed 
Meeting 22: Manipulation Resistant Reputation Systems (Chapter 27.5) 
HW 17 (due Tues ) · Determine the reputation ranking of all nodes in this graph, first using the PathRank algorithm and then the MaxFlow algorithm. Submitted via moodle before class as usual. Put finishing touches on your final project proposals according to my feedback on your shared google docs. 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

12 
Mon 
Meeting 23 : Reputation Systems, cont’d. Also: a simple, truthful, randomized constant pricing mechanism that gives a (log n)approximation to OPT (where OPT = full profit extraction = sum of all bidder valuations) 
Revise your final project proposals based on my feedback, and begin work on your final projects. Put in at least 25 hours of background research and/or design/coding by the end of the week. HW 18 (due Thurs, 4/28): Using the same graph as from HW17 above, show how Max Flow is not ranksybilproof 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 
Meeting 24: lab day for final projects (meet in Shain “PC classroom”) 
Continue work on your FINAL PROJECTS!! Put in at least another 5 hours on it. Presentations begin Thursday, May 5. 

WEEK 
DATE 
TOPIC 
AFTERCLASS 

13 
Mon 
Meeting 25: lab day for final projects (meet in Shain “PC classroom”) 
Work on your final projects. Presentations begin Thursday, May 5. 


Wed 
Final Project Presentations 
Finish 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 
AFTERCLASS 

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 18, unless you are a graduating senior. 


May 
Review Days and Final Exam Period 



All work must be submitted by noon on May 15 for most students, but by 5 pm on May 13 for graduating seniors. 








