Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Game Theory & Computation Seminar Series

The Game Theory and Computation Seminar is a weekly theory seminar series, highlighting recent advances in economic theory and computer science.  The range of topics includes algorithmic game theory, market design, microeconomic theory, social network theory, and other topics related to game theory and computation.

The agenda typically consists of a prepared presentation, followed by a period of questions and discussion. The seminar is aimed at an audience of theory researchers and students. We welcome members of the local academic community to attend.

The seminar's location alternates weekly between the MSR conference center at One Memorial Drive and the Littauer Center at Harvard University.  Please check the location information listed for upcoming talks.

Upcoming Talks

Do-Not-Track and the Economics of Third-Party Advertising

Georgios Zervas, Boston University
Wednesday, December 17  (Note the unusual day)
4:00 PM – 5:00 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
Retailers regularly target users with online ads based on their web browsing activity, benefiting both the retailers, who can better reach potential customers, and content providers, who can increase ad revenue by displaying more effective ads. The effectiveness of such ads relies on third-party brokers that maintain detailed user information, prompting legislation such as do-not-track that would limit or ban the practice. We gauge the economic costs of such privacy policies by analyzing the anonymized web browsing histories of 14 million individuals. We find that only 3% of retail sessions are currently initiated by ads capable of incorporating third-party information, a number that holds across market segments, for online-only retailers, and under permissive click-attribution assumptions. Third-party capable advertising is shown by 12% of content providers, accounting for 32% of their page views; this reliance is concentrated in online publishing (e.g., news outlets) where the rate is 91%. We estimate that most of the top 10,000 content providers could generate comparable revenue by switching to a “freemium” model, in which loyal site visitors are charged $2 (or less) per month. We conclude that do-not-track legislation would impact, but not fundamentally fracture, the Internet economy.

Available at: http://papers.ssrn.com/sol3/papers.cfm?abstract_id=2505643

Biography
Georgios Zervas is an assistant professor of Marketing at Boston University School of Management. Before joining BU in 2013 he was a Simons postdoctoral fellow at Yale, and an affiliate at the Center for Research on Computation and Society at Harvard. He received his PhD in Computer Science in 2011 from Boston University. He is broadly interested in understanding the strategic interactions of firms and consumers participating in internet markets using large-scale data collection and econometric analysis.

Back to top

Past Speakers

Two-sided matching via balanced exchange: Theory and applications

Utku Ünver, Boston College
Monday, December 1
4:00 PM – 5:30 PM
Harvard University, Littauer Center, 3rd Floor Lounge

Description
We introduce a new class of matching problems that mimic two-sided exchange programs. These include, for example, the tuition exchange programs used by colleges in the US to help the dependents of their eligible faculty use tuition benefits offered at other participating institutions. Each participating institution (i.e., firm) has to maintain a balance between the numbers of exported and imported students (i.e., workers), because a negative balance -- exports exceeding imports -- is generally penalized by suspension from the program. On the other hand, these programs function through decentralized markets that make it difficult to sustain overall balance, especially since workers and firms have preferences over each other.

We show that stable equilibria discourage net-exporting firms from exchange. We introduce two-sided top-trading-cycles (2S-TTC) mechanism that is balanced-efficient, worker-strategy-proof, individually rational, and respecting priority bylaws regarding worker eligibility. We prove 2S-TTC is the unique mechanism fulfilling these objectives. Moreover, it encourages exchange, since full participation is a dominant strategy for firms.

Joint work with Umut Mert Dur.

Biography
Utku Ünver, a Professor of Economics at Boston College, is an economic theorist with research interests in market design, mechanism design, and game theory with emphasis on the theory and practice of matching markets and allocation/exchange of discrete resources. His recent research includes (but is not limited to) the design of kidney exchange clearinghouses, improving recommendation systems used in adoption of children in foster care, matching in two-sided markets such as tuition exchange in college admissions, and school choice mechanisms. He has also worked on implementing kidney exchanges and improving adoption schemes in real life with policy workers.

Back to top

SPECIAL EVENT:  Reverse AGT workshop on Optimal Taxation
Monday, November 24
1:00 PM – 4:00 PM
Harvard University, 20 University Road, Room 646

Back to top

Bidding Games, Bargaining and Efficient Allocations

Reshef Meir, Harvard University
Monday, November 10
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
Bidding games are extensive form two-player games where players bid over who is going to play next. Zero-sum bidding games have been studied in the literature, mainly as variations of popular recreational games such as Chess and Tic-Tac-Toe.

We study for the first time bidding games with general utility functions, showing that there always exists a natural pure subgame perfect Nash equilibrium with the following desirable properties: (a) a Pareto-efficient outcome is reached for any initial budget; (b) any Pareto-efficient outcome is attained for some initial budget allocation; and (c) each agent’s utility is weakly monotone in her budget.

We show how this result can be applied to design a simple and efficient bargaining mechanism for allocating items among two agents with arbitrary valuation functions. Time permitting, we will discuss the computational complexity aspects and some possible extensions of the mechanism to randomized settings.

