FCRC (Google Meeting)

At FCRC 2011, Kate Berrios, Lisa McCracken and others of Google organized an event for academic researchers --- students and faculty --- to meet with Googlers. There was an unusual format with 10 or so short 3 slide presentation of projects and their major challenges by googlers and then each of the presenters was available at a table for an hour+ of discussion and questions. Some notes:

• Infrastructure: A web service request gets translated into 100's of parallel machine requests. Rare events (1 in million) happen! Fiuring out timing of processes across machines is a challenge. Performance problems in reality is hard to reproduce in labs because of the scale and complexity of real life.
• Cluster management: external view of the cluster is simple, internal view not as much. Each service depends on scores of others. Anything new introduced makes some people's life better, everyone's life simple bit worse. How do you move an application from one data center to another, when each depends on scores of other services? Failures are a reality, make them first class objects in thinking about systems. Load variations are enormous, 100B to 6 TB per request in some cases.
• Profiling systems at scale. Goal: 0% overhead for profiling across systems, platforms, languages, versions, and it has to be stable and everywhere? Very few benchmarks because world constantly changes and cant be reproduced. Use lot of open source tools and publish them.
• Social: social interactions are more than 2 people, or edges. Social behavior does not happen on graphs. Directionality, symmetry, organizational structure, etc. Are users comfortable with sharing: any measure of this and associated utility?
• Android security: Malware problem due to being popular and also open (due to large numbers). A problem: find andorid malware (client side? power-aware?). Malware perform redundant operations to be deceptive. Prob: Strong authentication methods for cellphone as a personal authenticated device?

I spoke about challenges of ad exchanges, and afterwards, at the table of market algorithms researchers --- Costas Daskalakis, Mukund Sundarajan, Gagan Goel, Vahab Mirrokni, Darja Krushevskaja, and others --- tried to shepherd the conversation to focus on large technical challenges, with the somewhat controversial hypothesis: "Research labs have given researchers good research problems, but not great ones. To engage the best of the research brains, you have to able to pose truly great problems." (In response, Costas said, "Archimedes was interested in squaring the circle." :)) Some of the discussions that ensued:

• Bayesian vs worst case values. Of course! We discussed Leonard Savage's work on Bayesian assumption. Do advertisers know values? Who knows priors, bidders or mechanism. Can we design mechanisms which will work in adversarial as well as Bayesian priors nicely?
• Multidimensional revenue optimal mechanisms, problem to solve. Correlated bidders.
• Auctions that optimize not expected revenue but risk aversion (see eg. Mukund + Qiqi's work), say concave utilities and say other stochastic measures besides expectation? Challenge is also conceptual, what is a suitable benchmark?
• Automated mechanism design?
• Repeated games. 2 bidders with budgets, repeated second price auctions, what happens? Bidders learn, CSists might have a better handle on this theory than say Economists.
• How to integrate auctions and machine learning? Of course! Variations in input vs predictions needs to be modelled. Online solutions vs where ML applies.
• Big problems, eg., can we provide guidance on how science budget should be allocated among various disciplines, or NSF CS budget among different areas? Given a subset of researchers, say we can estimate their impact on the society when funded. Given this oracle, can we allocate funds to people to maximize social welfare? Can we model people switching teams in second round or open bid systems for reallocating funds? Q: Why doesn't NSF give $'s to 2 teams for the same project and get them to compete? For some recent work, see the work of Shay Kutten, Ron Lavi and Amitabh Trehan.
• Level k thinking and dynamics. We discussed 2/3rd of the average game (did you know, there was a museum of money?). If you have a wrong model of competition (say you think you play against MIT students, but we are not), then you can do wrong things even if you are rational. Vahab mentioned several results on level k dynamics and ad auctions.
• Assumption about others. Can one design a mechanism that is independent of assumption about others, robust to beliefs, solution concepts, and despite sophistication of bidders. For ex, some black box where myopic learning leads to good equilibrium?
• Abstract a model, deisgn incentive-compatible mechanism, go to real world, property doesnt hold. We need a notion of how incentive-compatible are bidders. Need a useful analog of approx for incentive compatibility.