Berkeley's
EconCS Seminar Fall 10 abstracts

How to Manipulate Single Elimination Tournaments in the Braverman-Mossel model

Speaker: Virginia Vassilevska
Time:     Feb 1st, 2011
Place:     410 Hearst Mining

Speaker: Hari Phatak
Time:     Feb 8th, 2011
Place:     410 Hearst Mining

Is there a trade-off between the complexity of prediction market games and the efficiency with which these games aggregate information? I construct a static model of a betting market in which uncertainty over type and the presence of search costs influences the way in which an information-gathering principal structures the menu of bets offered to agents who possess private information. The principal in my environment must trade-off the richness of information collected from complex menus against the biased behavior and discouragement these menus induce in agents. I describe an experimental setup designed to detect whether long menus discourage agents from placing bets or lead to inefficient betting.

On the Competitive Ratio of Online Sampling Auctions

Speaker: George Pierrakos
Time:     Feb 15th, 2011
Place:     410 Hearst Mining

We introduce a novel kind of online profit-maximizing auctions for digital goods. We assume adversarial bid selection, uniformly random arrivals and our goal is to design auctions that are constant competitive with $\mathcal{F}^{(2)}$; in this sense our model lies at the intersection of prior-free mechanism design and secretary problems. We present some natural auctions, both randomized and deterministic, and study their competitive ratio; our analysis reveals some interesting connections of these auctions with RSOP.

Mechanisms for Maximizing Influence in Social Networks

Speaker: Yaron Singer
Time:     Feb 22nd, 2011
Place:     410 Hearst Mining

Throughout the past decade there has been extensive research on algorithmic and data mining techniques for solving the problem of influence maximization in social networks: if one can convince a subset of individuals to influence their friends to adopt a new product or technology, which subset should be selected so that the spread of influence in the social network is maximized?

Despite the progress in modeling and techniques, the incomplete information aspect of problem has been largely overlooked. While the network structure is often available, the inherent cost individuals have for influencing friends is difficult to extract.

In this talk we will discuss mechanisms that extract individuals' costs in well studied models of social network influence. We follow the mechanism design framework which advocates for truthful mechanisms that use allocation and payment schemes that incentivize individuals to report their true information. Beyond their provable theoretical guarantees, the mechanisms work well in practice. To show this we performed experiments on the Mechanical Turk platform and used social network data to provide experimental evidence of the mechanisms' practical effectiveness.

Economics of BitTorrent Communities

Speaker: Aviv Zohar
Time:     Mar 1st, 2011
Place:     410 Hearst Mining

Over the years, private file-sharing communities built on the BitTorrent protocol have developed their own policies and mechanisms for motivating members to share content and contribute resources. By requiring members to upkeep a minimum share ratio between uploads and downloads, private communities effectively establish credit systems, and with them a full-fledged economy. In attempting to understand the functioning of private communities, most previous studies view such communities as computer systems and focus on their ability to efficiently distribute files. In this paper, we advocate for adopting an additional perspective where communities are viewed as economic systems in which users adapt to site policies. We report on a year-long measurement study of DIME---a community for sharing live concert recordings---through which we find that users rationally react to cost differentials when making decisions on which files to consume. We observe significant disparities in the effective cost of new and old files, and examine the effect this has on the P2P economy. We find evidence of a mis-match between supply and demand and suggest some ways to improve the market.

Economics of BitTorrent Communities

Speaker: Aviv Zohar
Time:     Mar 1st, 2011
Place:     410 Hearst Mining

Over the years, private file-sharing communities built on the BitTorrent protocol have developed their own policies and mechanisms for motivating members to share content and contribute resources. By requiring members to upkeep a minimum share ratio between uploads and downloads, private communities effectively establish credit systems, and with them a full-fledged economy. In attempting to understand the functioning of private communities, most previous studies view such communities as computer systems and focus on their ability to efficiently distribute files. In this paper, we advocate for adopting an additional perspective where communities are viewed as economic systems in which users adapt to site policies. We report on a year-long measurement study of DIME---a community for sharing live concert recordings---through which we find that users rationally react to cost differentials when making decisions on which files to consume. We observe significant disparities in the effective cost of new and old files, and examine the effect this has on the P2P economy. We find evidence of a mis-match between supply and demand and suggest some ways to improve the market.

