Thursday, May 30, 2024

Sigecom Test of Time Award 2024 for AdWords and generalized online matching by Mehta, Saberi, Vazirani, and Vazirani

 The SIGecom Test of Time Award recognizes the author or authors of an influential paper or series of papers published between ten and twenty-five years ago that has significantly impacted research or applications exemplifying the interplay of economics and computation. More details and nomination procedure…

The Test of Time Award Winners for 2024 are Aranyak MehtaAmin SaberiUmesh Vazirani, and Vijay Vazirani  

They are cited for "introducing and solving a model of online matching with budgets that has seen many practical applications to online markets and broad and continuing impact in the literature."

in their paper

AdWords and generalized online matching, Journal of the ACM 54(5), 2007, Article 22

Abstract: How does a search engine company decide what ads to display with each query so as to maximize its revenue? This turns out to be a generalization of the online bipartite matching problem. We introduce the notion of a trade-off revealing LP and use it to derive an optimal algorithm achieving a competitive ratio of 1−1/e for this problem.

From the introduction:

"Internet search engine companies, such as Google, Yahoo and MSN, have revolutionized not only the use of the Internet by individuals but also the way businesses advertise to consumers. Typical search engine queries are short and reveal a great deal of information about user preferences. This gives search engine companies a unique opportunity to display highly targeted ads to the user.

"The online advertising mechanisms used by search engines, including Google’s AdWords, are essentially large auctions where businesses place bids for individual keywords, together with limits specifying their maximum daily budget. The search engine company earns revenue when it displays their ads in response to a relevant search query (if the user actually clicks on the ad). Indeed, most of the revenues of search engine companies are derived in this manner [Battelle 2005]. One factor in their dramatic success is that, unlike conventional advertising, search engine companies are able to cater to low-budget advertisers (who occupy the fat tail of the power law distribution governing advertising budgets of companies and organizations).

"The following computational problem, which we call the adwords problem, is a formalization of a question posed to us by M. Henzinger: There are (private communication, 2004). N bidders, each with a specified daily budget bi . Q is a set of query words. Each bidder i specifies a bid ciq for query word q ∈ Q. A sequence q1q2 · · · q M of query words q j ∈ Q arrive online during the day, and each query q j must be assigned to some bidder i (for a revenue of ciq j ). The objective is to maximize the total revenue at the end of the day while respecting the daily budgets of the bidders.

"In this article, we present a deterministic algorithm achieving a competitive ratio of 1 − 1/e for this problem, under the assumption that bids are small compared to budgets."


Last year's award:

Monday, April 3, 2023

Test of Time Award 2023 to Immorlica & Mahdian, and Ashlagi, Kanoria & Leshno


"Past and Present Members of the Test of Time Award Committee: Yeon-Koo Che, Yiling Chen, Nikhil Devanur, Joan Feigenbaum, Jason Hartline, Bobby Kleinberg, Paul Milgrom, Noam Nisan, Asu Ozdaglar, David Parkes, David Pennock, Alvin Roth, Tim Roughgarden, Larry Samuelson, Tuomas Sandholm, Yoav Shoham, Éva Tardos, Moshe Tennenholtz"

Wednesday, May 29, 2024

Marijuana policy and use in the U.S., 1979-2022, by Jonathan Caulkins, in Addiction

 Here's a paper forthcoming in the journal Addiction:

Changes in self-reported cannabis use in the United States from 1979 to 2022, by Jonathan P. Caulkins, published online 22 May 2024, 


Background and aims: Multiple countries are considering revising cannabis policies. This study aimed to measure long-term trends in cannabis use in the United States and compare them with alcohol use.

Design and setting: Secondary analysis of United States general population survey data.

Participants: The national surveys had a total of 1 641 041 participants across 27 surveys from 1979 to 2022.

