Certain Decisions in an Uncertain World
Sham Kakade, University of Pennsylvania
The paradigm of "decision making under uncertainty" is critical in the design and manipulation of large scale technological, social, and economic systems and networks. The foundational work in this area developed mathematically elegant solutions to the "exploration-exploitation dilemma": the conflict between maximizing the immediate reward and gathering information that will be useful in the long-run. Two vital issues to address for applicability to modern problems are: how to tackle settings in which our set of decisions is intractably large (or infinite); and how to choose decisions in large social or economic settings where our actions will influence the behavior of other agents in the setting.
This talk will survey much recent progress. From a technological standpoint, our state of the art algorithms are able to handle decisions sets which may be: paths on a graph (e.g. network routing), locations of sensor networks (where the decision space is continuous), online ads (out of thousands of possibilities). From an economic and social perspective, the talk will survey results on how social decisions are made in economic settings (where interacting agents have their own private incentives), e.g. the sale of digital goods, the design of online ad auctions (where advertisers are interacting with each other in placing bids), and social learning on networks.