Posts

Best-of-Both-Worlds Fairness in Committee Voting with Ordinal Preferences

Image
Working Paper: Title Best-of-Both-Worlds Fairness in Committee Voting with Ordinal Preferences Abstract: Choosing a committee by lottery can improve representation in expectation, but the committee ultimately selected must also be representative. We ask how far these two demands can be combined when voters rank candidates, possibly with ties. We show that every weak-ranking profile admits a lottery satisfying cutoff group fair share (cutoff-GFS) and fractional rank proportional justified representation plus (Rank-PJR+) ex ante, and inclusion proportionality for solid coalitions (IPSC) ex post. Such a lottery can be computed in polynomial time on unrestricted weak rankings. Under strict rankings, IPSC is proportionality for solid coalitions (PSC). In contrast, requiring rank justified representation (Rank-JR) ex post, and hence also Rank-PJR+, can be incompatible with rank individual fair share (Rank-IFS) ex ante, already under strict rankings. We also classify the complexity of exactly...

A Deterministic Polynomial-Query Protocol for Envy-Free Cake Cutting

Image
How do you divide a cake among n people so that nobody prefers someone else’s piece? For two people the answer is ancient: one cuts, the other chooses. For more people the road has been long. Brams and Taylor (1995) gave the first protocol for any number of people, but the number of steps it needs has no upper bound. Aziz and Mackenzie (2016) gave the first bounded protocol, with a bound that is a tower of six n’s. Earlier this year, Ye and Bai brought this down to a single-exponential bound, and Psomas gave a 2^O(n log n) protocol. In a new working paper, I give a deterministic protocol that uses O(n^8 log n) queries, the first deterministic polynomial bound. (A query asks one person to value a piece or to mark a cut.) Similar techniques give a polynomial bound for chore division as well.  The paper is getting early feedback and will be public soon on this page. Update: link

A Single-Exponential Protocol for Envy-Free Chore Division

Image
 Working Paper:

Core Anchors and Their Completions: Fair Lotteries and Anchored Rules

New Working Paper:  https://cgi.cse.unsw.edu.au/~haziz/grp-core.pdf Title:  Core Anchors and Their Completions: Fair Lotteries and Anchored Rules Abstract We study lotteries over fixed-size committees under approval preferences. We prove that group resource proportionality (GRP) ex ante is compatible with core stability ex post, via a polynomial-time construction whose support has size at most one more than the number of candidates. The key is a core anchor: an affordable partial committee whose every completion lies in the core. Core anchors always exist and can be computed in polynomial time. Randomized completion gives the best-of-both-worlds guarantee, while deterministic completion yields anchored rules, a new family of core-stable rules that can target any objective. For coverage and maximin support, their guarantees exceed those of both local and global harmonic-entropy rules of Becker et al. (2026). Finally, although strict Droop-core committees can be computed in poly...

Approximating Random Serial Dictatorship: Hardness and Markov Chains

