Posts

Featured Post

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

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.