Algorithmics, Social choice, Market Design, and Other Topics

Working Paper: https://cgi.cse.unsw.edu.au/~haziz/PIRMES.pdf  Abstract: In a typical school choice application, the students have strict preferences over the schools while the schools have coarse priorities over the students based on their distance and their enrolled siblings. The outcome of a centralized admission mechanism is then usually obtained by the Deferred Acceptance (DA) algorithm with random tie-breaking. Therefore, every possible outcome of this mechanism is a stable solution for the coarse priorities that will arise with certain probability. This implies a probabilistic assignment, where the admission probability for each student-school pair is specified. In this paper, we propose a new efficiency-improving stable `smart lottery' mechanism. We aim to improve the probabilistic assignment ex-ante in a stochastic dominance sense, while ensuring that the improved random matching is still ex-post stable, meaning that it can be decomposed into stable matchings regarding the ...

Title:  Fair Transit Stop Placement: A Clustering Perspective and Beyond Authors :  H. Aziz, L. Gai, Y. Guo, J. Vollen Abstract : We study the transit stop placement (TrSP) problem in general metric spaces, where agents travel between source–destination pairs and may either walk directly or utilize a shuttle service via selected transit stops. We investigate fairness in TrSP through the lens of justified representation (JR) and the core, and uncover a structural correspondence with fair clustering. Specifically, we show that a constant-factor approximation to proportional fairness in clustering can be used to guarantee a constant-factor biparameterized approximation to core. We establish a lower bound of 1.366 on the approximability of JR, and moreover show that no clustering algorithm can approximate JR within a factor better than 3. Going beyond clustering, we propose the Expanding Cost Algorithm, which achieves a tight 2.414-approximation for JR, but does not give any bound...

https://link.springer.com/content/pdf/10.1007/s11238-025-10098-0.pdf  

H. Aziz, B. Lee, S. Morota Chu, and J. Vollen. Proportionally Representative Clustering.  WINE 2024 .  [  Pdf  ]  In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering— one of the fundamental tasks in unsupervised machine learning. We pro- pose a new axiom “proportionally representative fairness” (PRF) that is designed for clustering problems where the selection of centroids re- flects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair cluster- ing algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approxi- mation algorithm for the well-studied Proportional Fairness (PF) axiom [ 13 ]. Our algorithm for the discrete setting also matches the best kn...

Special Issue on Fair Public Decision Making: Allocating Budgets, Seats, and Probability at SCW. URL:   https://link.springer.com/article/10.1007/s00355-024-01564-9 It was a pleasure to co-edit with Felix Brandt, Edith Elkind & Jérôme Lang.

  Workshop Theme The field of  Computational Social Choice  studies the ways in which the preferences of individuals can be aggregated in order to make collective decisions, like choosing the winner of an election. Algorithms for these problems have wide-ranging applications in democracy, hiring, facility location, reinforcement learning, school choice, and more. Researchers have sought to develop quantitative approaches to understanding the effectiveness of voting rules. A prominent measure is the notion of  distortion : one imagines that the voters’ preferences are derived from some underlying cardinal utilities/costs, and the distortion measures how well a voting rule is able to optimize the total social welfare/cost given only the ordinal preferences. The pursuit of voting rules with low distortion in each of these models has been an incredibly fruitful endeavor, deepening our understanding of previously studied voting rules, and also leading to the design of a n...