Joint work with Gil Kalai and Moshe Tennenholtz.

Biography
Reshef is a post-doctoral fellow at Harvard's Center for Research on Computation and Society. He received his PhD from the Hebrew University in Jerusalem, which has received an honorable mention for Victor Lesser Distinguished Dissertation Award (IFAAMAS), and won the Michael B. Maschler Prize for research in game theory (shared with Omer Tamuz). His main research areas are Computational Game Theory, Mechanism Design, and Bounded Rationality.

Back to top

Incentivizing Exploration

Bobby Kleinberg, Cornell University
Monday, November 3
4:00 PM – 5:30 PM
Harvard University, Littauer Center, 3rd Floor Lounge

Description
An important recent theme in the development of on-line social systems is the potential of crowdsourced effort to solve large problems — defining tasks in which many people can each contribute a small amount of time to the overall goal. In some cases the arrangement is based on a direct compensation scheme, in which a (low) rate is paid for each unit of work performed. But in many settings one only has access to a crowd "in the wild", as they go about their everyday activities. Examples include product recommendations, social news readers, and scientific activities ranging from crowdsourced "citizen science" to the funding of research by national agencies.

In all of these domains, there is a problem of misaligned incentives: the designer's goal is to carry out exploration (of the space of news stories, products, bird habitats, etc.) as efficiently as possible, but for reasons of scale they must implement the exploration via a crowd composed of members who each derive their own utility from participating in the exploration. We model this as a multi-armed bandit problem in which selfish, myopic agents pull arms with publically observable outcomes, and a principal seeking to maximize the cumulative time-discounted reward may influence the agents by offering monetary (or other) rewards contingent on choosing particular actions. Our main result is a full characterization of the trade-off between the expected payments the principal must make and the total reward that can be achieved.

Joint work with Peter Frazier, David Kempe, and Jon Kleinberg.

Biography
Robert Kleinberg is an Associate Professor of Computer Science at Cornell University. His research studies the design and analysis of algorithms, and their relations to economics, learning theory, and networks. Prior to receiving his doctorate from MIT in 2005, Kleinberg spent three years at Akamai Technologies, where he assisted in designing the world's largest Internet Content Delivery Network. He is the recipient of a Microsoft Research Faculty Fellowship, an Alfred P. Sloan Foundation Fellowship, and an NSF CAREER Award.

Back to top

Simple Mechanisms with Simple Strategies

Vasilis Syrgkanis, Microsoft Research
Monday, October 27
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
We introduce single-bid auctions as a new format for combinatorial auctions. In single-bid auctions, each bidder submits a single bid for the right to buy items at a fixed price. Contrary to other simple auction formats, such as simultaneous or sequential single-item auctions, bidders can implement no-regret learning strategies in polynomial time. Price of anarchy bounds for correlated equilibria concepts in single-bid auctions therefore have more bite than their counterparts in auctions where learning is not known to be computationally tractable. To this end, we show that for any subadditive valuations the social welfare at equilibrium is an \Theta(\log m)-approximation to the optimal social welfare, where m is the number of items. We also provide tighter approximation results for several subclasses. Our welfare guarantees hold for Nash equilibria and no-regret learning outcomes in both Bayesian and complete information settings via the smooth-mechanism framework. Of independent interest, our techniques show that in a combinatorial auction setting, efficiency guarantees of a mechanism via smoothness for a very restricted class of cardinality valuations extend, with a small degradation, to subadditive valuations, the largest complement-free class of valuations.

Joint work with Nikhil Devanur, Jamie Morgenstern, Matt Weinberg.

Biography

Vasilis is a Postdoctoral researcher at MSR NYC. He recently received his PhD in Computer Science from Cornell University under the supervision of Prof. Eva Tardos. His research interests include algorithms, game theory, auction theory, mechanism design, crowdsourcing and computational complexity. Driven from electronic market applications such as ad auctions, his research focuses on the design and analysis of approximately efficient mechanisms with guaranteed good properties even when players participate in many mechanisms simultaneously or sequentially and even if they use learning algorithms to identify how to play the game and have incomplete information about the competition. More broadly he is interested in quantifying the inefficiency of systems with strategic users.

Back to top

Social Learning with Costly Search and Social Advertising

Mallesh Pai, University of Pennsylvania
Monday, October 6
4:00 PM – 5:30 PM
Harvard University, Littauer Center

Description
We study a sequential social learning model where agents may privately acquire information by costly search. Search costs of agents are private. We show that asymptotic learning occurs if and only if search costs are not bounded away from zero. We explicitly characterize all equilibria for the case of two actions, and show that the probability of late moving agents taking the suboptimal action vanishes at a linear rate. Social welfare converges to the social optimum as the discount rate converges to one if and only if search costs are not bounded away from zero.

