Posts

Showing posts from October 11, 2026

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)