Course
Schedule
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 |
Tues
|
Overview of
algorithmic game theory (Braess’ paradox,
quantifying inefficiency of equilibria, mechanism design - auctions, cake
cutting) |
HW1 1.
Read entire
syllabus. Post any questions you have
about it to moodle or bring them to class on Thurs. 2.
Read 1.1 and 1.2 of Binmore (handout). 3.
Complete the
following exercises (using pen/pencil and paper) to be handed in at the start
of class on Thurs: o Create a congestion network (where the goal is minimize max latency, as we saw in class on slides 5-6)
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. o Design a truthful
auction for allocating two identical items to the bidders with the top two
valuations for an item.
Justify/explain how/why your auction mechanism is truthful (or if you
fail to find one, why the one you propose is not truthful). · What about for k identical items going to the top k bidders? |
|
|
|
Thurs |
Game theory
fundamentals (sequential games, extensive form, backwards induction,
“rollback” equilibrium) |
HW2 (due at the start
of class on Tuesday, Sept 3) o
Read intro and section
1.1 (pages 3-5), section 1.2B, C, E (pages 7-11) o
Skim chapter 2 (read
according to your interest-level) starting on page 17 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
Complete these
exercises from Chapter 3 (starting on page 80) to be handed in on
Monday: 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.
The sooner the better, but I will accept extra credit submissions late
too. You can and should discuss with
others, as extensively as you wish, but you have to ultimately write up the
explanation yourself and that write-up will be the true test of your own
understanding. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
2 |
Tues |
Game theory fundamentals (simultaneous games, normal form,
best response, Nash equilibria, dominant strategies) |
HW3 (double HW) due
Sept 5 o Read
all of chapter 4. (Well, 4.2B and 4.6 are
technically optional…) o Complete
exercises: U3, U4, U5, S5, S6, U7 o In
class I mentioned in passing that there are some normal-form games with “no
Nash Equilibrium in pure strategies.”
(See section 4.8 of the reading for more on what this means.) Can you devise such a game (other than the
Tennis Game from your text book)? Can
you devise a back story to go along with your game? What are the best response functions and NE in the
following game (given at the end of class):
$10 to split between two players. Each player asks for an amount no greater
than $10. If their 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). |
|
|
|
Thurs |
Game theory
fundamentals (mixed strategies and mixed NE) |
HW4
due Sep 110 o
Read…
o
Complete these
exercises…
o Chapter 8: exercises
U1, U2 |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
3 |
Tuesday
Sept 10 |
Game theory
fundamentals (repeated prisoner’s) |
HW5 ·
Read Chapter 11,
Sections 1 & 2 ·
Complete exercise
S3, which you started in class. (Check
your solution!) ·
Complete Chapter 11
exercises: U1, U2, U3, and U5.
|
|
|
|
Thurs |
Game theory
fundamentals (social choice) [Chapter 16 of
Dixit, or Chapter 9 of AGT text] |
HW6 o
Read Chapter 16
(all) o
Complete Chapter 16
exercises: U1, U2, U3, U4, U5 o
Show
how/why the Borda count algorithm and the Condorcet
criterion algorithm give the output they do on the “milk, beer, or wine”
example from this article that was passed out in class: http://www.siam.org/news/news.php?id=674.
o
Devise
your own voting algorithm, write it down, and show what it outputs on the
same “milk, beer, wine” example. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
4 |
Tues |
Auction
Mechanisms for welfare maximization In the NRTV text: half of chapter 9 (through
9.3), and the beginning of chapter 11 (through 11.2.1). |
HW
7 (see related reading to the left) ·
Suppose you are auctioning
k identical items to n bidders who each have a private value for receiving
one of the items. Assume n >
k. Each item will go to a different
bidder. Devise an incentive compatible
mechanism that allocates the k items to the k players who have the highest
valuation for receiving an item.
(Hint: start with k = 2, then k
= 3. Try to generalize Vickrey’s second price auction, in which k = 1.) Argue/prove
that your mechanism is incentive compatible. ·
In class we learned
about the combinatorial auction problem.
Devise a concrete example of a combinatorial auction (this should be
entirely fictional, so feel free to get creative). For each bidder, you will need to specify
her valuation for each bundle of items.
Then give the allocation of items to bidders that maximizes social
welfare (total valuation of all players) in your example. ·
In
class we also 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 is NP-hard. We mentioned two
greedy algorithms, one greedy by ·
Begin to brainstorm
ideas for midterm
project. |
|
|
Thurs |
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) |
Work
on proposals for midterm
project. HW 8 1.
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 single-parameter settings. 2.
In class we
mistakenly concluded that in the following example, under the Greedy1 mechanim, both players 1 and 2 should win and pay 299,
the bid of player 3. Explain why this
is incorrect based on what wrote should be the critical payment of each
winner (based on the definition of critical payment). Player 1: {1,2}, 301; Player 2: {3,4}, 300;
Player 3: {2,4}, 299. [Hint: Player 1
need actually not pay a thing!] 3.
The Greedy3
algorithm from class chose winners in order of decreasing valuation per
item. a.
Can you find an
input instance that demonstrates Greedy3 is suboptimal? b.
Is Greedy3
monotone? c.
What would the critical
payments be for each winner to ensure that Greedy3 is incentive compatible? Write
pseudocode for Greedy1 and Greedy3 that includes the procedure for
calculating critical payments for winners. |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
5 |
Tues |
Auction mechanisms
for profit maximization: digital goods.
(See chapter 13, mostly 13.4, of the agt
text, or the corresponding
original paper) |
HW 9 1.
Construct
an input instance (where all the bids are different – no ties) where the
optimal fixed price f*(b) is… a. the top bidder’s bid. b. the bottom bidder’s bid c. a middle bidder’s bid 2. Recall that in class we
computed the profit that the Deterministic Optimal Price (DOP) algorithm
achieves on the following input: n =
100, 10 bidders bid 10, and 90 bidders bid 1?
Please explain/show work for how we got our answer. 3. Using the optimal fixed-price profit (OPT_F) as our benchmark, what does
this make the “competitive ratio” (the ratio of the OPT_F profit to the
algorithm’s profit) for this instance?
4. Can you make this ratio worse (higher)? Finish
proposals for midterm
project to be submitted in hard copy in class on Tuesday. |
|
|
Thurs Sept
26 |
Midterm
project proposals due. Profit maximization
with digital goods, cont’d. (Proof that
deterministic truthful auctions can’t compete with OPT_F2.) |
HW 10 1.
In
case it helps, here is the original
paper on the stuff we’ve been learning about this week. 2.
Recall the proof from class that no
deterministic auction can achieve a profit guarantee of at least
OPT_F2/n. Give the instance indicated
by that proof that shows DOP can achieve profit no better than OPT_F2/n. (Show what DOP’s profit is on the instance,
and what OPT_F2 is.) 3.
Devise your own deterministic
truthful auction for the digital goods setting. (It’s okay if it’s a simple one.) And again, using the idea from the proof in
class today, give the bad instance that shows that your alg
cannot achieve profit better than OPT_F2/n.
Work on your midterm projects. |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
6 |
Tues |
FALL BREAK |
||
|
|
Thurs |
Example of a
randomized auction that is 4-competitive for the digital goods setting. Limited supply (aka
“knapsack auctions”). Up to Theorem 4.1
of this
paper |
HW 11 Consider the following instance of a knapsack
auction: C = 100, d = {52, 60, 40, 30,
20, 10, 5, 3, 25, 15}, v = {$1000, $200, $80, $10, $5, $6, $5, $7, $10, $20}.
1. Run the AK algorithm on this
input. Show all work. E.g., what is N’, H, l, etc. How much profit is earned? 2. Consider a mechanism that
charges each bidder exactly their bid (as listed in v above). Would such a pricing rule be monotone? Why or why not? 3. Draw a picture of a valid
monotone pricing function for the bidders in the set N’. The picture should clearly show how much
each bidder will be charged for their demand amount. Does your function give the optimal
monotone pricing profit for N’?
Justify your answer. Work on midterm projects for at least
5 to 10 hours. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
7 |
Tues |
HW12 (a) Trace through the HybridAlg on the input instance of HW11. (Recall that HybridAlg
was: 1. Run AK, 2. Run OPT(H), 3. Charge prices that are max(price
from 1, price from 2) for each demand size.
Details in your class notes and/or the Knapsack Auctions paper linked
above.) (b) Verify that in this particular
instance it indeed earns a profit of at least OPT/3-h (which we proved it always
would). Note this requires you to also
reason about the value of OPT, which is the optimal monotone pricing profit
on the instance. [You can probably do
this successfully and rigorously even without having to pinpoint exactly what
OPT is.] Bonus: conclusively answer
Patrick’s question from class… “can price from step 2 of HybridAlg
ever be lower than the corresponding price from step 1?” If yes, give an example. If no, give a proof. Work on midterm projects |
||
|
|
Thurs |
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). |
More Bonus:
is Patrick’s version of a greedy-density algorithm still
truthful? Explain/justify. Even More Bonus:
is HybridAlg truthful? Explain/justify. Finish midterm projects
|
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
8 |
Tues |
Midterm
Projects due at the start of class, midterm project presentations start. |
HW 13 (due Tuesday March 31) ·
In
class we saw that, in the digital goods setting, RandAlg1 [choosing a bid
value uniformly at random from all n of the bids and using that as the price]
gave an n-approximation (in expectation) to OPT-h (where OPT is full profit
extraction, i.e. sum of all bids/valuations, and h is the highest bid
value). Show that in fact, even the
basic deterministic second-price Vickrey auction
(selling one item to the first bidder at a price equal to the second highest
bid), gives an n-approximation to OPT-h.
I.e., show that the profit derived from the second price Vickrey auction is guaranteed to be at least
(OPT-h)/n. ·
We
also saw that RandAlg2 [choosing a bid value from the bidders in the set
{2,4,8,16,…,n} instead] gave a 2logn-approximation
(in expectation) to OPT-h. Here we
assumed that n was a power of 2. We
did some hand-waving toward the end of this argument. Write the complete argument down. The easiest way to do this is probably to
show a little algebra. ·
Bonus
1: Show that RandAlg2 gives a
2logn-approximation to OPT-h (in expectation) regardless of the number of
bidders. (Remove the assumption that n
is a power of 2.) ·
Bonus
2: Answer Jules’ in-class question
about whether RandAlg1 is really truthful.
You will want to revisit the definitions of truthfulness of randomized
mechanisms for this. Prepare your midterm project presentations. |
|
|
|
Thurs Oct
17 |
Midterm
project presentations |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
9 |
Tues |
Midterm
project presentations |
HW
14 (due Tuesday, April 9) Recall
that computing optimal monotone pricing profit for a Knapsack Auction is
NP-Hard. Computing the optimal constant price (or fixed price)
profit, however, is not. (Note this is different from computing
optimal constant price in the digital goods setting, because there you have
unlimited supply, while in a Knapsack Auction, anyone who can afford the
price you pick must fit within the knapsack, otherwise it is an invalid price.)
Devise an algorithm to compute the optimal (valid) constant
price. To be clear: your inputs are the capacity of the
resource you are auctioning, C, each player’s valuation, and each player’s
demand size. Your algorithm should output the valid fixed
price (the same price for all winners, regardless of their demand) that
maximizes your profit. (Note, I’m not
asking for a truthful auction mechanism here, just a way to compute OPT_F.) |
|
|
|
Thurs Oct
24 |
Midterm
project presentation |
||
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
10 |
Tues |
Quantifying Inefficiency of Equilibria: Non-atomic
routing game (see Roughgarden-Tardos paper),
Shapley network design game (chp 17 of agt text) |
HW15: Recall from class the Shapley Network Design
Game. ·
We
drew an example instance of the
game on the board with three players.
As we did in class, find the price of anarchy = (cost of worst NE)/(cost of OPT) in that instance of the game. As always, explain/justify your
answer! ·
Then
create an instance of the game where price of anarchy is worse. How bad can you make it? For this you should use a different
network, the simpler the better.
(Hint: the network structure of Pigou’s example works, and players
don’t need to have different s’s and t’s.)
Explain how you determined the price of anarchy in your example. |
|
|
|
Thurs |
More
POA stuff: network design cont’d, load
balancing game |
HW 16 (due Tuesday, April 14): ·
Redo
HW 14 based on clarifications given in class.
In addition to a high-level description of the algorithm, please also
submit pseudocode for it! ·
In
class we learned that the Shapley Network Design Game on directed graphs has a POS of H_n =
ln(n), where ln stands for the natural log.
(This means there are no instances where POS is worse than ln(k), and,
as we saw in class, there exists an instance where it is exactly ln k.) We then learned that POS of undirected graphs 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.] See
if you can construct the instance and explain how/why it has POS = 4/3. · Read final
project
page. Email me if you need a partner. Start brainstorming and sending
me final project proposals. · Write down a few possible ideas
(one or two sentences each) for your final project. (Don’t worry, this is just so you will
start brainstorming, nothing you write will be binding.) Challenge question (due by the last day of finals, worth at least a letter grade increase
to your final average, and possibly a research publication): construct an instance of the game on an
undirected graph with POS >= 2. Extra credit question (also due by the last day of finals, worth some smaller, but
non-trivial amount): construct an
instance of the game on an undirected graph with POS > 4/3. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
11 |
Tues |
Load Balancing
games and some evolutionary game theory (stochastic stability and price of
stochastic anarchy). See slides posted
on Moodle. |
HW17 Recall from class the game of load balancing on unrelated machines. We saw that POA can be unbounded in the
worst case. Devise an instance of the
game where POA is bounded, but
worse than 1. (For example, some
constant value greater than 1 will do.)
As always, you must explain
how to find the POA in the instance you devise. Work on final project proposals (due Thurs night,
April 16, via Google Docs, at 11:59 pm). |
|
|
|
Thurs |
Altruists, Egoists,
Hooligans (see the paper,
or click this link for a “local” copy) |
HW18 Recall from class that in the paper we discussed,
there are only two situations where altruists remain altruists from one round
to the next. Prove it. (One way to do this is to show that in all
other situations, altruists in one round become egoists in the next.) [See page 161 of paper or your class notes
for a review of what I’m talking about.] http://ideas.repec.org/a/aea/aecrev/v88y1998i1p157-79.html Complete final project proposals (due via Google
Docs at 11:59 pm). |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
12 |
Tues |
Cascading Behavior in Networks (Chapter 24 of AGT
text) |
Be sure you have
received “official final approval” on your final project proposals from me via email. Begin work on final projects. Put in a solid 2-5 hours of background
research or coding or both. |
|
|
|
Thurs |
All-College Symposium: No class |
Continue work on your
FINAL PROJECTS!! Due one week from Tuesday. |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
13 |
Tues |
Cascading Behavior in Networks
(Chp 24 cont’d) |
HW 19 Explain/argue why the contagion threshold is not
above q=˝ on the line graph that we saw in class. Work
on your final projects |
|
|
|
Thurs |
Manipulation Resistant Reputation Systems (Chapter 27.5) |
Finish
your final projects and prepare your
presentations |
|
|
WEEK |
DATE |
TOPIC |
AFTER-CLASS |
|
|
14 |
Tues |
Final Project Presentations |
HW 20 (Optional, for bonus) Determine the reputation ranking of all nodes in this graph,
first using the PathRank algorithm and then the MaxFlow algorithm. |
|
|
|
Thurs |
THANKSGIVING BREAK |
||
|
WEEK |
Tues |
Final Project Presentations |
|
|
|
|
Thurs |
Final Project Presentations |
||
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