Bargaining solutions in the cloud

Speaker: Eric Friedman
Time:     Mar 8th, 2011
Place:     410 Hearst Mining

I talk about some interesting connections between bargaining solutions (such as Nash's seminal work) and resource allocation in cloud computing.

Bayesian models of cognition

Speaker: Tom Griffiths
Time:     Mar 15th, 2011
Place:     410 Hearst Mining

The idea of explaining human behavior in terms of that of rational agents has recently been the subject of a great deal of criticism in behavioral economics. However, rational methods such as Bayesian inference are at the heart of recent advances in machine learning and artificial intelligence. This creates a puzzle, since apparently irrational people are still far better than these rational machines at some basic cognitive tasks, such as learning a language, forming a concept from a small number of examples, or determining the causal relationships that characterize our world. I will talk about how we might resolve this puzzle. First, I will show how the assumption of rationality can help us understand how people make inductive inferences, and help us design new experimental methods for identifying the expectations that guide human learning. Second, I will discuss how we can connect this approach to psychologically motivated cognitive constraints, considering heuristics that might allow people to approximate Bayesian inference. Both parts of the talk draw on ideas from computer science, particularly Monte Carlo methods.

Attributing Changes in Multilinear Characteristic Functions

Speaker: Mukund Sundararajan
Time:     Mar 29th, 2011
Place:     410 Hearst Mining

We study the attribution problem, that is, the problem of attributing a change in the value of a characteristic function to its independent variables. We make three contributions. First, we propose a formalization of the problem based on a standard cost-sharing model. Second, in our most important technical contribution, we show that there is a unique path attribution method that satisfies Affine Scale Invariance and Anonymity if and only if the characteristic function is multilinear. We term this the Aumann-Shapley-Shubik method. Third, we study multilinear characteristic functions in detail; we describe a computationally efficient implementation of the Aumann-Shapley-Shubik method and discuss practical applications to portfolio analysis, e-commerce, and sports statistics.

Online Labor Markets

Speaker: Anand Kulkarni
Time:     Apr 05th, 2011
Place:     410 Hearst Mining

Combinatorial Prediction Markets and Efficient Automated Market Makers

Speaker: Jake Abernethy
Time:     Apr 12th, 2011
Place:     410 Hearst Mining

A prediction market offers a menu of contracts whose payout depends on the outcome of an uncertain future event. As prices are set according to market demand, the price of a contract will reveal information, in aggregate, about the presumed likelihood of a particular outcome. In this talk I'll discuss how to design a prediction market based on an automated "market maker" -- an institution that sets prices adaptively for each contract -- that is efficient even when the outcome space is exponentially large (or infinite). This is achieved using tools from convex optimization; in particular, conjugate duality.

This is joint work with Yiling Chen and Jenn Wortmann Vaughan. Our forthcoming EC 2011 paper can be found here: http://www.eecs.berkeley.edu/~jake/ec041-abernethy.pdf

Identity and Social Distance in Network Formation

Speaker: Joan De Marti
Time:     Apr 19th, 2011
Place:     410 Hearst Mining

We analyze a network formation model where agents belong to different communities. Both individual benefits and costs depend on direct as well as indirect connections. Benefits of an indirect connection decrease with distance in the network while the cost of a link depends on the type of agents involved. Two individuals from the same community always face a low linking cost and the cost of forming a relationship for two individuals of different communities diminishes with the rate of exposure of each of them to the other community. We derive a number of results with regard to equilibrium networks. In particular, socialization among the same type of agents can be weak even if the within-type link cost is very low and oppositional identity patterns can arise for a wide range of parameters. Our model also suggests that policies aiming at reducing segregation are socially desirable only if they reduce the within-community cost differential by a sufficiently large amount.

Talking to Your Friends Makes it Worse - But by How Much?

Speaker: Elchanan Mossel
Time:     Apr 25th, 2011
Place:     410 Hearst Mining

A common view is that social interactions improve the quality of decisions and actions taken by individuals. In this talk I will present a natural model where social interaction clearly results in inferior decisions taken. I will then ask the question of how much worse the outcome is after the social interaction?

Based on ongoing work with Joe Neeman and Omer Tamuz