Markets as Approximation Algorithms: Their Design and Analysis

Speaker: Dr. Yaonan Jin
Huawei's Taylor Lab

Title: Markets as Approximation Algorithms: Their Design and Analysis

Date: Monday, 29 September 2025

Time: 4:00pm - 5:00pm

Venue: Lecture Theater F (Leung Yat Sing Lecture Theater), near lift 25/26, HKUST

Abstract:

Numerous modern applications in computer science involve self-interested participants, whose incentives are typically misaligned with the algorithm designers. Examples abound, such as auctions for online advertising, pricing schemes in e-commerce, and resource allocation in various contexts. The theory of EconCS, an intersection of Computer Science and Economics, addresses challenges arising in these scenarios.

In this talk, I will survey my research in EconCS, with an emphasis on the lens of approximation -- a viewpoint brought by computer scientists that has greatly enriched our understanding of markets. Below are two representative results:

  • 1. First Price Auction, the "most canonical and pivotal" auction format -- the unifying algorithm by Google and other major platforms for online advertising -- guarantees a tight 1 - 1/e2 ≈ 86.47% approximation to the theoretically optimal (but utopian) welfare.
  • 2. Uniform Pricing, the "most practical and ubiquitous" pricing scheme -- seen across online and offline retail -- ensures a tight 38.17% approximation to the theoretically optimal (but impractical) revenue.

Biography:

Yaonan Jin is a full-time researcher at Huawei's Taylor Lab. His research interests encompass Theoretical Computer Science, with an emphasis on Algorithmic Economics. Before joining Huawei, he obtained his PhD from Columbia University in 2023 (advised by Xi Chen and Rocco Servedio). Before that, he obtained his MPhil from Hong Kong University of Science and Technology in 2019 (advised by Qi Qi) and his BEng from Shanghai Jiao Tong University in 2017.