Algorithmics, Social choice, Market Design, and Other Topics

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

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 Haris Aziz, Péter Biró, Gergely Csáji, Tom Demeulemeester https://arxiv.org/abs/2602.10679  

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. 

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