Professor Anna Karlin of the University of Washington’s Theory of Computation group recently became the first Allen School faculty member to be elected a member of the National Academy of Sciences. Karlin, who holds the Bill & Melinda Gates Chair in Computer Science & Engineering and serves as Associate Director for Graduate Studies at the Allen School, was honored for her significant contributions to algorithms and algorithmic game theory. She joins a distinguished community of scholars elected by their peers to advise the nation on matters related to science and technology while promoting education and research.
Much of Karlin’s early research was focused on online and probabilistic algorithms and analysis. Online algorithms receive a series of inputs over time, and must make decisions as each input arrives, without the benefit of information about future inputs. Karlin and her collaborators Mark Manasse, Larry Rudolph and Daniel Sleator coined the phrase “competitive algorithm” to describe an online algorithm that achieves the provably best possible performance compared to the clairvoyant optimal result — in other words, performs nearly as well as if decisions were made with full knowledge of the future.
A useful abstraction and simple illustrative example is the ski rental problem. “When you start out skiing, you don’t know if you’ll love it or hate it or how many times you will end up going,” Karlin explained. “And yet, each time you head out, you have to make a decision: should you rent or should you buy?
“If you rent until the total amount you’ve spent equals the cost of buying skis,” she went on, “you will never pay more than twice what the optimal clairvoyant would have paid. More interesting is that using randomization reduces this factor of 2 down to e/(e-1), which is about 1.58. And it turns out that both of these bounds are provably optimal.”
Karlin and various co-authors applied this style of analysis to achieve optimally competitive algorithms for a number of problems including memory management, load balancing, and transmission control protocol (TCP) acknowledgement.
Her research on paging and caching naturally led her into collaborations with systems researchers on various other memory management problems. For example, in work with Pei Cao, Edward Felten (Ph.D., ‘93) and Kai Li that received a Best Paper Award at the 1995 ACM SIGMETRICS Conference, she studied optimal integrated strategies for prefetching and caching. The team complemented its theoretical analysis with simulations showing that the new strategies proposed were able to reduce the running time of applications by up to 50%. Karlin and her student Tracy Kimbrel (Ph.D., ‘97) subsequently extended the theoretical results to prefetching and caching from multiple parallel disks. In another example, Karlin worked with Alec Wolman (Ph.D., ‘02), Geoff Voelker (Ph.D., ‘00), Nitin Sharma (M.S., ‘98), Neal Cardwell (M.S., ‘00) and faculty colleague Hank Levy to demonstrate the limitations of web proxy cache sharing among organizations.
A favorite topic of Karlin’s throughout her career has been probabilistic algorithms and analysis. One of her most impactful results in this area emerged from a collaboration with Yossi Azar, Andrei Broder and Eli Upfal on “Balanced Allocations,” which has come to be known as the “power of two choices.” This paper considers a basic “balls-in-bins” problem: It has long been known that when n balls are tossed one at a time into n bins, independently and uniformly at random, the expected value of the maximum load is about log(n)/loglog(n). Karlin and her co-authors showed that if, when placing each of the n balls into a bin, two random bins are selected and then the ball is placed in the less loaded bin, this maximum load drops to loglog(n) — an exponential improvement.
“Balls-in-bins problems are ubiquitous in computer science,” said Karlin, “and the ‘power of two choices’ paradigm has turned out to be useful in a variety of applications, from hashing and load balancing to network and data center management.”
In 1999, Karlin became excited by work on “Competitive Auctions and Digital Goods” that her student Jason Hartline (Ph.D., ‘03) had done with Andrew Goldberg and Andrew Wright during a summer internship at InterTrust Technologies’ STAR Lab. That work, which recently earned the 2021 SIGECOM Test of Time Award for “initiating a long and fruitful line of work in approximately revenue-optimal auction design in prior free settings,” inspired Karlin to turn her attention to auction theory and, more generally, the field of mechanism design. Mechanism design applies the tools of game theory to design systems in which rational participants intent on maximizing their own self-interest will also achieve the designer’s intended goal. Potential applications run the gamut from network traffic routing and scheduling tasks in the cloud, to ecommerce and search engine advertising — all of them enabled by the rise of the internet.
“Nowadays, pretty much any real algorithmic problem that arises in a distributed setting is in fact a mechanism design problem,” Karlin noted.
The implications of Karlin’s work in this area extends to multiple industries in which the provision of goods and services depends on finding the ideal balance between pricing and profit given available resources and consumer motivations. For example, in joint work with Shuchi Chawla, Nikhil Devanur and Balasubramanian Sivan, she considered the design of “pay-per-play” pricing of songs, apps, video games and other software for consumers whose value for such a digital good evolves as they use it according to a stochastic process known as a martingale. In contrast to the standard approach to selling goods, where the buyer purchases an item and then can use it an unlimited number of times, in this form of pricing the buyer pays a little bit each time they want to use it. This enables a seller to extract different amounts of money from different consumer types based on how long and to what extent they remain interested in the product, as opposed to the one-price-fits-all model.
“We showed that using a free trial period followed by a fixed posted price for each use yields near-optimal profit for such digital goods — and one which is, generally speaking, significantly higher than that obtained using other pricing methods,” Karlin said. “Pay-per-play has the added advantage of being risk-free to the consumer, since they can stop buying that app, game or song whenever they lose interest.”
In another paper, Karlin worked with Kira Goldner (Ph.D. ‘19), Amos Fiat and Elias Koutsoupias to solve the “FedEx problem,” wherein the seller has to balance maximizing revenue with customer expectations related to service quality and cost. Sellers tend to have a variety of options available to them for responding to price sensitivity and other customer-driven factors, including market segmentation, differential pricing, or lower-cost (and presumably lower-quality) versions of a product or service. Karlin and her collaborators came up with the optimal approach for the seller to extract maximum revenue in instances where customer values such as desired delivery time or other factors are drawn from known probability distributions.
Despite its name, like many of the questions Karlin has tackled in her career, the results on the FedEx problem are more broadly applicable to a variety of domains. This also holds true for her work on novel algorithmic mechanisms for maximizing social welfare in the pricing of goods with the prospect of resale with Goldner, Fiat, Alon Eden and Michal Feldman. In this case, the team addressed a scenario known as the interdependent value setting, which captures the fact that information one prospective buyer has about goods being sold may significantly affect the value other buyers have for those goods. The researchers used the example of auctioning off oil drilling rights on a piece of land, where geologic surveys done by one prospective buyer contain information that could significantly sway the interests of another prospective buyer.
The decades-old economics literature on this problem had yielded strong impossibility results, even in extremely simple scenarios such as selling a single item. Karlin and her co-authors were able to circumvent these negative results using a combination of randomization and approximation, obtaining the first positive results for a broad class of combinatorial auctions — and earning the award for Best Paper with a Student Lead Author at the 20th Conference on Economics and Computation (EC ‘19).
Other problems Karlin has considered include pricing and resource allocation in the cloud, sponsored search auction design and analysis, minimizing cost in procurement auctions such as “buying” a shortest path in a network or a spanning tree, strategic behavior of Bitcoin miners, and the design of auctions that achieve near-optimal performance in the presence of a Bayesian prior without actually knowing the prior. Inspired by the Mechanism Design for Social Good initiative, initially founded by her former student Goldner and Rediet Abebe, going forward, Karlin aims to build on past work and apply her expertise in mechanism design and modern matching markets to domains such as health care, energy, and the gig economy.
Along with advancing new algorithms for mechanism design, Karlin is also interested in pushing the field forward by addressing long-standing problems that underpin the theory and practice of computing. In what is likely to be the most influential result of her career, last year she worked with current Ph.D. student Nathan Klein and faculty colleague Shayan Oveis Gharan to achieve the first improved approximation algorithm for the Traveling Salesperson Problem (TSP) in over 40 years. TSP — which aims to find the most efficient route across multiple points and back to the start — is a fundamental question with real-world implications ranging from transportation and logistics, to genomics and circuit board design. TSP is also a cornerstone problem in theoretical computer science, the study of which has led to the development of many foundational algorithmic techniques.
“TSP is NP-complete, so the holy grail has been to design an efficient approximation algorithm that is guaranteed to get a nearly optimal solution,” Karlin explained. “In the 70s, researchers discovered an algorithm that always guarantees a solution whose cost is never more than 50% higher than optimum. Nathan, Shayan and I were finally able to surpass the 50% threshold, which hopefully will pave the way for even greater progress down the road.”
According to Oveis Gharan, Karlin stands out not only for being a gifted theoretician but also for her eagerness to embrace unfamiliar ideas and learn alongside her students.
“I have worked with a few senior researchers in my career, but Anna is perhaps the only one who gets so excited and spends a significant amount of time learning new ideas and new techniques outside of her comfort zone,” Oveis Gharan said. “This is a great motivation for graduate students who are just starting out to learn new techniques together with their advisor and to build their self-confidence as researchers.”
Karlin’s enthusiasm for helping students to explore new ideas inspired her to co-author the book Game Theory, Alive with mathematician Yuval Peres. Published by the American Mathematical Society in 2017, the book presents the mathematical concepts that underpin game theory in an approachable and engaging way, including anecdotes, illustrations, and profiles of the individual mathematicians, statisticians, and economists credited with advancing the field.
“Game theory’s influence is felt in a wide range of disciplines, and the authors deliver masterfully on the challenge of presenting both the breadth and coherence of its underlying world-view,” Cornell professor Jon Kleinberg wrote. “The book achieves a remarkable synthesis, introducing the reader to the blend of economic insight, mathematical elegance, scientific impact, and counter-intuitive punch that characterizes game theory as a field.”
Karlin’s research career began at Stanford University, where she earned her bachelor’s degree in applied mathematics before earning her Ph.D. in computer science. Following a postdoc at Princeton University, Karlin spent six years as a principal scientist at DEC’s Systems Research Center. While it became clear early on that she would be a “rock star” in the field of computing, Karlin was also an actual rock star wannabe; in 1993, she took part in the first musical performance to be live-streamed on the internet with the band Severe Tire Damage — although, as Karlin herself says with a smile, “just because we were first doesn’t mean we were any good.”
Shortly thereafter, she left Palo Alto for Seattle to join the UW as a visiting professor in 1994. She made the move permanent two years later.
“I’m so honored to receive this recognition,” said Karlin. “All I can say is that my good fortune is due to the many brilliant colleagues and students I’ve had the pleasure of collaborating with during my career.”
Karlin is one of 120 leading scholars and scientists to be elected full members of the NAS and among a record-high 59 women recognized in the 2021 class. The Academy elected another 30 non-voting international members, bringing the total honorees to 150.
“We are incredibly proud of Anna for being elected to the National Academy of Sciences,” said Magdalena Balazinska, professor and director of the Allen School. “Anna is a tremendously talented researcher. She’s also a dedicated colleague and deeply caring teacher and mentor. She’s an inspiration to all of us.”
Karlin was previously elected Fellow of the American Academy of Arts & Sciences and of the Association for Computing Machinery. She is the fifth Allen School faculty member to be elected a member of the National Academies, joining professors Tom Anderson, Ed Lazowska, and Hank Levy and professor emeritus Susan Eggers — all of whom were inducted into the National Academy of Engineering.
Read the NAS announcement here.
Congratulations, Anna!