Haris Aziz, Bart de Keijzer, Sebastian Homrighausen, Ali Pourmiri:  A pproximating Random Serial Dictatorship: Hardness and Markov Chains . Working Paper, 202 6 Abstract: We consider a setting in which a randomised social choice rule selects one of the alternatives on the basis of preferences expressed by agents. Our focus is on \emph{Random Serial Dictatorship} (RSD), a central rule in social choice theory.  Computing RSD shares exactly is known to be $\mathsf{\#P}$-complete but the complexity of approximating it has been open for more than a decade. We resolve this question negatively: unless $\mathrm{NP}\subseteq\mathrm{BPP}$, there is no FPRAS for computing the RSD share of a given listed alternative, even for  dichotomous preferences.  We also develop a Markov Chain Monte Carlo framework for approximately counting the permutations that select a target alternative. The framework gives an FPRAS whenever the relevant suffix-restricted state spaces admit rapidly mix...

From Subsidies to Lotteries: A Payment Bridge for Best-of-Both-Worlds Fairness

Image
I am sharing a preliminary draft of joint work with Xinhang Lu, Simon Mackenzie, and Mashbat Suzuki on best-of-both-worlds fair division.  We establish an algorithmic payment bridge: polynomial-time algorithms for suitable envy-freeable allocations at every positive utility rescaling yield explicit ex-ante envy-free lotteries in polynomial time, preserving prescribed ex-post guarantees. We also give an exact characterization of feasible fair lotteries and new guarantees for several valuation classes. We are currently refining the presentation and welcome comments. Read the preliminary draft (PDF)

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability: A Video Explainer

  Smart Lotteries in School Choice: Ex-ante Pareto-Improvement with Ex-post Stability Haris Aziz, Péter Biró, Gergely Csáji, Tom Demeulemeester https://arxiv.org/abs/2602.10679  

Fair budgets from ranked ballots: PB-EAR

How do you split a shared budget fairly when people rank projects that cost very different amounts? PB-EAR, from our AAAI 2021 paper  Proportionally Representative Participatory Budgeting with Ordinal Preferences  ( AAAI version ), gives every voter an equal slice of the budget and lets groups pool their slices to fund the projects they rank highest, looking further down the ballots only when nothing is yet affordable. Every cohesive group is guaranteed its proportional share, and the rule extends our  Expanding Approvals Rule  for elections to budgets with project costs, ties and unequal voter weights.  That makes it a natural fit for DAO grant rounds such as   TheDAO Security Fund 's ETHSecurity Initiatives, where badge holders will rank the security initiatives listed on   the app  to allocate the fund's budget. The two-minute video below walks through a worked example. Here's an educational tool someone built to show how PB-EAR works. 

Smart Lotteries in School Choice Ex-ante Pareto-Improvement with Ex-post Stability

Image
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 ...

Fair Transit Stop Placement: A Clustering Perspective and Beyond

Image
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...

Jérôme Lang’s contributions at the interface of economic theory with artificial intelligence

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

Proportionally Representative Clustering

Image
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

Image
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.

Distortion in Social Choice @ FOCS 2024

  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...

KTI70: Conference to celebrate the 70th anniversary of the Institute of Economics

Image

KTI70: CONFERENCE TO CELEBRATE THE 70TH ANNIVERSARY OF THE INSTITUTE OF ECONOMICS

Image
KTI70: Conference to celebrate the 70th anniversary  of the Institute of Economics Date: 21-22 October, 2024 Venue: Institute of Economics, HUN-REN Center for Economic and Regional Studies 1097 Budapest, Tóth Kálmán str. 4. PROGRAM Monday, 21 October, 2024 Plenary Session I. Venue: Conference Hall 09.30 – 09.40 Opening remarks by László Á. Kóczy, Director, Institute of Economics 09.40 – 10.40 Plenary talk by Haris Aziz (UNSW Sydney): Justifiably Fair Decision Making 10.40 – 11.00 Coffee break (Gallery) 11.00 – 12.30 Parallel Session I. Parallel Session: Theory Venue: room K.0.11 • Miklós Pintér, (Budapest University of Technology and Economics): Generalized Type Spaces • Péter Csóka, (Institute of Economics): Two Axiomatizations of the Pairwise Netting Proportional Rule in Financial Networks • László Á. Kóczy, (Institute of Economics): One Man, One Vote, One Price Parallel Session: Social and collaboration networks Venuee: room K.0.12 • László Lőrincz, (Institute of Economics), Old...

Hong Kong Algorithmic game theory Summer School

  https://projects.croucher.org.hk/summer-courses/algorithmic-game-theory/programme

SAGT 2024 papers

Image
 

AI and ‘fair’ decision-making

Image
 I was featured in the APAC network expert segment where I discussed the the intersection of computer science and game theory.

An Invitation to Algorithmic Market Design: An Interplay b/w Maths, Economics and Computer Science

Image
Who gets what is a fundamental question when resources are constrained. In this talk, the speaker will provide a window to the topic of Algorithmic Market Design that is based on an exciting interplay between mathematics, economics and computer science. In this long session, I gave an overview of the topic to a general audience at The Black Hole society .  The first 45 minutes is a general interactive session.