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

**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

**Utku Ünver, Boston College**

Monday, December 1

4:00 PM – 5:30 PM

Harvard University, Littauer Center, 3rd Floor Lounge**Giorgos Zervas****, Boston University**

Monday, December 8

4:00 PM – 5:30 PM

Microsoft Research, One Memorial Drive (1st Floor)

Back to top

# Past Speakers

**Bidding Games, Bargaining and Efficient Allocations**

**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.

**Incentivizing Exploration**

**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.

**Simple Mechanisms with Simple Strategies**

**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.

**Social Learning with Costly Search and Social Advertising**

**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.

**Risk Dynamics in Trade Networks**

**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.

**On the Efficiency of the Walrasian Mechanism**

**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.

# 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.