RAIN schedule for Autumn Quarter 2013-14
The RAIN seminar gratefully acknowledges support from the Computer Forum and Yahoo!
Google Calendar for RAIN
Previous year's talks
Archived talks can be accessed here.
Talk AbstractsAlgorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games
Tuomas Sandholm, Carnegie Mellon University
Incomplete-information games - such as most auctions, negotiations,
and future (cyber)security settings - cannot be solved using minimax
search even in principle. Completely different algorithms were
needed. A dramatic scalability leap has occurred in our ability to
solve such games over the last seven years, fueled largely by the
Annual Computer Poker Competition. I will discuss the key
domain-independent techniques that enabled this leap, including
automated abstraction techniques and approaches for mitigating the
issues that they raise, new equilibrium-finding algorithms, safe
opponent exploitation methods, techniques that use qualitative
knowledge as an extra input, and endgame solving techniques. I will
finish by benchmarking poker programs against the best human poker
professionals and by discussing what humans can learn from the
Bio: Tuomas Sandholm is Professor at Carnegie Mellon University in the Computer Science Department, Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), and CMU/UPitt Joint Ph.D. Program in Computational Biology. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 450 papers on market design, optimization (search and integer programming, stochastic optimization, and convex optimization), game theory, auctions and exchanges, automated negotiation and contracting, coalition formation, voting, electronic commerce, preference elicitation, normative models of bounded rationality, resource-bounded reasoning, game solving, equilibrium finding, safe exchange, and machine learning. He has over 20 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems. In parallel with his academic career, he was Founder, Chairman, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 of the world's largest-scale generalized combinatorial auctions, with over $60 billion in total spend and over $6 billion in generated savings. Dr. Sandholm's algorithms also run the US-wide UNOS kidney exchange. He is Founder and CEO of Optimized Markets, Inc., a new startup that is bringing a new paradigm to advertising sales and scheduling - in TV, display, streaming, mobile, and cross-media advertising. He also serves as the redesign consultant of Baidu's sponsored search auctions and display advertising markets; within two years Baidu's market cap increased 5x to $50 billion due to better monetization. He has served as consultant, advisor, or board member for Yahoo!, Google, Granata Decision Systems, Netcycler, and others. He has applied his game-solving algorithms to develop some of the world's best poker-playing programs. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his many honors are the NSF Career Award, inaugural ACM Autonomous Agents Research Award, Sloan Fellowship, Carnegie Science Center Award for Excellence, and Computers and Thought Award. He is Fellow of the ACM and AAAI.
"Going Viral" and the Structure of Online Diffusion
Sharad Goel, Microsoft Research NYC
New products, ideas, norms and behaviors are often thought to propagate through a person-to-person diffusion process analogous to the spread of an infectious disease. Until recently, however, it has been prohibitively difficult to directly observe this process, and thus to rigorously quantify or characterize the structure of information cascades. In one of the largest studies to date, we describe the diffusion structure of billions of events across several domains. We find that the vast majority of cascades are small, and are characterized by a handful of simple tree structures that terminate within one degree of an initial adopting "seed." While large cascades are extremely rare, the scale of our data allows us to investigate even the one-in-a-million events. To study these rare, large cascades, we develop a formal measure of what we label "structural virality" that interpolates between two extremes: content that gains its popularity through a single, large broadcast, and that which grows via a multi-generational cascade where any one individual is directly responsible for only a fraction of the total adoption. We find that the very largest observed events nearly always exhibit high structural virality, providing some of the first direct evidence that many of the most popular products and ideas grow through person-to-person diffusion. However, medium-sized events -- having thousands of adopters -- exhibit surprising structural diversity, and are seen to grow both through broadcast and viral means. Finally, we show that our empirical results are largely consistent with an SIR model of contagion on a scale-free network, reminiscent of previous work on the long-term persistence of computer viruses.
Bio: Sharad Goel is a Senior Researcher at Microsoft Research - New York City, where he works in the general area of computational social science, an emerging discipline at the intersection of computer science, statistics, and the social sciences. Sharad has broad interests, and has worked on diverse topics in economics, political science, marketing, psychology, sociology, computer science, and statistics. He is particularly interested in using large-scale datasets and computing tools to measure and describe complex social phenomena. Sharad holds a PhD in Applied Mathematics and a Masters in Computer Science from Cornell, and a BS in Mathematics from the University of Chicago. Following postdoctoral positions in the math departments at Stanford and the University of Southern California, he worked for several years in the Microeconomics and Social Systems group at Yahoo Research.
The Value of Network Information
Itay Fainmesser, Brown University
Motivated by the proliferation of companies, such as Facebook.com, MySpace and Twitter, whose business models rely, at least in part, in monetizing the information on the interactions and influences of their users, we evaluate how much a monopoly can increase its profit by exploiting individual level data on "who influences whom" when designing his selling strategy. We also analyze the effect that the use of such information has on consumers' welfare. Our framework incorporates a rich set of market products, including goods characterized by global and local network effects. It also has the novel feature to distinguish between the level of influence of a consumer and her susceptibility to influence, a distinction that has been shown to be important empirically.
Joint work with Andrea Galeotti.
Bio: Itay Fainmesser is an Assistant Professor of Economics at Brown University. He received his PhD from Harvard University in May 2010. His research focuses on Market Design, Matching Markets, and Social and Economic Networks, and uses both theoretical modeling and experimental methods. Itay is visiting the Economics Department at Stanford University for the academic year 2013-2014.
Prediction in complex networks: The impact of structure on learning and prediction
Jennifer Neville, Purdue University
The recent popularity of online social networks and social media has increased the amount of information available about users' behavior--including current activities and
interactions among friends and family. This rich relational information can be exploited to predict user interests and preferences even when individual data is sparse, as the
relationships are a critical source of information that identify potential statistical dependencies among people. Although network data offer several opportunities to improve
prediction, the characteristics of real world datasets present a number of challenges to accurately incorporate relational information into machine learning algorithms. In
this talk, I will discuss the effects of sampling, parameter tying, and model roll-out on the properties of the resulting statistical models--which occurs through a complex
interaction between local model properties, global network structure, and the availability of observed attributes. By understanding the impact of these interactions on
algorithm performance (e.g., learning, inference, and evaluation), we can develop more accurate and efficient analysis methods for large, partially-observable social network
and social media datasets.
Bio: Jennifer Neville is an associate professor at Purdue University with a joint appointment in the Departments of Computer Science and Statistics. She received her PhD from the University of Massachusetts Amherst in 2006. In 2012, she was awarded an NSF Career Award, in 2008 she was chosen by IEEE as one of "AI's 10 to watch", and in 2007 was selected as a member of the DARPA Computer Science Study Group. Her research focuses on developing data mining and machine learning techniques for relational and network domains, including citation analysis, fraud detection, and social network analysis.