The seminar is organized by Ozan Candogan (Chicago Booth), Vahideh Manshadi (Yale), and Fanyin Zheng (Columbia). Akshaya Suresh (Yale) serves as student organizer.
The seminar will be monthly on the first or second Fridays of the month at 1-2 pm ET (10-11 am PT).
Previous talks can also be viewed on our YouTube Channel.
If this seminar interests you and you would like to be notified of upcoming speakers, you can join our email list.
Dec 3 Panel discussion on "Matching on Transportation Platforms”
Panelists: Gad Allon (University of Pennsylvania), Saar Golde (Via), Tim Graciano (Convoy), David Shmoys (Cornell University)
2021 FALL Series
Oct 8 Gerard Cachon (University of Pennsylvania)
Title: Decentralized or Centralized Control of Online Service Platforms: Who Should Set Prices?
Abstract: Online service platforms that enable customers to connect with a large population of independent servers have been successfully developed in many sectors, including transportation, lodging, and delivery, among others. We ask a basic, yet fundamentally important, question - who should set the prices on the platform? The platform or the servers? Servers privately know their own cost and are small. Hence, while they can influence their share of demand, they cannot individually change the overall attractiveness of the platform to customers. These characteristics apply even in markets without a central platform (e.g., a fully decentralized platform enabled by blockchain-based smart contracts). We find that when the platform uses a simple commission contract to earn revenue, the price delegation decision depends on the importance of regulating server competition relative to the value of allowing servers to tailor their prices to their costs. However, merely adding appropriate linear quantity discounts or surcharges to the basic commission contract allows the platform and servers to enjoy the benefits of both centralized and decentralized control of prices.
Nov 5 Amin Saberi (Stanford University)
Title: Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities
Abstract: The rich literature on online Bayesian selection problems has long focused on so-called prophet inequalities, which compare the gain of an online algorithm to that of a "prophet" who knows the future. An equally natural, though significantly less well-studied benchmark is the optimum online algorithm, which may be omnipotent (i.e., computationally-unbounded) but not omniscient. What is the computational complexity of the optimum online? How well can a polynomial-time algorithm approximate it? We study the above questions for the online stochastic maximum-weight matching problem under vertex arrivals. For this problem, several 1/2-competitive algorithms are known against optimum offline. This is the best possible ratio for this problem, as it generalizes the original single-item prophet inequality problem. We present a polynomial-time algorithm that approximates the optimal online algorithm strictly better than the best-possible prophet inequality. In contrast, we show that it is PSPACE-hard to approximate this problem within some constant smaller than 1. Joint work with Christos Papadimitriou, Tristan Pollner, and David Wajc
Dec 3 Panel discussion on "Matching on Transportation Platforms”
Panelists: Gad Allon (University of Pennsylvania), Saar Golde (Via), Tim Graciano (Convoy), David Shmoys (Cornell University)
2021 SPRING Series
April 16 Retsef Levi (MIT)
Title: Food and Agriculture Supply Chain Analytics & Sensing : Managing Risks on Human Health
Abstract: Food and agriculture supply chains are essential to any society and economy, but at the same time pose significant risks to human health. In this talk, we will discuss how supply chain analytics and sensing, machine learning and modeling can inform regulatory policies and resource allocation to address and manage food adulteration and safety risks as well as zoonotic disease risks. Much of the talk will focus on a major multidisciplinary research effort to study risks related to economically motivated adulteration (EMA) of food in China, particularly ones originated from the upstream parts of the corresponding supply chains.
The talk is based on work done under a new collaborative project funded by the Walmart Foundation as well as work under a contract with the US FDA. It is joint work with multiple faculty and students at MIT and in Chinese universities.
April 30 Greg Lewis (Microsoft Research)
Title: Voluntary Disclosure and Personalized Pricing
Abstract: Central to privacy concerns is that firms may use consumer data to price discriminate. A common policy response is that consumers should be given control over which firms access their data and how. Since firms learn about a consumer’s preferences based on the data seen and the consumer’s disclosure choices, the equilibrium implications of consumer control are unclear. We study whether such measures improve consumer welfare in monopolistic and competitive markets. We find that consumer control can improve consumer welfare relative to both perfect price discrimination and no personalized pricing. First, consumers can use disclosure to amplify competitive forces. Second, consumers can disclose information to induce even a monopolist to lower prices. Whether consumer control improves welfare depends on the disclosure technology and market competitiveness. Simple disclosure technologies suffice in competitive markets. When facing a monopolist, a consumer needs partial disclosure possibilities to obtain any welfare gains. Joint work with Nageeb Ali and Shoshanna Vasserman.
May 14 David Parkes (Harvard University)
Title: Differentiable Economics
Abstract: In this talk I will introduce a research agenda that seeks to make use of differentiable representations of economic rules, together with suitable objectives, architectures, and constraints, to learn rules that approximately optimize various kinds of desiderata. I plan to illustrate this framework to the settings of revenue-optimal auction design, two-sided matching, and indirect mechanism design, and I will suggest some directions for future work. This talk represents work with various wonderful collaborators, including Gianluca Brero, Paul Duetting, Alon Eden, Zhe Feng, Matthias Gerstgrasser, Vincent Li, Harikrishna Narasimhan, Sai Srivatsa Ravindranath, and Duncan Rheingans-Yoo.
May 28 Dirk Bergemann (Yale University)
Title: Selling Impressions
Abstract: When publishers sell impressions, buyers have limited ability to target viewers without information from the publisher. By withholding information from buyers (or limiting their ability to make contingent bids), the publisher can pool impressions for a given buyer. Pooling impressions increases market thickness but reduces efficiency. We show that it is optimal for the publisher to pool high value impressions, in order to maintain market competition, but separate low value impressions, to maintain efficiency. This is joint work with Tibor Heumann (PUC Chile) and Stephen Morris (MIT).
2020 Winter Series
Mar 26 Gerard Cachon (University of Pennsylvania) [POSTPONED]
Mar 12 Garrett van Ryzin (Amazon)
Title: Autonomous Vehicle Market Design
Abstract: We develop an economic model of autonomous vehicle (AV) ride-hailing markets in which uncertain aggregate demand is served with a combination of a fixed fleet of AVs and an unlimited potential supply of human drivers (HVs). We analyze market outcomes under two dispatch platform designs (common platform vs. independent platforms) and two levels of AV competition (monopoly AV vs. competitive AV). A key result of our analysis is that the lower cost of AVs does not necessarily translate into lower prices; the price impact of AVs is ambiguous and depends critically on both the dispatch platform design and the level of competition. In the extreme case, we show if AVs and HVs operate on independent dispatch platforms and there is a monopoly AVs supplier, then prices are even higher than they are in a pure HV market. When AVs are introduced on a common dispatch platform, we show that whether the equilibrium price is reduced depends on the level of AV competition. If AVs are owned by a monopoly firm, then the equilibrium price is the same as in a pure HV market. In fact, the only market design that leads to unambiguously lower prices in all demand scenarios is when AVs and HVs operate on a common dispatch platform and the AV supply is competitive. Our results illustrate the critical role market design and competition plays in realizing potential welfare gains from AVs. Joint work with Zhen Lian, Cornell Johnson School.
Feb 26 Nikhil Agarwal (MIT)
Title: Choices and Outcomes in Assignment Mechanisms: The Allocation of Deceased Donor Kidneys
Abstract: While the mechanism design paradigm emphasizes notions of efficiency based on agent preferences, policymakers often focus on alternative objectives. School districts emphasize educational achievement, and transplantation communities focus on patient survival. It is unclear whether choice-based mechanisms perform well when assessed based on these outcomes. This paper evaluates the assignment mechanism for allocating deceased donor kidneys on the basis of patient life-years from transplantion (LYFT). We examine the role of choice in increasing LYFT and compare equilibrium assignments to benchmarks that remove choice. Our model combines choices and outcomes in order to study how selection induced in the mechanism affects LYFT. We show how to identify and estimate the model using quasi-experimental variation resulting from the mechanism. The estimates suggest that the design in use selects patients with better post-transplant survival prospects and matches them well, resulting in an average LYFT of 8.78, which is 0.92 years more than a random assignment. However, the aggregate LYFT can be increased to 13.84. Realizing the majority of the gains requires transplanting relatively healthy patients, who would have longer life expectancies even without a transplant. Therefore, a policymaker faces a dilemma between transplanting patients who are sicker and those for whom life will be extended the longest.
Feb 12 Eva Tardos (Cornell University)
Title: Stability and Learning in Strategic Queuing Systems
Abstract: Bounding the price of anarchy, which quantifies the damage to social welfare due to selfish behavior of the participants, has been an important area of research. In this paper, we study this phenomenon in the context of a game modeling queuing systems: routers compete for servers, where packets that do not get service will be resent at future rounds, resulting in a system where the number of packets at each round depends on the success of the routers in the previous rounds. We model this as an (infinitely) repeated game, where the system holds a state (number of packets held by each queue) that arises from the results of the previous round. We assume that routers satisfy the no-regret condition, e.g. they use learning strategies to identify the server where their packets get the best service. Classical work on repeated games makes the strong assumption that the subsequent rounds of the repeated games are independent (beyond the influence on learning from past history). The carryover effect caused by packets remaining in this system makes learning in our context result in a highly dependent random process. In joint work with Jason Gaitonde we analyze this random process and find that if the capacity of the servers is high enough to allow a centralized and knowledgeable scheduler to get all packets served even with double the packet arrival rate, and queues use no-regret learning algorithms, then the expected number of packets in the queues will remain bounded throughout time, assuming older packets have priority. This paper is the first to study the effect of selfish learning in a queuing system, where the learners compete for resources, but rounds are not all independent: the number of packets to be routed at each round depends on the success of the routers in the previous rounds. Studying this system also raises interesting questions on what is the right way to learn in systems with such carryover effects.
Jan 29 Eric Budish (University of Chicago)
Title: Quantifying the High-Frequency Trading "Arms Race": A Simple New Methodology and Estimates
Abstract: We use stock exchange message data to quantify the negative aspect of high-frequency trading, known as “latency arbitrage.” The key difference between message data and widely-familiar limit order book data is that message data contain attempts to trade or cancel that fail. This allows the researcher to observe both winners and losers in a race, whereas in limit order book data you cannot see the losers, so you cannot directly see the races. We find that latency-arbitrage races are very frequent (about one per minute per symbol for FTSE 100 stocks), extremely fast (the modal race lasts 5-10 millionths of a second), and account for a large portion of overall trading volume (about 20%). Race participation is concentrated, with the top 6 firms accounting for over 80% of all race wins and losses. Most races (about 90%) are won by an aggressive order as opposed to a cancel attempt; market participants outside the top 6 firms disproportionately provide the liquidity that gets taken in races (about 60%). Our main estimates suggest that eliminating latency arbitrage would reduce the market’s cost of liquidity by 17% and that the total sums at stake are on the order of $5 billion annually in global equity markets.
Jan 22 Asuman Ozdaglar (MIT)
Title: Analysis and Interventions in Large Network Games
Abstract: In many social and economic settings, decisions of individuals are affected by the actions of their friends, colleagues, and peers. Examples include adoption of new products and innovations, opinion formation and social learning, public good provision, financial exchanges and international trade. Network games have emerged as a powerful framework to study these settings with particular focus on how the underlying patterns of interactions, governed by a network, affect the economic outcomes. For tractability reasons, much of the work in this area studied games with special structure (e.g., quadratic cost functions, scalar non-negative strategies) or special properties (e.g., games of strategic complements or substitutes). In this talk, we first present a unified framework based on a variational inequality reformulation of the Nash equilibrium to study equilibrium properties of network games including existence and uniqueness, convergence of the best response dynamics and comparative statics. Our framework extends the literature in multiple dimensions, covering games with general strategic interactions and multidimensional and constrained strategy sets. In the second part of the talk, we will present a new class of infinite populations games, graphon games, that can capture heterogenous local interactions. We will show that equilibria in graphon games can approximate the equilibria of large network games sampled from the graphon. We also show that (under some regularity assumptions on the graphon), interventions based on graphon games can be designed using computationally tractable optimization problems and with much less information than the entire network structure.
Jan 15 Paul Milgrom (Stanford University)
Title: Investment Incentives in Near-Optimal Mechanisms
Abstract: In many real-world resource allocation problems, optimization is computationally intractable, so any practical allocation mechanism must be based on an approximation algorithm. We study investment incentives in strategy-proof mechanisms that use approximations. In sharp contrast with the Vickrey-Clark-Groves mechanism, for which individual returns on investments are aligned with social welfare, some algorithms that approximate efficient allocation arbitrarily well can nevertheless create misaligned investment incentives that lead to arbitrarily bad overall outcomes. However, if a near-efficient algorithm "excludes bossy negative externalities," then its outcomes remain near-efficient even after accounting for investments. A weakening of this "XBONE" condition is necessary and sufficient for the result. Joint work with Mohammad Akbarpour, Scott Duke Kominers, and Shengwu Li.
December 18 - Matthew Jackson (Stanford University)
Title: Learning through the Grapevine: The Impact of Noise and the Breadth and Depth of Social Networks
Abstract: We examine how well people learn when information is noisily relayed from person to person; and we study how communication platforms can improve learning without censoring or fact-checking messages. We analyze learning as a function of social network depth (how many times information is relayed) and breadth (the number of relay chains accessed). Noise builds up as depth increases, so learning requires greater breadth. In the presence of mutations (deliberate or random) and transmission failures of messages, we characterize sharp thresholds for breadths above which receivers learn fully and below which they learn nothing. When there is uncertainty about mutation rates, optimizing learning requires either capping depth, or if that is not possible, limiting breadth by capping the number of people to whom someone can forward a message. Limiting breadth cuts the number of messages received but also decreases the fraction originating further from the receiver, and so can increase the signal to noise ratio. Finally, we extend our model to study learning from message survival: e.g., people are more likely to pass messages with one conclusion than another. We find that as depth grows, all learning comes from either the total number of messages received or from the content of received messages, but the learner does not need to pay attention to both.
November 13 - Winners of the Michael H. Rothkopf Junior Researcher Paper Prize
Yannai A. Gonczarowski (Microsoft Research, Postdoctoral Researcher)
Title: Matching for the Israeli "Mechinot" Gap-Year Programs: Handling Rich Diversity Requirements
We describe our experience with designing and running a matching market for the Israeli "Mechinot" gap-year programs. The main conceptual challenge in the design of this market was the rich set of diversity considerations, which necessitated the development of an appropriate preference-specification language along with corresponding choice-function semantics, which we also theoretically analyze. Our contribution extends the existing toolbox for two-sided matching with soft constraints. This market has been run annually since 2018, and in 2020 matched 1,937 high-school seniors (out of a total of 6,118 candidates) to 42 different programs. Joint work with Lior Kovalio, Noam Nisan, Assaf Romm.
Irene Lo (Assistant Professor, Management Science and Engineering at Stanford University)
Title: The Cutoff Structure of Top Trading Cycles in School Choice
This paper develops a tractable theoretical framework for the Top Trading Cycles (TTC) mechanism for school choice that allows quantifying welfare and optimizing policy decisions. We compute welfare for TTC and Deferred Acceptance (DA) under different priority structures, and find that the choice of priorities can have larger welfare implications than the choice of mechanism. We solve for the welfare-maximizing distributions of school quality for parametrized economies, and find that optimal investment decisions can be very different under TTC and DA. Our framework relies on a novel characterization of the TTC assignment in terms of a cutoff for each pair of schools. These cutoffs parallel prices in competitive equilibrium, with students' priorities serving the role of endowments. We show that these cutoffs can be computed directly from the distribution of preferences and priorities in a continuum model, and derive closed-form solutions and comparative statics for parameterized settings. The TTC cutoffs clarify the role of priorities in determining the TTC assignment, but also demonstrate that TTC is more complicated than DA. Joint work with Jacob Leshno.
Scott Rodilitz (PhD Student in Operations, Yale School of Management)
Title: Online Policies for Efficient Volunteer Crowdsourcing
Nonprofit crowdsourcing platforms encourage volunteers to complete tasks by using nudging mechanisms to notify a subset of volunteers with the hope that at least one of them responds positively. However, since excessive notifications may reduce volunteer engagement, the platform faces a trade-off between notifying more volunteers for the current task and saving them for future ones. Motivated by these applications, we introduce the online volunteer notification problem and develop two online randomized policies that achieve constant-factor guarantees. Further we demonstrate the effectiveness of our policies by testing them on data from a volunteer-based food recovery platform. Joint work with Vahideh Manshadi.
October 30 - Jon Kleinberg (Cornell University)
Title: Fairness and Bias in Algorithmic Decision-Making
Abstract: As algorithms trained via machine learning are increasingly used as a component of screening decisions in areas such as hiring, lending, and education, discussion in the public sphere has turned to the question of what it means for algorithmic classification to be fair to different groups. We consider several of the key fairness conditions that lie at the heart of these debates, and discuss recent research establishing inherent trade-offs between these conditions. We also explore how the complexity of a classification rule interacts with its fairness properties, showing how natural ways of approximating a classifier via a simpler rule can act in conflict with fairness goals. The talk will be based on joint work with Jens Ludwig, Sendhil Mullainathan, Manish Raghavan, and Cass Sunstein.
October 16 - John Birge (University of Chicago)
Title: Increasing Efficiency in Electricity Market Auctions
Abstract: Electricity markets in much of the world are organized with day-ahead and real-time components for energy and in some place regular auctions of financial transmission rights that depend on the energy prices. The form of these organizations leads to a degree of inherent efficiency and instability due to misalignments of incentives. This talk will describe potential mechanisms for alleviating these inefficiencies including the inclusion of some form of stochastic clearing, flexibility in the forms of bids, and penalties for inefficiencies caused by speculative bidders.
October 02 - Alvin Roth (Stanford University)
Title: Kidney Exchange: an Operations Perspective
Abstract: Many patients in need of a kidney transplant have a willing but incompatible (or poorly matched) living donor. Kidney exchange programs arrange exchanges among such patient-donor pairs, in cycles and chains of exchange, so each patient receives a compatible kidney. Kidney exchange has become a standard form of transplantation in the United States and a few other countries, in large part because of continued attention to the operational details that arose as obstacles were overcome and new obstacles became relevant. We review some of the key operational issues in the design of successful kidney exchange programs. Kidney exchange has yet to reach its full potential, and the paper further describes some open questions that we hope will continue to attract attention from researchers interested in the operational aspects of dynamic exchange.
We collaborate with the Games, Decisions, & Networks online seminar series. This might be a particularly interesting seminar for those of you interested in the foundations and applications of game theory, decision theory, and network theory. Please note that both seminars take place on Fridays, but on alternating weeks.