Monday, May 28, 2012

Algorithms Day at Google, NYC

Google NY folks organized an Algorithms Research day following STOC and invited a bunch of STOC attendees. Vahab orchestrated the day, and from what I could see, the team of Nitish, MohammadHossein, Silvio and Jon helped out, may be others too, behind the scenes where I couldnt see. The team did a great job!

Eva Tardos, our newest Godel winner, started the day and talked about sequential auction. Bidders know order of auctions.  v_i(A_i) for items A_i for i. n bidders, m items. Goal: social welfare. Agents strategic. Solution concept: subgame perfect eq (for each subgame history). They looked at PoA of complete as well as incomplete information case.  The talk had an interesting example (Dining Bidders) that showed some of the nuances, and had one nontrivial bidding strategy (and its variant for analysis): each player draws  a random sample of value from others values and uses that to strategize. Costas and Moses asked what value distributions challenge the analysis and how the PoA of 3 is affected by the distribution. I asked, if the order of auctions can be determined and how that affects PoA.

Eyal Manor, the Engg Director for Ad Exchange (AdX), spoke next.  Q & A was the key, this was clearly an opportunity for researchers to get answers from a key person in AdX.  Bobby asked, why push bids for each impression sold, why not let ad networks push bids in a flexible way in small bulks. Eyal's answer was,  real time strategies seem important to AdX players.  Someone asked, there is information asymmetry, can AdX equalize the information available to all parties. Eyal answered that AdX did not own all the information in the ecosystem, publishers and other players do, and their data is private or secret. Eva asked, is BlueKai a pain in AdX operations? Eyal said they were good partners. Eva pointed out that Economics says what data should be shared: platforms should share, buyers should not have to share. Again, the issue is data is owned by many parties. Moses asked, what data are not shared. Eyal gave the example of someone day bought a ticket, bank login etc.

Alfred, VP of Google Research, spoke via video. He used the occasion to let folks know that Google was providing some space for Cornell's operations in NY, which is good news for Academia. Alfred couldnt resist posing some technical  challenges: we dont understand fairness of auctions to individual users; we have complex auctioning systems and very sophisticated distributed systems, how do we quantity and control risk?

There were several other talks during the day (bobby, gagan, mohammad, andrew mcgregor, et al) which I am unable to summarize here. Vahab gave an excellent overview of research in Google NY and provided pointers to folks who were experts in different projects. Towards the end, Mukund spoke about some interesting problems with interpreting sales data, and our other new Godel Prize winner Tim spoke about simple and optimal auctions.

Prabhakar called me an old timer, and I felt like one, slightly out of touch with it all. I ran the first of such meetings in 2009 after SODA, and it is great to see the continuing tradition. It was also good to catch up with Sanjeev, Stefano, Sampath, Seffi and others, that is just the S's.



Post a Comment

<< Home