(USC)The Mysteries of Security Games:
Equilibrium Computation Becomes Combinatorial Algorithm Design
|9:30||Pathikrit Basu (Caltech)Repeated coordination with private learningWe study a repeated game with payoff externalities and observable actions where two players receive information over time about an underlying payoff-relevant state, and strategically coordinate their actions. Players learn about the true state from private signals, as well as the actions of others. They commonly learn the true state (Cripps et al., 2008), but do not coordinate in every equilibrium. We show that it is possible to construct equilibria in which players eventually coordinate on the correct action, for any discount factor. For high discount factors we show that in addition players can also achieve efficient payoffs.|
|10:00||Jiasi Chen (UCR)Economic Analysis of Wireless Network Infrastructure Sharing|
Market: How Theory Influenced Practice I will talk about an optimal online algorithm for Internet Ad markets, such as Google's AdWords market. Although this result was obtained over a decade ago when the algorithmic and economic/game-theoretic issues of this marketplace were just being understood, its impact is becoming clear only in recent years. Our result addresses a central algorithmic issue underlying this marketplace: how to match query keywords to advertisers so as to maximize Google's revenue.
I will give an overview of the novel LP-based techniques that led to this result and the simple heuristic, of bid scaling, that is suggested by our algorithm. I will also present a formal framework for thinking about budgeted auctions more generally. These ideas have been widely adopted by Google and other search engine companies.
Purely theoretical work, from the 1990s, on the online bipartite matching problem greatly benefitted our work. The latter problem, while mathematically clean and elegant, appears to have no applications. On the other hand, the multi-billion dollar online ad industry has become the key source of revenues for several Internet companies. For algorithms designers, this a very happy story of practical impact from rich theory.
This talk is intended for a wide audience
|1:00||Hamid Nazerzadeh (USC)Balancing Ride-hailing Marketplaces via Surge Pricing|
|1:30||Philipp Strack (UC Berkeley)Turning Up the Heat: The Demoralizing Effect of Competition in ContestsWe demonstrate, in the standard, symmetric complete-information all-pay contest framework, that, whenever marginal effort costs are increasing, increasing contest competitiveness demoralizes contestants, thereby reducing the mean and increasing the riskiness of output. This demoralization effect imposes testable restrictions on the mean and variability of output which we verify using extant experimental and field data. These results have significant implications: Although often criticized as evidence of laxity or cronyism, muting competition (e.g., adopting softer grading curves or less high-powered promotion systems) both reduces inequality and increases expected output. Reducing class size, simply by reducing classroom competition, improves student performance.|
|2:30||Elchanan Mossel (MIT)Information flow on (deep) networks|
Vahab Mirrokni (Google) Robust Ad Allocation: Online Optimization & Auction Design