We use this analysis to study agents who are active on a (reduced form) online social network, and must select among competing products of unknown quality. We study the impact of advertising by duopolist firms, and the incentives of the underlying social network. We consider display advertising, which is standard firm to consumer advertising, and social advertising, in which agents who purchased that firm's product are highlighted to their friends. We show that in equilibrium, the heterogeneous firms spend the same amount on advertising. Social advertising may be more lucrative than standard display advertising. However, both forms of advertising have no effect on consumer welfare. A social network motivated by advertising revenues may limit the amount of information agents see about actions by other agents, since this will increase advertising revenue. This reduces consumer welfare relative to the first best, since early movers' purchases are informative about relative quality.

This talk is based on two papers, "Social Learning With Costly Search" and "Do Online Social Networks Increase Welfare?", both joint with Manuel Mueller-Frank.

Biography
Mallesh M Pai is an Assistant Professor of Economics in the Department of Economics at the University of Pennsylvania since 2011. He is also an affiliate of the Warren Center for Network and Data Sciences. His research interests include mechanism design/auction theory, the economics of privacy, social networks/social learning and statistical decision theory.

He has a PhD in Managerial Economics and Strategy from the Kellogg School of Management, Northwestern University, and a Bachelor's degree in Computer Science and Engineering from the Indian Institute of Technology, Delhi.

Back to top

Risk Dynamics in Trade Networks

Rafael Frongillo, Harvard
Monday, September 29
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
We present a new framework to model interactions among agents which seek to negotiate to minimize their risk with respect to some future outcome. We quantify this risk using the concept of risk measures from finance, and introduce a class of trade dynamics which allow agents to trade contracts contingent upon the future outcome. We then show that these trade dynamics exactly correspond to a variant of randomized coordinate descent. By extending the analysis of these coordinate descent methods to account for our more organic setting, we are able to show convergence rates for very general trade dynamics, showing that the market or network converges to a unique steady state. Applying these results to prediction markets, we expand on recent results by adding convergence rates and general aggregation properties.

Joint work with Mark Reid (ANU & NICTA)

Biography
Rafael Frongillo is a computer scientist working on theoretical problems at the interface between machine learning and economics, primarily focusing on problems such as crowdsourcing or prediction markets which involve the exchange of information for money. Before coming to Harvard, he was a postdoc at Microsoft Research in New York City, and he received his Ph.D. at UC Berkeley, advised by Christos Papadimitriou and supported by the NDSEG Fellowship.

Back to top

On the Efficiency of the Walrasian Mechanism

Moshe Babaioff, Microsoft Research
Monday, September 15
4:00 PM – 5:30 PM
Microsoft Research, One Memorial Drive (1st Floor)

Description
Central results in economics guarantee the existence of efficient equilibria for various classes of markets. An underlying assumption in early work is that agents are price-takers, i.e., agents honestly report their true demand in response to prices. A line of research initiated by Hurwicz (1972) is devoted to studying market performance when agents are strategic about their demands. This is captured by the Walrasian Mechanism that proceeds by collecting reported demands, then finding clearing prices for the reported market.

In practice, agents commonly reduce their demand, leading to inefficient outcomes. We ask how inefficient the equilibria can be. We show that the welfare of every pure Nash equilibrium of the Walrasian mechanism is at least one quarter of the optimal welfare, when players have gross substitute valuations and do not overbid. Our result shows that approximate efficiency is guaranteed regardless of the size of the market.

Our results extend to Bayes-Nash equilibria and outcomes of no regret learning via the smooth mechanism framework. We also extend our bounds to any mechanism that maximizes welfare with respect to the declared valuations and never charges agents more than their bids. We also relax the no-overbidding assumption, and present bounds that are parameterized by the extent to which agents are willing to overbid.

Joint work with Brendan Lucier, Noam Nisan and Renato Paes Leme

Biography
Moshe Babaioff is a Researcher at Microsoft Research. His research interests lie in the intersection of Computer Science and Economics and he studies problems on the border of Computer Science Theory, Game Theory, and Microeconomic Theory. Much of his research focuses on the theoretical foundations of electronic markets. Prior to joining Microsoft Research at 2007, he spent two years as a post-doctoral scholar at the University of California, Berkeley. He received his PhD in Computer Science from the Hebrew University in Jerusalem at 2005, where he was advised by Professor Noam Nisan. He holds a M.Sc. in Computer Science and a B.A. in Mathematics and Computer Science, also from the Hebrew University.

Back to top

SPECIAL EVENT:  Reverse AGT workshop on Optimal Taxation
Monday, November 24
1:00 PM – 4:00 PM
Harvard University, 20 University Road, Room 646

Back to top

Where

Microsoft Research New England
First Floor Conference Center
One Memorial Drive, Cambridge, MA

Harvard University
Littauer Center, 3rd Floor Lounge
1805 Cambridge Street, Cambridge, MA

Arrival Guidance

Upon arrival at MSR, be prepared to show a picture ID and sign the Building Visitor Log when approaching the Lobby Floor Security Desk. Alert them to the name of the event you are attending and ask them to direct you to the appropriate floor. Typically the talks are located in the First Floor Conference Center, however sometimes the location may change.

If you have any questions or concerns, please send us an email.

Mailing List

To subscribe to the mailing list, send a blank message to this email address.

To unsubscribe, send a blank message to this email address.