Jason Hartline Wins ESA Test of Time Award

Northwestern Engineering’s Jason Hartline received a European Symposium on Algorithms (ESA) Test of Time Award, which recognizes “excellent papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating for the field today.”

The paper “Competitive Auctions for Multiple Digital Goods,” was co-authored by Andrew Goldberg, senior principal scientist at Amazon, and originally appeared in the Proceedings of the 9th Annual European Symposium on Algorithms in August 2001.

Hartline and Goldberg considered the sale of multiple digital goods — for instance, concurrent broadcasts of several movies to passengers on a flight — to buyers who each desire one movie at most. The team investigated adaptive pricing via auctions and determined that, when the optimal revenue from pricing movies is sufficiently high for the airline and the maximum prices customers are willing to pay are known, then a mechanism without knowledge of buyer preferences can obtain a significant fraction of this optimal revenue.

“The ideas of a paper are only important 20 years after its publication date if the research community invests in developing, extending, and adapting them,” Hartline said. “It has been really wonderful to see where the algorithms community, in particular of the European Symposium on Algorithms, has taken the ideas that captivated Andrew Goldberg and me back in 2001. It's quite an honor to receive this award and a wonderful chance to reflect on and review two decades of fantastic subsequent research of the community.”

In the paper, Hartline and Goldberg demonstrated an approach to robust mechanism design that splits the optimal pricing problem into two parts: first, understanding algorithms for computing prices for diverse markets from data, and second, understanding the sample complexity of various pricing algorithms. 

“This perspective has been expanded on in many subsequent papers and the two directions —algorithmic pricing and sample complexity in mechanism design — are now vibrant subfields at the interface between computer science and economics,” Hartline said.

Hartline’s collaboration with Goldberg began in the summer of 1999 at InterTrust Technologies’ STAR Lab, the research arm of the digital rights management company. Hartline joined the lab for a summer internship as a second-year PhD student at the University of Washington (UW), advised by Anna Karlin, the Bill and Melinda Gates Chair in Computer Science and Engineering at UW. Goldberg was a researcher at the STAR Lab at the time.

“This was my second paper that explored the role of algorithms in the design of auctions,” Hartline said. “The topic became my PhD thesis and the basis for my entire career.”

Northwestern CS at ESA 2022

Additional Northwestern contributions to ESA 2022 included:

“Correlated Stochastic Knapsack with a Submodular Objective” — Sheng Yang, a visiting scholar in Northwestern CS; Samir Khuller, Peter and Adrienne Barris Chair of Computer Science at Northwestern Engineering; and Sunav Choudhary, Subrata Mitra, and Kanak Mahadik (Adobe Research). Yang is a member of the Northwestern CS Theory Group advised by Khuller.

“Simple Dynamic Spanners with Near-optimal Recourse Against an Adaptive Adversary” — Pattara Sukprasert, fifth-year PhD student in computer science advised by Khuller; Sayan Bhattacharya (University of Warwick, United Kingdom); and Thatchaphol Saranurak (University of Michigan).