Measurements: Rates of use reported to the US National Survey on Drug Use and Health and its predecessors are described, as are trends in days of use reported. Four milepost years are contrasted: 1979 (first available data and end of relatively liberal policies of the 1970s), 1992 (end of 12 years of conservative Reagan-Bush era policies), 2008 (last year before the Justice Department signaled explicit federal non-interference with state-level legalizations) and 2022 (most recent data available).

Findings: Reported cannabis use declined to a nadir in 1992, with partial recovery through 2008, and substantial increases since then, particularly for measures of more intensive use. Between 2008 and 2022, the per capita rate of reporting past-year use increased by 120%, and days of use reported per capita increased by 218% (in absolute terms from the annual equivalent of 2.3 to 8.1 billion days per year). From 1992 to 2022, there was a 15-fold increase in the per capita rate of reporting daily or near daily use. Whereas the 1992 survey recorded 10 times as many daily or near daily alcohol as cannabis users (8.9 vs. 0.9 M), the 2022 survey, for the first time, recorded more daily and near daily users of cannabis than alcohol (17.7 vs. 14.7 M). Far more people drink, but high-frequency drinking is less common. In 2022, the median drinker reported drinking on 4–5 days in the past month, versus 15–16 days in the past month for cannabis. In 2022, past-month cannabis consumers were almost four times as likely to report daily or near daily use (42.3% vs. 10.9%) and 7.4 times more likely to report daily use (28.2% vs. 3.8%).

ConclusionsLong-term trends in cannabis use in the United States parallel corresponding changes in cannabis policy, with declines during periods of greater restriction and growth during periods of policy liberalization. A growing share of cannabis consumers report daily or near daily use, and their numbers now exceed the number of daily and near daily drinkers."

Daily and Near Daily (DND) use


"That is still not as high as for cigarettes. The 2022 NSDUH survey finds that 58.7% of PM ["Past Month"] cigarette smokers smoked ‘daily’—defined as ‘smoked one or more packs of cigarettes per day’ [8]. Therefore, there are more daily cigarette smokers than DND PM marijuana users (24.1 vs 17.7 million). 3 Still, patterns of marijuana consumption have shifted from being like alcohol to being closer to cigarette use. It is also no longer a young person's drug. In 2022, people 35 and older accounted for (slightly) more days of use than did those under the age of 35."

Tuesday, May 28, 2024

Gonzalo Arrieta defends his dissertation

Gonzalo Arrieta defended his dissertation last week.

Here's his job market paper:

Procedural Decision-Making In The Face OfComplexity by Gonzalo Arrieta and Kirby Nielsen

Abstract: A large body of work documents that complexity affects individuals’ choices, but the literature has remained mostly agnostic about why. We provide direct evidence that individuals use different choice processes for complex and simple decisions. We hypothesize that individuals resort to “procedures”—cognitively simpler choice processes that we characterize as being easier to describe to another person—as the complexity of the decision environment increases. We test our hypothesis using two experiments, one with choices over lotteries and one with choices over charities. We exogenously vary the complexity of the decision environment and measure the describability of choice processes by how well another individual can replicate the decision-maker’s choices given the decision-maker’s description of how they chose. We find strong support for our hypothesis: Both of our experiments show that individuals’ choice processes are more describable in complex choice environments, which we interpret as evidence that decision-making becomes more procedural as complexity increases. We show that procedural decision-makers choose more consistently and exhibit fewer dominance violations, though we remain agnostic about the causal effect of procedures on decision quality. Additional secondary evidence suggests that procedural decision-making is a choice simplification that reduces the cognitive costs of decision-making."

Another of his papers is a really creative investigation of human welfare:

Abstract: The dominant approach to welfare is based on revealed preferences and thus is restricted to settings where the individual knows their preferences have been fulfilled. We use a choosing-for-others framework to experimentally study welfare when what the individual believes to be true differs from what is actually true. About 42% of participants see welfare as independent of beliefs; 22% see welfare as only depending on beliefs; and 29% see a lower, but still positive, welfare effect when beliefs are fixed. Furthermore, the average participant values accurate beliefs. Our results suggest most people support the idea that welfare goes beyond awareness, which can inform media regulation, informational policies, and government communication.


