The last Homework is now posted... As usual, ask your questions here.
This one has half about auctions (GSP) and half about MapReduce (which you'll learn in today's lecture).
This Homework and your project plan are the last things of the term. Both are due at the end of finals, but there is no reason why you can't turn them in earlier if you don't want to hang around until then!
Subscribe to:
Post Comments (Atom)
Q3 (a) When PoA's defined in terms of social welfare, don't we have PoA <= 1?
ReplyDeleteI'm sorry for the confusion. This is purely a matter of convention that should have been clarified (in class or in the homework). So far, we have encountered load balancing games and routing games, where the social measure was some sort of 'cost'. Therefore, the social cost of the worst Nash equilibrium was always at least the optimal social cost. This ensured that the price of anarchy, which was defined as the ratio of the social cost of the worst Nash equilibrium to that of the optimal, is always >= 1. This is a highly accepted convention for PoA - that it is always >= 1.
ReplyDeleteNow, when the social measure is welfare (as in the case of ad auctions), to preserve this convention, the PoA definition is usually modified to be the ratio of the optimal social welfare to the social welfare of the worst Nash equilibrium.
I hope this clarifies your doubt.
Yup that's what I presumed too. Thanks Raga!
ReplyDeleteFor question 3, it says that advertiser pi(k) pays b_pi(k + 1) per click. Since pi(n + 1) doesn't exist, how much would advertiser pi(n) pay per click? Do we assume that b_pi(n + 1) is 0?
ReplyDeleteThanks!
In practice, the advertiser who bids the lowest usually pays some constant reserve price (think of it as the minimum bid required to enter the auction). For this homework problem, you can assume what you suggested - the lowest bidding advertiser gets the last slot for free.
ReplyDeleteHi everyone, to follow up on a previous comment, I just noticed that in the homework, for problem 3, the price of anarchy definition has to be inverted, that is, the price of anarchy is the ratio of the optimal social welfare to the worst Nash social welfare. I've corrected this and the change should be reflected in the homework that is online soon.
ReplyDeleteFor the MapReduce question 2 (Highschool days), should the output include both the scores and the student names?
ReplyDeleteNo. We are not interested in student names. Only scores are enough.
ReplyDeleteFor problem 3, recall the definition of price of anarchy of a game, versus price of anarchy of a class of games. For a class of games, the price of anarchy is the max/sup of the prices of anarchy of each individual game in that class. Therefore, to show that the PPoA when n=2 is exactly 1.25, you need to show that no game in this class has a PPoA > 1.25, and also show that there is a game in this class with PPoA = 1.25.
ReplyDeleteIn problem 3 (iv), i'm not sure what "pair of bidders (i,j) that satisfy i<j" means. Does "i<j" means player i has a higher value than j?
ReplyDeleteAlso \pi is a mapping from position k to player index i, hence it's a bit weird to see it applied as \pi(i): Does \pi(i) mean more intuitively the position of the ith player, or the index of the player with the i-th highest bid according to the definition?
I'm sorry, that is a typo. It should have been "for each pair of slots (i,j) that satisfy i<j". This should clarify the other confusion as well - \pi is always a mapping from slots/positions to players. No overloading here.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteClarifications regarding PageRank question:
ReplyDelete1. Minor typo:
"while(stoppingCriterion(r, rUpdated)"
should be
"while(NOT stoppingCriterion(r, rUpdated))"
2. rUpdated comes out as a list of (node number, current pagerank). Just treat it as a list of (current pagerank). Interpret distUpdated similarly in 'Gauge The Distance'.