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 brief Q&A. The seminar is aimed at an audience of theory researchers and students. We welcome members of the local academic community to attend.
Optimal Allocation of Public Services Without Monetary Transfers or Costly Signals
Itai Ashlagi, MIT
Wednesday, Dec 4
2:00 PM – 3:30 PM
We study the social planner's problem of designing a mechanism to optimally allocate a set of public services to a set of heterogeneous agents with private utilities, without the ability to differentiate agents by charging prices or requiring costly effort. This is motivated by the 2012-2013 Boston school choice reform, in which social planners had to design a school choice lottery to allocate public school seats among families from various neighborhoods, in order to balance efficiency, equity, and busing costs. We consider two types of mechanisms: cardinal mechanisms, which can use any information, and ordinal mechanisms, which can only use agents' rankings of preferences but not preference intensities. We show that under assumptions of ``soft capacity limits'' and ``Pareto optimality of interim allocation rules,'' any valid interim cardinal allocation rule is ``type-specific-pricing,'' in which agents are given equal budgets of ``virtual money'' and buy the optimal probabilistic bundle of services given type-specific prices for each service. Under similar assumptions, any valid ordinal allocation rule is ``lottery-plus-cutoff,'' in which agents are given i.i.d. lottery numbers and services post type-specific lottery-cutoffs; agents get their most preferred service for which they do not exceed the cutoff. Given additional assumptions on the public objective function and allowing for linear budget constraints, we present an algorithm to efficiently compute the optimal ordinal mechanism. We apply this to real data from Boston and for each of the main plans proposed during the 2012-2013 reform, we compute a corresponding ``optimal'' plan that uses the same transportation budget but optimizes for efficiency and equity. We compare the plans and discuss potential policy insights.
Joint work with Peng shi
Itai Ashlagi is an Assistant Professor of Operations Management at the Sloan School of Management. He is interested in game theory, mechanism and market design. He is the recipient of the outstanding paper award in the ACM conference of Electronic Commerce 2009. He received the Tarasaki award for novel developments in kidney exchange and the Services and Needs best paper award at INFORMS 2013. Before coming to MIT he spent two years as a postdoctoral researcher at Harvard Business School. Itai holds a BA in mathematics and computer science from Haifa University, and an MSc and PhD in operations research from Technion-Israel Institute of Technology.
The Computational Hardness of Pricing Compound Options
It is generally assumed that you can make a financial asset out of any underlying event or combination thereof, and then sell a security. We show that while this is theoretically true from the financial engineering perspective, compound securities might be intractable to price. Even given no information asymmetries, or adversarial sellers, it might be computationally intractable to put a value on these, and the associated computational complexity might afford an advantage to the party with more compute power. We prove that the problem of pricing an option on a single security with unbounded compounding is PSPACE hard, even when the behavior of the underlying security is computationally (poly-time) tractable. We also prove some hardness results in a more realistic bounded-compounding model, when the underlying asset is given by an oracle.
Joint work with Kanika Pasricha
Mark Braverman is an assistant professor of computer science at Princeton University, where he has been on the faculty since 2011. He received his PhD in 2008 from the University of Toronto under the supervision of Stephen Cook. Prior to joining Princeton he spent two years as a postdoc at Microsoft Research New England and a year as a faculty member at the University of Toronto. Braverman's interests include complexity theory, information theory, the theory of computation in dynamical systems, algorithms, and applications of computer science and game theory in healthcare and medicine.
His recent work developed and expanded the connections between information theory and computational complexity, by extending the reach of Shannon's information theory to interactive computation. He is a recipient of the Sloan fellowship, the NSF CAREER award, the Turing Centenary Fellowship, and the Packard Fellowship in Science and Engineering.
An Optimization Approach to Mechanism Design
Costis Daskalakis, MIT
Wednesday, Nov 13
2:00 PM – 3:30 PM
I will present an optimization framework based on optimal transport theory characterizing the structure of revenue-optimal mechanisms in single-bidder multi-item settings. Our framework provides closed-form descriptions of mechanisms, generalizes Myerson's celebrated single-item auction, and exhibits simple settings with very rich structure in the optimal mechanism. This part of the talk is based on work with Alan Deckelbaum and Christos Tzamos.
For the second part of the talk, which will be algorithmic, I will revisit the question posed by Nisan and Ronen in the birth of algorithmic mechanism design: How much harder is optimizing an objective over inputs that are furnished by rational agents compared to when the inputs are known? I will present a computationally efficient reduction from mechanism design (i.e. optimizing an arbitrary objective over rational inputs) to algorithm design (i.e. optimizing the same objective over known inputs) in general Bayesian settings. I will discuss applications of this framework to designing optimal mechanisms for max-min fairness and makespan. This part of the talk is based on work with Yang Cai and Matt Weinberg.
No knowledge of mechanism design will be assumed.
Constantinos Daskalakis is the x-window consortium associate professor of computer science at MIT. He holds a diploma in electrical and computer engineering from the National Technical University of Athens, and a Ph.D. in electrical engineering and computer sciences from UC-Berkeley. His research interests lie in theoretical computer science and applied probability with a focus on the computational aspects of the Internet, online markets and social networks. Daskalakis has been honored with the 2007 Microsoft Graduate Research Fellowship, the 2008 ACM Doctoral Dissertation Award, the Game Theory and Computer Science Prize from the Game Theory Society, the 2010 Sloan Fellowship in Computer Science, the 2011 SIAM Outstanding Paper Prize, the 2011 Ruth and Joel Spira Award for Distinguished Teaching, and the 2012 Microsoft Research Faculty Fellowship.
The Power of Local Information in Social Networks
Michael Brautbar, MIT
Wednesday, Nov 6
2:00 PM – 3:30 PM
We study the power of local information algorithms for optimization problems on social networks. We focus on sequential algorithms for which the network topology is initially unknown and is revealed only within a local neighborhood of vertices that have been irrevocably added to the output set. The distinguishing feature of this setting is that locality is necessitated by constraints on the network information visible to the algorithm, rather than being desirable for reasons of efficiency or parallelizability.
We study a range of problems under this model of algorithms with local information. We first consider the case in which the underlying graph is a preferential attachment network. We show that one can find the node of maximum degree in the network in a polylogarithmic number of steps, using an opportunistic algorithm that repeatedly queries the visible node of maximum degree. This addresses a decade-old open question of Bollobas and Riordan. In contrast, local information algorithms require a linear number of queries to solve the problem on arbitrary networks.
Motivated by problems faced by advertisers in online networks, we also consider network coverage problems such as finding a minimum dominating set. For this optimization problem we show that, if each node added to the output set reveals sufficient information about the set's neighborhood, then it is possible to design randomized algorithms for general networks that nearly match the best approximations possible even with full access to the graph structure. We show that this level of visibility is necessary.
We conclude that a network provider's decision of how much structure to make visible to its users can have a significant effect on a user's ability to interact strategically with the network.
Michael (Mickey) Brautbar is currently a postdoctoral associate in MIT, affiliated with LIDS, hosted by Daron Acemoglu and Asu Ozdaglar. His main research interests lie in the theory of social and economic networks and in the algorithmic aspects of game theory. Before coming to MIT, he completed his PHD degree in computer and information science from the University of Pennsylvania, where he was advised by Michael Kearns. In the past he obtained B.Sc. and M.Sc. degrees in computer science (both summa cum laude) from the Hebrew University of Jerusalem.
The Demise of Walk Zones in Boston: Priorities vs. Precedence in School Choice
Scott Kominers, Harvard
Wednesday, Oct 30
2:00 PM – 3:30 PM
School choice plans in many cities grant students higher priority for some (but not all) seats at their neighborhood schools. This paper demonstrates how the precedence order, i.e. the order in which different types of seats are filed by applicants, has quantitative effects on distributional objectives comparable to priorities in the deferred acceptance algorithm. While Boston's school choice plan gives priority to neighborhood applicants for half of each school's seats, the intended effect of this policy is lost because of the precedence order. Despite widely held impressions about the importance of neighborhood priority, the outcome of Boston's implementation of a 50-50 school split is nearly identical to a system without neighborhood priority. We formally establish that either increasing the number of neighborhood priority seats or lowering the precedence order positions of neighborhood seats at a school have the same effect: an increase in the number of neighborhood students assigned to the school. We then show that in Boston a reversal of precedence with no change in priorities covers almost three-quarters of the range between 0% and 100% neighborhood priority. Therefore, decisions about precedence are inseparable from decisions about priorities. Transparency about these issues---in particular, how precedence unintentionally undermined neighborhood priority---led to the abandonment of neighborhood priority in Boston in 2013.
Scott Duke Kominers is a Junior Fellow at the Harvard Society of Fellows, a Research Scientist at the Harvard Program for Evolutionary Dynamics, and an Associate of the Harvard Center for Research on Computation and Society. From 2011-2013, he was the inaugural Research Scholar at the Becker Friedman Institute for Research in Economics at the University of Chicago.
Kominers received his A.B. in Mathematics and Ph.D. in Business Economics from Harvard University, in 2009 and 2011, respectively. His research focuses on market design and its interactions with law and computer science. His specific research interests include matching theory, eminent domain, law and economics, and quadratic form representation theory.
Optimal Competitive Auctions
Nick Gravin, MSR New England
Wednesday, Oct 23
2:00 PM – 3:30 PM
In an effort to make a progress in worst-case mechanism design a big amount of work has been devoted to the following simple scenario: a single-round, sealed-bid auction for an item in unlimited supply (usually referred to as a digital good). A competitive auction must be truthful (i.e., encourages buyers to bid truthfully) and on every input it must generate profit within a constant factor of a certain benchmark. The profit of the optimal single sale price is commonly used as a benchmark in the context of digital goods auctions.
I'll present a few examples of competitive auctions as well as our work in progress with Ning Chen and Pinyan Lu. The optimal competitive ratio is known to be at least 2.42 due to Goldberg, Hartline, Karlin, and Saks (2004), who also conjectured that this lower bound must be tight. I will describe necessary and sufficient conditions for any benchmark to admit a truthful auction that raises at least 100% revenue of the benchmark's value on every input. As a corollary we will see that the conjectured competitive ratio is indeed optimal. As another application we will see that the optimal auction has a competitive ratio of 1.25 for one more economically meaningful benchmark given by the revenue of the best Vickrey auction with a limited supply.
Nick Gravin is a Postdoc with us at Microsoft Research New England. Nick has two PhD degrees: one from Steklov Institute of Mathematics in Saint-Petersburg and another from Nanyang Technological University in Singapore. His research interests are twofold. In Mathematics he works in graph theory, convex and discrete geometry. In Theoretical Computer Science he is particularly interested in Algorithmic Mechanism Design and Equilibria computations.
Emissaries: How Bridges Affect Network Centrality
Ben Golub, Harvard
Wednesday, Oct 16
2:00 PM – 3:30 PM
Consider two finite-state irreducible Markov chains. Each chain has a stationary distribution, which can be interpreted as measuring the 'importance' or 'centrality' of various states in a corresponding weighted directed graph of transitions. I'll also mention some quite different applications in which stationary distributions (or, equivalently, eigenvector centrality measures) describe the 'importance' of nodes in an economic network.
Suppose we connect our two Markov chains by introducing a bridge -- new transitions between two emissary states, one from each chain. How much of the stationary mass does each constituent chain get after the merger? We give an explicit formula in terms of the properties of the bridge: how central the emissaries are in their own chains, and how much weight they place on each other. Arbitrarily "small" bridges can have arbitrarily large effects on the post-merger stationary distribution, and a chain keeps more of the mass if its emissary was less central pre-merger. The proof, which is short enough to give in full, uses the characterization of the stationary distribution in terms of expected visits during sojourns in the Markov chain.
Applications include understanding why the small details of the present legislative standoff matter a lot for the world, and understanding how 'social power' is redistributed after two societies come into contact.
Benjamin Golub is currently a Junior Fellow at the Harvard Society of Fellows, and will begin an appointment as an Assistant Professor at the Harvard Department of Economics in July 2015. He received a Ph.D. in Economics from the Stanford Graduate School of Business in 2012, and a B.S. in Mathematics from the California Institute of Technology in 2007. Ben’s research focuses on microeconomic theory, and in particular, social and economic networks: how these networks form when agents invest strategically in relationships, how information is transmitted through them, and how they mediate processes such as group cooperation. Applications of his research include measuring social segregation and understanding its consequences for polarization of beliefs or behaviors.
Two(!) Good To Be True
Sergiu Hart, Hebrew University of Jerusalem
Monday, Oct 7
2:00 PM – 3:30 PM
How to sell goods optimally? While the mechanism-design literature has solved this problem neatly when there is only one good, the multiple goods case turns out to be extremely difficult, mathematically and conceptually. Much of what is true for one good does not extend to multiple goods. We will try to explain the difficulties, show what can go wrong, and then present some universal approximation results. The talk is essentially self-contained; no background in mechanism design is necessary.
Sergiu Hart is the Kusiel-Vorreuter University Professor, Professor of Mathematics, and Professor of Economics, at the Hebrew University of Jerusalem. From 1991 to 1998 he was the founding director of the highly reputed Center for the Study of Rationality. Besides game theory and economic theory, he has contributions in mathematics, computer science, probability and statistics. He is known for studies of strategic foundations of cooperation; strategic use of information in long-term interactions ("repeated games"); adaptive and evolutionary dynamics, particularly with boundedly rational agents; perfect economic competition and its relations to models of fair distribution; and riskiness. He is Fellow of the Econometric Society and Member of the Israel Academy of Sciences and Humanities. In 1998 he received the Rothschild Prize. He served as president of the Israel Mathematical Union in 2005-2006, and as president of the Game Theory Society in 2008-2010.
On the Value of using Group Discounts under Price Competition
Reshef Meir, Harvard
Wednesday, Oct 2
2:00 PM – 3:30 PM
The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price, either as a monopolist or when competing with other vendors. When vendors have uncertainty about buyers' valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyers' types are i.i.d. and that other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyers are not i.i.d., or other vendors post discount schedules, then posting a schedule may yield higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors minimize their maximum regret over all type realizations.
Reshef Meir is a post-doctoral fellow at Harvard SEAS and at the Center for Research on Computation and Society. He was a PhD student at the Hebrew University in Jerusalem and an intern in MSR in Israel. He is mainly interested in the design and analysis of mechanisms that encourage self-interested agents to cooperate.
Predictability and Power in Legislative Bargaining
Nageeb Ali, University of California-San Diego
Wednesday, Sept 25
2:00 PM – 3:30 PM
This paper examines the effect of the predictability of recognition processes on the concentration of political power in legislative bargaining. For a broad class of legislative bargaining games, we identify a mild predictability condition on the recognition rule, requiring an ability to rule out some minimum number of legislators as the next proposer, under which Markovian equilibria deliver all economic surplus to the first proposer. That result holds irrespective of whether legislators are patient or impatient. When legislators can be nearly certain that the next proposer belongs to a class of the requisite size, the first proposer receives nearly all of the surplus.
Nageeb Ali is an assistant professor of economics at UCSD, and is visiting Microsoft Research for the month of September as a Consulting Researcher. His focus is microeconomic theory, and his interests range from multilateral bargaining to studying self-control problems to the role of networks in contract enforcement.
Repeated Population Games of Incomplete Information I: Compressed Nash Equilibrium
Ehud Kalai, MSR New England
Wednesday, Sept 18
2:00 PM – 3:30 PM
In equilibrium of large (many players) Bayesian games, stability properties fail when player types are interdependent. But when the game is played repeatedly, the players “learn to be independent” and stability is restored.
To conduct robust tractable analysis of such games, we develop a new equilibrium concept called compressed equilibrium. Defined for finite population games, compressed equilibrium is significantly easier to compute, is independent of the number of players and repetitions of the game, and it becomes an ε-Nash equilibrium as the number of players increases.
Ehud Kalai works in game theory and its interface with economics, computer science and other areas. He is a Principal Researcher at Microsoft Research New England and the James J O'Connor Distinguished Professor of Decision and Game Sciences at Northwestern University, where is the director of the Center for Game Theory and Economic Behavior. He holds an AB (Cornell, 1972), a PhD (UC Berkeley, 1967) and an Honorary Doctorate (University of Paris 2010) in mathematics. Kalai is the founding Editor of Games and Economic Behavior, and a co-founder and past President of the Game Theory Society. He is a Fellow of the American Academy of Arts and Sciences and of the Econometric Society.
Microsoft Research New England
First Floor Conference Center
One Memorial Drive, Cambridge, MA
Upon arrival, 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.