Upcoming Events
| 09 Dec 2025; - 10:00AM - 11:00AM Metric Distortion of Matching: A Stochastic Perspective |
| 10 Dec 2025; - 08:00AM - 09:30AM Learning, Directing, and Validating Synthetic Crowds: Parametric Inference, Design Optimization, and Heterogeneous Reinforcement Learning with Variance-Based Evaluation |
| 10 Dec 2025; - 12:00PM - 02:00PM Generation and Optimization of Physics-Based Graphics Simulations |
Subscribe to RSS FeedCS Events
Qualifying ExamMetric Distortion of Matching: A Stochastic Perspective |
|
||
Tuesday, December 09, 2025, 10:00am - 11:00am |
|||
Speaker: Ziyi Cai
Location : CoRE 305
Committee:
Assistant Professor Peng Zhang
Assistant Professor Kangning Wang
Assistant Professor Xintong Wang
Professor Eddy Z. Zhang
Event Type: Qualifying Exam
Abstract: Bipartite matching is a fundamental problem with a wide range of applications, in many of which only ordinal preferences, rather than the underlying cardinal utilities, are available. The metric distortion framework was established to measure the efficiency loss when only ordinal information is used. However, determining the optimal metric distortion for bipartite matching has proved to be notoriously difficult.In this talk, I will present some recent progress on metric distortion of matching under stochastic models. Average-case distortion on a uniform line: We show that when agents and items are drawn i.i.d. from a uniform distribution on a one-dimensional segment, the simple matching rule of random serial dictatorship achieves exponentially better distortion than the best-known distortion in the worst-case model. Semi-random model: When points in an arbitrary metric space are randomly partitioned into two sides, we propose a new simple matching rule with distortion better than the best-known distortion in the worst-case model.Related Publication(s): Ziyi Cai, Qing Chen, Kangning Wang, and Peng Zhang. Metric Distortion of Matching: A Stochastic Perspective. In submission.
:
Contact Assistant Professor Peng Zhang
Zoom Link: https://rutgers.zoom.us/j/93037440994?pwd=wfoNwFJ1o6fbeoApSF25TVLrC3UoFU.1