
Compatible k-Relaxations of Fairness and Non-Wastefulness Under Hereditary Constraints
- Presenter
- Dr. Zhaohong Sun. Faculty of Information Science and Electrical Engineering, Department of Informatics. Kyushu University, Japan
- Date & Time
- Tuesday, August 4, 12:30 – 13:50
- Location
- Research Building 7, Room 123
Abstract
We study two-sided matching markets under count-based hereditary constraints, which extend beyond simple capacity limits and arise in applications such as diversity requirements and refugee resettlement after appropriate aggregation. In these settings, fairness and non-wastefulness are often incompatible, and existing approaches typically address this tension by prioritizing one property at the expense of the other. We take a different approach by relaxing both properties simultaneously using a single integer parameter. Specifically, we study envy-received up to k peers (ER-k) and non-wastefulness up to k objections (NW-k). Our main theoretical result establishes a tight compatibility frontier by showing that, for every integer k, ER-k and NW-k are always compatible under count-based hereditary constraints. We provide two equivalent polynomial-time algorithms to compute such matchings: a k-admissible cutoff algorithm and a k-admissible college-proposing deferred acceptance mechanism. Finally, experimental results demonstrate that even small relaxations achieve a favorable balance between fairness and non-wastefulness.
Biography
In April 2023, Dr. Zhaohong Sun joined the Kyushu University Multi-Agent Lab as a tenure-track Associate Professor, while simultaneously serving as a Research Scientist at CyberAgent AI Lab through the cross-appointment system. He also holds a Visiting Researcher position at the University of Tokyo Market Design Center (UTMD) and actively contributes to the ERATO Kojima Market Design Project under the direction of Prof. Fuhito Kojima. Dr. Sun received his Ph.D. in Computer Science from UNSW Sydney in September 2020, where he was supervised by Scientia Prof. Haris Aziz, Prof. Serge Gaspers, and Scientia Prof. Toby Walsh. During his doctoral studies (2016–2020), he was also affiliated with the Commonwealth Scientific and Industrial Research Organisation (CSIRO). Prior to his Ph.D., he obtained his master’s degree from Kyushu University (2014–2016) under the supervision of Distinguished Prof. Makoto Yokoo. He earned his bachelor’s degree from Dalian University of Technology in 2013.
