Here's a figure from the instructions about the creation of "real" and "fake" inscribed copies of books. A third party judged the welfare to the recipient

"Our altruistically revealed preference paradigm consists of asking surrogate participants to trade off a monetary bonus given to the Receiver, and the Receiver getting the books with the original notes over those with the fake notes. The bonus amount is a surprise to the Receiver to minimize concerns that they use it to deduce which books they got (i.e., to maintain obliviousness). Our three requirements allow us to interpret the bonus amount that leaves participants indifferent between giving the original and fake notes as a measure of the change in the Receiver’s welfare. As a benchmark, we also elicit the welfare effect when the Receiver does learn which notes they get."
Welcome to the club, Gonzalo.

Monday, May 27, 2024

Matching for love or profit at Stanford

 Looking for a date, a marriage, a business partner?  Stanford might have the right app for you.

Here's the story from the Stanford Daily

Match, Marry, Capitalize? A catalog of Stanford’s matchmaking services, By Oriana Riley

"Here’s how matchmakers have attempted to help the Stanford community find love, friendships and business partners. 

Marriage Pact 

Perhaps the most famous Stanford matchmaking service, Marriage Pact, originated as a final project for a Stanford economics project. The annual service, which uses a survey to match compatible individuals for friendships and romantic relationships, has expanded to 88 campuses and more than 400,000 people.


"Founder Pact 

"Founder Pact presented an opportunity for students to try their hand not at love, but entrepreneurship. Founder Pact, created by the Business Association of Stanford Entrepreneurial Students (BASES), aimed to match entrepreneurs to realize their business ideas together. 

"The Founder Pact form, however, is now closed. 


"A baby bird on the Stanford dating scene is Wing, announced to Stanford students via email on April 18. According to the email, Wing is built on the idea of “set[ting] up your friends.” 

Sunday, May 26, 2024

Recent papers on matching: May GEB

 The May issue of Games and Economic Behavior has several papers on matching that caught my eye:

Games and Economic Behavior, Volume 145, May 2024

Strong core and Pareto-optimality in the multiple partners matching problem under lexicographic preference domains, by Péter Biró and Gergely Csáji

Abstract: We study strong core and Pareto-optimal solutions for multiple partners matching problem under lexicographic preference domains from a computational point of view. The restriction to the two-sided case is called stable many-to-many matching problem and the general one-sided case is called stable fixtures problem. We provide an example to show that the strong core can be empty even for many-to-many problems, and that deciding the non-emptiness of the strong core is NP-hard. On the positive side, we give efficient algorithms for finding a near feasible strong core solution and for finding a fractional matching in the strong core of fractional matchings. In contrast with the NP-hardness result for the stable fixtures problem, we show that finding a maximum size matching that is Pareto-optimal can be done efficiently for many-to-many problems. Finally, we show that for reverse-lexicographic preferences the strong core is always non-empty in the many-to-many case.

Bayesian stable states, by Yi-Chun Chen and Gaoji Hu 

Abstract: This paper extends the Bayesian stability notion of Liu (2020) to define the Bayesian stability of a market state, which consists of a matching outcome and an information structure. The information structure can be arbitrarily heterogeneous and can accommodate learning among agents. We first establish that a Bayesian stable matching function of Liu (2020) can be recast as Bayesian stable market states with homogeneous information. We then illustrate the usefulness of such an extension by (i) refining Liu's Bayesian efficiency notion to define the Bayesian efficiency of a market state and (ii) generalizing his result—that Bayesian stable matching functions are Bayesian efficient—to an analogous one for market states. More importantly, we show that (iii) a decentralized matching process converges to a Bayesian stable market state and thereby offer a decentralized foundation for Liu's Bayesian stable matching function.

Efficient matching under general constraints  by Kenzo Imamura, Yasushi Kawase

