abhi shelat and Muthuramakrishnan Venkitasubramaniam (U. Rochester) receive Google Research Award
Congratulations to abhi shelat, and his colleague Muthuramakrishnan Venkitasubramaniam from U. Rochester. Google received 808 proposals and funded 122.
Title: Fast Secure Computation via Divide and Conquer
Secure two-party computation for any function f() allows for mutually distrustful parties to collaborate and compute f() jointly while leaking as little information as possible on their private inputs. Recent work consisting of protocol improvements and implementation insights illustrates the approaching practicality of this technology. This proposal suggests an novel direction to designing secure computation protocols that is inspired by the algorithmic technique of divide-and-conquer.
abhi’s is not the only U.Va. proposal to be funded! Denis Nekipelov (Econ, with a courtesy appointment in CS) also won an award! Denis’s proposal — which has a significant CS dimension — was joint with Eva Tardos from Cornell.
Title: Econometric inference and algorithmic learning in games
With auctions having emerged as main source of revenue on the Internet, there are multitudes of interesting data sets for user behavior in Internet auctions. Classical analysis of game outcomes relied on the notion of Bayes Nash equilibrium in multiple ways, both in analysing outcomes, and inferring the user’s types or valuations from the observed data. However, the assumption that these data are generated by the equilibrium behavior of the players is often unrealistic. The main challenge considered in this proposal is the dynamic nature of the online environ- ment. The focus of the proposed project is on developing a methodology for inference in games without relying on the standard notions of the stability of outcomes. Typical games describing on- line environments, including the Internet auctions, are best thought of as repeated games, where participation and the strategies of agents evolve over time. The main goal of the proposed work is to develop a theory for game outcomes in such an environment, and understand how to infer from the observed data the player’s valuations and their strategies in learning how to play the game.