India Theory Day
Satya Lokam, Ravi Kannan and others at MSR hosted the India Theory Day at Bangalore. It is a little spooky to fly several hours, drive to some office, see Kunal Talwar, George Varghese, Deeparnab Chakrabarty, Amit Deshpande, and others from a more immediate context in my working mind.
Eva Tardos spoke about the Generalized Second Price (GSP) auction. She reviewed by now well-known analyses of GSP that PoS=1 and PoA is like 1.6 or 1.2 depending. Her talk focused on the role of uncertainty. In particular, assuming separability, bidder i in position j will get expected value \alpha_i \beta_j v_i where \alpha_i depends on bidder, \beta_j on the position. While bidder i knows value v_i, they dont know the other parameters, and even if they know the distribution of these parameters, they dont know the instantiation of the click probability in any particular auction. In presence of this uncertainty, GSP does not have efficient Nash equilibrium, and the result was that PoA is bounded by like 2.93. The O(1) PoA result is easy to motivate by considering the shading strategy of letting bid of i be v_i/2 (the best bound needs a more detailed strategy). Likewise, this strategy also has direct no-regret learning interpretation, and similar results follow for revenue as well under MHR assumption like Myerson. This research is much-needed, GSP is widely used and it is remarkable how little we know about it.
Other speakers: Mike Saks spoke about his very nice results on finding LIS in sampling and streaming models; Amit Kumar gave a near encyclopedic discussion of approximate clustering; Alas, I missed Nikhil Bansal's talk on randomized rounding; Nisheeth Vishnoi gave a short, rapid talk on closest vector problems with preprocessing, his brain seemingly whirring even as he stated complicated results.
On the earlier day, I gave a general introductory talk on ad auctions and met several researchers from other areas (Venkat: talked about difficulties of localizing even with compass and accelerometer, Kumaran: translating Indian languages; Sriram: language verification). Over dinner, we debated what was the great intellectutal work of 20th century: Einstein's, Turing's or Watson-Crick's? Deeparnab stretched with the observation that Einstein's work will be relevant even if there were non-carbon lifeforms!
Eva Tardos spoke about the Generalized Second Price (GSP) auction. She reviewed by now well-known analyses of GSP that PoS=1 and PoA is like 1.6 or 1.2 depending. Her talk focused on the role of uncertainty. In particular, assuming separability, bidder i in position j will get expected value \alpha_i \beta_j v_i where \alpha_i depends on bidder, \beta_j on the position. While bidder i knows value v_i, they dont know the other parameters, and even if they know the distribution of these parameters, they dont know the instantiation of the click probability in any particular auction. In presence of this uncertainty, GSP does not have efficient Nash equilibrium, and the result was that PoA is bounded by like 2.93. The O(1) PoA result is easy to motivate by considering the shading strategy of letting bid of i be v_i/2 (the best bound needs a more detailed strategy). Likewise, this strategy also has direct no-regret learning interpretation, and similar results follow for revenue as well under MHR assumption like Myerson. This research is much-needed, GSP is widely used and it is remarkable how little we know about it.
Other speakers: Mike Saks spoke about his very nice results on finding LIS in sampling and streaming models; Amit Kumar gave a near encyclopedic discussion of approximate clustering; Alas, I missed Nikhil Bansal's talk on randomized rounding; Nisheeth Vishnoi gave a short, rapid talk on closest vector problems with preprocessing, his brain seemingly whirring even as he stated complicated results.
On the earlier day, I gave a general introductory talk on ad auctions and met several researchers from other areas (Venkat: talked about difficulties of localizing even with compass and accelerometer, Kumaran: translating Indian languages; Sriram: language verification). Over dinner, we debated what was the great intellectutal work of 20th century: Einstein's, Turing's or Watson-Crick's? Deeparnab stretched with the observation that Einstein's work will be relevant even if there were non-carbon lifeforms!
Labels: aggregator
posted by metoo at 12:44 PM
0 Comments:
Post a Comment
<< Home