Abstract: We study indivisible goods allocation problems under constraints and provide algorithms to check whether a given matching is Pareto efficient. We first show that the serial dictatorship algorithm can be used to check Pareto efficiency if the constraints are matroid. To prove this, we develop a generalized top trading cycles algorithm. Moreover, we show that the matroid structure is necessary for obtaining all Pareto efficient matchings by the serial dictatorship algorithm. Second, we provide an extension of the serial dictatorship algorithm to check Pareto efficiency under general constraints. As an application of our results to prioritized allocations, we discuss Pareto improving the deferred acceptance algorithm.

Saturday, May 25, 2024

Size is important in liver exchange

 Liver exchange has a lot in common with kidney exchange, in the sense that the issues involved in forming cycles and chains once you know which donors are compatible with which patients are very similar.  But a big difference is what constitutes a compatible donor: for livers, size (of the donor, and the donor liver) is very important, sensitively so.

Here's a paper forthcoming in the American Journal of Transplantation, by a team of transplant physicians and economists (with kidney exchange experience), on the importance of size.

"Enhanced Role of Multi-Pair Donor Swaps in Response to Size Incompatibility: The First Two 5-Way and the First 6-Way Liver Paired Exchanges" by Sezai Yilmaz, MD, FACS, Tayfun Sönmez, PhD, M. Utku Ünver, PhD, Volkan Ince, MD, Sami Akbulut, MD, PhD, FACS, Kemal Baris Sarici, MD, and Burak Isik, MD, American Journal of Transplantation, Brief communication, in press.

Abstract: A significant portion of liver transplantations in many countries is conducted via living-donor liver transplantation (LDLT). However, numerous potential donors are unable to donate to their intended recipients due to factors such as blood-type incompatibility or size incompatibility. Despite this, an incompatible donor for one recipient may still be a viable donor for another patient. In recent decades, several transplant centers have introduced liver paired exchange (LPE) programs, facilitating donor exchanges between patients and their incompatible donors, thereby enabling compatible transplants. Initially, LPE programs in Asia primarily involved ABO-i pairs, resulting in 2-way exchanges mainly between blood-type A and B recipients and donors. This practice has led to a modest 1-2% increase in LDLTs at some centers. Incorporating size incompatibility alongside blood-type incompatibility further enhances the efficacy and significance of multiple-pair LPEs. Launched in July 2022, a single-center LPE program established at Inönü University Liver Transplant Institute in Malatya, Türkiye, has conducted thirteen 2-way, nine 3-way, four 4-way, two 5-way, and one 6-way LPEs until February 2024. In 2023 alone, this program facilitated 64 LDLTs, constituting 27.7% of the total 231 LDLTs performed. This paper presents the world's first two 5-way LPEs and the first 6-way LPE.


Another (not entirely unrelated) domain in which size is important, and exchange involves many pairs, involves the exchange of shells among hermit crabs. See these earlier posts (which included this short video):


Saturday, July 21, 2012

Friday, May 24, 2024

NRMP Board of Directors (2020-2024), and a 40th anniversary

 This bit of glass marks the end of my term on the National Resident Matching Program (NRMP) Board of Directors.

One of the issues that consumed a lot of attention during my term is discussed in this post:

Friday, April 21, 2023

Transition from medical school to residency: defending the parts that work well (namely the NRMP Resident Match)

And here are all my posts about residents and fellowsgoing back to the beginning of this blog in 2008. (It's been interesting watching medical specialties begin to develop signaling in ways  reminiscent of signaling in the Economics job market, to deal with congestion of interviews and applications.*)

My first paper dealing explicitly with The Match suddenly seems to have been published 40 years ago:
Roth, A.E. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory", Journal of Political Economy, Vol. 92, 1984, 991‑1016. 

And the main report (with Elliott Peranson) of our redesign of The Match is now a quarter of a century old:
Roth, A.E. and E. Peranson, "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design,” American Economic Review, 89, 4, September, 1999, 748-780.

*See yesterday's post for some discussion of market design interventions in job markets.