RAIN schedule for Spring Quarter 2012-13
RAIN will be held on Wednesdays from 12:00-1:00pm. All meetings will be held in Y2E2 101. And yes, lunch will be served!
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 AbstractsEliciting and aggregating information from the crowd
Anirban Dasgupta, Yahoo Labs!
Crowdsourcing is now widely used to replace judgement or evaluation by an expert authority with an aggregate evaluation from a number of non-experts, in applications ranging from rating and categorizing online content all the way to evaluation of student assignments in massively open online courses (MOOCs) via peer grading. Two key issues in these settings are: i) how to provide incentives such that agents in the crowd put in their 'full effort' in making good evaluations, as well as truthfully report them and ii)
how to aggregate these evaluations, thereby giving an accurate estimate of the ground truth, given that the agents are of varying, unknown, expertise.
In this talk, we look at both of these problems. For the first, we present an information elicitation mechanism for multiple tasks when agents have endogenous proficiencies, with the following property: exerting maximum effort followed by truthful reporting of observations is a Nash equilibrium with maximum payoff.
For the aggregation problem, we consider a model where each task is binary and each agent has an unknown, fixed, reliability that determines the agent's error rate in performing tasks. The problem is to determine the truth values of the tasks solely based on the agent evaluations. We present algorithms whose error guarantees depend on the expansion properties of the agent-task graph--- these algorithms perform well empirically.
Joint work with Nilesh Dalvi, Arpita Ghosh, Vibhor Rastogi and Ravi Kumar.
Should auctions be complex?
Noam Nisan, Hebrew University of Jerusalem
Do simple auctions suffice for obtaining high revenue or do we need to
design complex ones? For the case of selling one item, Myerson shows
that the answer is "yes": the revenue-maximizing auction is
deterministic with a single reserve price. When selling two (or more)
items, we show that the answer is "no": complex auctions can yield
infinitely more revenue than simple ones, even when there is only a
single bidder with an additive valuation. "Complex" may be defined in
various ways here including allowing randomization as well as our
choice of measuring the auction's menu size. However, when the
bidder’s values for the items are independently distributed, the
answer is “approximately yes”: selling each of two items simply and
separately yields at least half the revenue of any auction.
Joint work with Sergiu Hart.
The extent of price misalignment in prediction markets
David Pennock, Microsoft Research, NYC
We examine misaligned prices for logically related contracts in prediction markets. First, we uncover persistent arbitrages between identical contracts on different exchanges; price support beyond what is in the published order book multiplies the size of these arbitrages. Second, misalignment between logically related contracts listed on the same exchange occurs when contracts systemically shut down or fail to respond efficiently around moments of high information flow. Third, other examples of bounded rationality include: consistent asymmetry between buying and selling, and persistent price lags between exchanges. Fourth, we propose solutions to these problems by fixing logical contradictions within the exchange and providing flexible trading interfaces, freeing traders to focus on providing information in the form they find most natural. Joint work with David Rothschild.
Adaptive Seeding in Social Networks
Yaron Singer, Google and Harvard University
The rapid adoption of social networking technologies throughout the past decade is bringing special attention to algorithmic and data mining techniques designed for maximizing information cascades in social networks. Despite the immense progress which has been made in the past decade, due to limited data access and the structure of social networks the application of state-of-the-art techniques often results in poor performance.
In this talk we will introduce a new framework we call adaptive seeding. The framework is a two-stage model which leverages a phenomenon known as the "friendship paradox" in social networks in order to dramatically increase the spread of information cascades. Our main result shows constant factor approximations are achievable for the most well-studied models of information spreading in social networks. The result follows from new techniques and concepts that may be of independent interest for those interested in stochastic optimization and machine learning.
Joint work with Lior Seeman.
Pricing in Social Networks
Francis Bloch, Ecole Polytechnique, France.
We analyze the problem of optimal monopoly pricing in social networks where agents care about consumption or prices of their neighbors. We characterize the relation between optimal prices and consumers' centrality in the social network. This relation depends on the market structure (monopoly vs. oligopoly) and on the type of externalities (consumption versus price). We identify two situations where the monopolist does not discriminate across nodes in the network (linear monopoly with consumption externalities and local monopolies with price externalities). We also analyze the robustness of the analysis with respect to changes in demand, and the introduction of bargaining between the monopolist and the consumer.
(joint with Nicolas Querou)
Language and Social Dynamics in Online Communities
Cristian Danescu-Niculescu-Mizil, Stanford University and Max Planck Institute SWS.
Much of online social activity takes the form of natural language, from product reviews to conversations on social-media platforms. I will show how analyzing these interactions from the perspective of language use can provide a new understanding of social dynamics in online communities.
I will describe two of my efforts in this direction. The first project leverages insights from psycholinguistics to build a novel computational framework that shows how key aspects of social relations between individuals are embedded in (and can be inferred from) their conversational behavior. In particular, I will discuss how power differentials between interlocutors are subtly revealed by how much one individual immediately echoes the linguistic style of the person they are responding to. The second project explores the relation between users and their community, as revealed by patterns of linguistic change. I will show that users follow a determined lifecycle with respect to their susceptibility to adopt new community norms, and how this insight can be harnessed to predict how long a user will stay active in the community.
This talk includes joint work with Susan Dumais, Michael Gamon, Dan Jurafsky, Jon Kleinberg, Jure Leskovec, Lillian Lee, Bo Pang, Christopher Potts and Robert West.
References: WWW 2013, WWW 2012, WWW 2011.