Skip to content Skip to navigation

The RAIN seminar is held on Wednesdays from 12:00-1:00pm in Y2E2 101 . And yes, lunch is provided!

RAIN schedule for Autumn Quarter 2016-17

Date Speaker Topic
October 12
Philippe Rigollet at OIT seminar, room M109 at GSB Online Learning in Repeated Auctions
November 2
Dennis Feehan Network reporting methods for sample surveys
November 16
Mohammad Akbarpour Timing "versus" Matching: Dynamic Matching on Stochastic Networks
November 30
Ariel Procaccia Computational Social Choice: For the People

Google Calendar for RAIN

Previous year's talks

Archived talks can be accessed here.

Talk Abstracts

Computational Social Choice: For the People
Ariel Procaccia, CMU

Computational social choice deals with algorithms for aggregating individual preferences or opinions towards collective decisions. AI researchers (including myself) have long argued that such algorithms could play a crucial role in the design and implementation of multiagent systems. However, in the last few years I have come to realize that the "killer app" of computational social choice is helping people -- not software agents -- make joint decisions. I will illustrate this theme through two recent endeavors:, a website that offers provably fair solutions to everyday problems; and, which provides optimization-driven voting methods. Throughout the talk, I will devote special attention to the theoretical foundations and results that make these services possible.

Bio: Ariel Procaccia is an Assistant Professor in the Computer Science Department at Carnegie Mellon University, and an Affiliated Faculty in the Machine Learning Department. He usually works on problems at the interface of computer science and economics. His distinctions include the IJCAI Computers and Thought Award (2015), the Sloan Research Fellowship (2015), the NSF Faculty Early Career Development Award (2014), and the IFAAMAS Victor Lesser Distinguished Dissertation Award (2009); as well as multiple paper awards including Best Paper (2016) and Best Student Paper (2014) at the ACM Conference on Economics and Computation (EC). He is co-editor of the Handbook of Computational Social Choice (Cambridge University Press, 2016).

Timing "versus" Matching: Dynamic Matching on Stochastic Networks
Mohammad Akbarpour, Stanford

We introduce a dynamic analogue of Erdos-Renyi random graph model and study the problem of finding the "maximum matching" in such dynamic graph. In our model, agents arrive and depart stochastically, and the composition of the trade graph depends endogenously on the matching algorithm. We show that if the planner can identify agents who are about to depart, then waiting to thicken the market is highly valuable, and if the planner cannot identify such agents, then matching agents greedily is close to optimal. The planner's decision problem in our model involves a combinatorially complex state space. However, we show that simple local algorithms that choose the right time to match agents, but do not exploit the global graph structure, can perform close to complex optimal algorithms. Finally, we consider a setting where agents have private information about their departure times, and design a continuous-time dynamic mechanism to elicit this information.

Joint work with Shengwu Li and Shayan Oveis Gharan

Bio: Mohammad Akbarpour is an Assistant Professor of Economics at Stanford GSB. He completed his PhD at Stanford University Economics department in 2015, then spent the 2015-2016 academic year at the University of Chicago Economics department, before coming back to Stanford in September 2016.

Network reporting methods for sample surveys
Dennis Feehan, UC Berkeley

Surveys have traditionally been based on the idea that researchers can estimate characteristics of a population by obtaining a sample of individuals and asking them to report about themselves. Network reporting surveys generalize this traditional approach by asking survey respondents to report about members of their personal networks. Network reporting surveys can be used to study many important rare and hidden populations for which traditional survey methods are inadequate; for example, the approach has been used to estimate the size of epidemiologically important groups like sex workers, drug injectors, and men who have sex with men. I will introduce a framework for developing estimators from network reporting surveys and then I will present some results from a nationally-representative survey experiment that my colleagues and I conducted in Rwanda.

Bio: Dennis Feehan is an Assistant Professor in the Department of Demography at UC Berkeley. He completed his PhD at Princeton University in 2015 and spent the fall/winter of 2015 as a postdoc at Facebook before starting at Berkeley last January.

Online Learning in Repeated Auctions
Philippe Rigollet, MIT

Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical. Comparing our performance against that of the best fixed bid in hindsight, we show that sublinear regret is also achievable in this case. For both the stochastic and adversarial models, we prove matching minimax lower bounds showing our strategies to be optimal up to lower-order terms. To our knowledge, this is the first complete set of strategies for bidders participating in auctions of this type

Joint with Jonathan Weed, and Vianney Perchet.

Bio: Philippe Rigollet