Source-linked AI summary
Fair Division of Lotteries
Ayumi Igarashi, Yeeseok Oh
TL;DR
Fair division of uncertain items raises the question of whether an allocation fair under expected utilities is also fair after item values are realized. The paper studies ex-ante and ex-post envy-freeness, establishing conditions for exact or approximate alignment and analyzing the complexity of evaluating ex-post EF probability.
Problem
The paper asks whether ex-ante envy-free allocations can also maximize or approximate the probability of being envy-free after uncertain utilities are realized.
Source: §1 · pp. 1–2Method
The paper analyzes fixed allocations under exogenous random item utilities and derives results for distributional conditions including convolution-power families, log-concavity, and symmetry.
Source: §1 · pp. 1–2Results
Ex-ante EF allocations maximize ex-post EF probability under specified convolution-power conditions and provide constant-probability guarantees under log-concavity or symmetry for a fixed number of agents; evaluating the probability is weakly #P-hard but has a pseudo-polynomial dynamic-programming algorithm.
Source: §1 · p. 2Takeaways & Limitations
The results identify settings in which ex-ante EF aligns with optimal or approximately optimal ex-post EF probability, while also characterizing computation of that probability.
Source: §1 · p. 2For non-atomic common item values under identical valuations, every allocation has zero ex-post EF probability when there are at least two agents and at least one item, so the multiplicative guarantees are vacuous.
Source: §7.2 · p. 15
Abstract
from arXiv · showhide
We study fair division of uncertain items, where the utility of each item is a random variable whose realization is observed only after the allocation is determined. This uncertainty creates a distinction between ex-ante fairness, evaluated before utilities are realized, and ex-post fairness, evaluated after realization. We examine to what extent these two notions are compatible. We first identify conditions under which ex-ante envy-free allocations maximize ex-post envy-freeness probability. These include two-agent instances where utilities toward the same item follow the same distribution from a convolution-power family. For an arbitrary number of agents, we establish analogous optimality results when the common generator is non-atomic or log-concave. Beyond convolution-power families, we derive approximation guarantees for ex-ante envy-free allocations relative to the optimal ex-post envy-freeness probability under log-concave or symmetric utilities. We also study the computational complexity of evaluating ex-post envy-freeness probabilities, establishing hardness results as well as pseudo-polynomial-time algorithms.
1. Introduction
The paper asks whether allocations judged fair before uncertain item values are realized remain fair afterward, focusing on envy-freeness (EF). It identifies conditions for ex-ante EF to maximize or approximate ex-post EF probability, and studies the complexity of computing that probability.
Our Contributions
- In the fishing example, one allocation is ex-ante EF but has ex-post EF probability 0.0099, while another is not ex-ante EF but has probability 0.99.The example illustrates that the two fairness assessments can diverge.Source: §1 · p. 2
- Ex-ante EF allocations maximize ex-post EF probability for two agents with a common convolution-power family of item-utility distributions; this extends to any number of agents when the generator is non-atomic or log-concave.The paper also gives approximation guarantees beyond these families and studies the computation of ex-post EF probability.Source: §1 · p. 2
- Under log-concave or symmetric utilities, an ex-ante EF allocation achieves a constant ex-post EF probability guarantee for a fixed number of agents, though it need not maximize that probability.This result applies beyond convolution-power families.Source: §1 · p. 2
- Evaluating an allocation’s ex-post EF probability is weakly #P-hard, but dynamic programming computes it in pseudo-polynomial time.Source: §1 · p. 2
- In the identical-valuations case, valuations for each item are the same across agents, and the paper reports that most of its results transfer to this setting.Source: §1 · p. 2
Related Work
- Unlike related work on minimizing expected maximum envy, allocation-dependent asymptotic fairness, or lotteries over allocations, this paper fixes an allocation and studies ex-post EF probability under uncertain utilities.The related models include uncertain ordinal preferences in house allocation and uncertainty in divisible-resource allocation.Source: §1 · pp. 2–3
2. Preliminaries
The preliminaries introduce probability-distribution concepts used in the paper, including characteristic functions, Poisson and log-concave distributions, and convolution powers.
Probability distributions
- A random variable is symmetric when its distribution is unchanged by reflection around its mean, and it is non-atomic when it assigns zero probability to every single value.Source: §2 · p. 3
Probability tools
- A random variable’s characteristic function is ϕX(t) = E[eitX], and the preliminaries introduce an atom inversion formula for it.Source: §2 · p. 3
Probability distributions
- A Poisson random variable with rate λ has mean λ, and independent Poisson variables sum to a Poisson variable whose rate is the sum of their rates.The paper presents Poisson distributions as a model for event counts over a fixed time or space.Source: §2 · pp. 3–4
- Log-concavity applies to continuous densities or integer-valued probability mass functions with interval support and a single-peaked shape; it is preserved under convolution.The paper lists uniform, Gaussian, exponential, Bernoulli, and binomial distributions as examples.Source: §2 · p. 4
- A convolution-power family generated by a distribution consists of the distributions of finite sums of i.i.d. random variables drawn from that distribution.The paper notes that convolution powers of a log-concave distribution are also log-concave.Source: §2 · p. 4
3. Model
The model allocates indivisible items among agents with additive utilities that are independent random variables, evaluating fairness both at expected values and after utilities are realized. It also shows that ex-ante welfare maximization carries over to ex-post welfare maximization for utilitarian and Nash welfare.
Fair Division of Lotteries
Fairness and welfare
- An allocation is envy-free when every agent values their own bundle at least as highly as every other agent’s bundle.Source: §3 · p. 5
Ex-Ante and Ex-Post Problems
- Ex-ante properties are evaluated using expected item utilities, whereas ex-post property probabilities are evaluated over realized utilities.The paper’s example contrasts an ex-ante EF allocation with probability 0.0099 of ex-post EF and a non-ex-ante-EF allocation with probability 0.99.Source: §3 · p. 5
- An ex-ante utilitarian or Nash social welfare maximizing allocation also maximizes the corresponding ex-post welfare objective.For utilitarian welfare, the ex-ante and ex-post values coincide by linearity of expectation; for Nash welfare, the proof uses independence of agents’ own-bundle utilities.Source: §3 · p. 5
4. Achieving Ex-Post Fairness with Ex-Ante Solutions
The section identifies conditions under which ex-ante envy-free allocations maximize the probability of being envy-free after utilities are realized. The conditions cover two-agent convolution-power instances and, with additional restrictions, instances with any number of agents.
4. Achieving Ex-Post Fairness with Ex-Ante Solutions
- For two agents with the same itemwise utility distributions from a common convolution-power family, every ex-ante EF allocation maximizes ex-post EF probability.This includes Poisson item yields.Source: §4 · pp. 6, 9
- For two agents, equal splitting maximizes ex-post EF probability when all utilities follow the same distribution.The proof characterizes ex-ante EF allocations as those giving the two agents equal numbers of convolution-generator copies.Source: §4 · pp. 6–7
- With three agents, identical distributions across agents do not suffice: an instance exists where an ex-ante EF allocation fails to maximize ex-post EF probability.The counterexample uses a distribution with both atomic and continuous components.Source: §4 · p. 7
- For any number of agents, the same optimality holds when the common convolution-power generator is non-atomic or log-concave.Poisson item utilities are one covered case.Source: §4 · pp. 7–9
5. Approximating Ex-Post Fairness
The section bounds how well ex-ante EF allocations perform after realization when exact optimality is not assured. The guarantees depend on distributional assumptions and, in some settings, on the number of agents.
5. Approximating Ex-Post Fairness
- An ex-ante EF allocation can have ex-post EF probability (3/4)^{n(n−1)}, which tends to zero as the number of agents grows.The example uses binary lottery items.Source: §5 · p. 10
- For log-concave utilities, an ex-ante EF allocation has ex-post EF probability at least e^-n(n-1), yielding the same approximation ratio to the optimum.The guarantee applies when all utilities are continuous or all are discrete.Source: §5 · p. 10
- For symmetric utilities, an ex-ante EF allocation has ex-post EF probability at least 2^-n(n-1), and this bound is tight.Source: §5 · p. 11
- The reported approximation to the optimal ex-post EF probability is e2 ≈ 0.930, and this approximation is tight.Source: §5 · p. 11
- For common non-atomic symmetric item distributions, ex-ante EF gives an n^n4^−(n choose 2)-approximation; for two agents it maximizes ex-post EF probability.Source: §5 · p. 11
6. Complexity of Ex-Post Fairness
The section studies the computational difficulty of ex-post envy-freeness, including evaluating a fixed allocation’s fairness probability. It establishes counting hardness alongside pseudo-polynomial algorithms, while showing that ex-ante methods can certify optimality in cases where their guarantees apply.
6. Complexity of Ex-Post Fairness
- Approximating the optimal ex-post EF probability is NP-hard, and deciding whether a given allocation maximizes it is coNP-hard.The arguments use deterministic instances, where each allocation’s ex-post EF probability is either zero or one.Source: §6 · p. 12
- Computing an allocation’s ex-post EF probability is weakly #P-hard even with two agents, by reduction from #Partition.The reduction uses binary lottery items and a fixed-value item.Source: §6 · p. 12
- The probability can be computed in O(n^2m(B + 1) + nm^2(B + 1)^2) arithmetic operations and pseudo-polynomial time for independent utilities.Dynamic programming computes bundle-value distributions before combining them to evaluate ex-post EF.Source: §6 · p. 13
- If utilities for the same item may be correlated across agents, computing ex-post EF probability is strongly #P-hard, even for binary lottery items.The base computational model uses integer-valued, finite-support lotteries with rational probabilities represented explicitly.Source: §6 · pp. 12–13
- When Section 4’s conditions make an ex-ante EF allocation ex-post optimal, that allocation can certify optimality without computing its probability.Ex-ante problems reduce to classical fair-division problems after computing expected utilities.Source: §6 · pp. 12–13
7. Identical Valuations
With identical valuations, each item has one realized value shared by all agents, though different items remain independent. The paper extends ex-ante optimality and computational results to this setting, but its positive ex-post probability guarantees do not generally transfer.
7. Identical Valuations
- Identical valuations mean every agent receives the same realized utility from an item, while item values remain mutually independent.The example contrasts an ex-ante EF allocation whose ticket outcome always leaves one person envious with another allocation that is ex-post EF with probability 0.99.Source: §7 · p. 14
7.1. Ex-Ante and Ex-Post Optimality
- Under identical valuations, ex-ante EF allocations maximize ex-post EF probability when n = 2, or the common generator is non-atomic or log-concave.The convolution-power optimality guarantees extend to this setting; the Poisson guarantee also extends.Source: §7.1 · pp. 14–15
7.2. Ex-Post Fairness Guarantees
- For non-atomic common item values, every allocation has ex-post EF probability zero when there are at least two agents and one item.Thus the multiplicative guarantees hold only vacuously, with both achieved and optimal probabilities equal to zero.Source: §7.2 · p. 15
7.3. Computational Complexity
- Under identical valuations, computing ex-post EF probability remains weakly #P-hard even for two agents, yet has a pseudo-polynomial-time algorithm.For integer-valued utilities with finite support and rational probabilities, the arithmetic-operation bound is O(nm(B + 1) + m^2(B + 1)^2).Source: §7.3 · p. 15
8. Conclusion
The conclusion identifies conditions in which an ex-ante EF allocation maximizes ex-post EF probability and points to other fairness notions as future work.
8. Conclusion
- The paper identifies settings where an ex-ante EF allocation maximizes ex-post EF probability.Considering other fairness notions, such as EF1, is a natural direction for future work.Source: §8 · p. 16
Disclosure of AI Usage
The authors report using AI models to find related work and distribution properties, generate examples, and check proofs.
Disclosure of AI Usage
- AI models assisted with related-work searches, identifying distribution properties, generating examples, and checking proofs.The authors report that these uses sometimes yielded an improved result.Source: Disclosure of AI Usage · p. 18
A.1. Counterexamples for Three Agents
Three-agent instances show that ex-ante envy-freeness need not maximize the probability of ex-post envy-freeness, even when agents have identical valuations or share the same item-utility distribution.
A.1. Counterexamples for Three Agents
- A three-agent instance with the same item-utility distribution for every agent shows that an ex-ante EF allocation need not maximize ex-post EF probability.The section also gives a counterexample under identical valuations.Source: §A.1 · pp. 18–19
- When all items’ utilities follow the same distribution, ex-ante EF requires bundle sizes (2,2,2), but no such allocation maximizes ex-post EF probability; under identical valuations, ex-post EF means equal bundle values.Source: §A.1 · p. 20
A.2. Proof of Lemma 4.6
The proof of Lemma 4.6 uses total positivity and log-concavity properties of sums of i.i.d. log-concave random variables to establish inequalities for weighted expectations.
A.2. Proof of Lemma 4.6
- For nonnegative discrete log-concave X, the lemma studies sums S_k of k i.i.d. copies and a bounded log-concave function G through the quantities A_k,ℓ.It establishes A_a,b A_b,a ≤ A_a+1,b−1 A_b−1,a+1.Source: §A.2 · p. 20
- The proof establishes that the pmf p_k(x) of S_k is TP2 in (k, x), using likelihood-ratio and stochastic orders.TP2 means the relevant two-variable function satisfies the total-positivity inequality.Source: §A.2 · pp. 20, 22
- For bounded log-concave W, the weighted expectation B_k = E[W(S_k)] is log-concave in k.This property supplies a key ingredient for the inequalities involving A_k,ℓ.Source: §A.2 · pp. 23, 25
A.3. Proof of Corollary 4.7
The appendix proves an optimality result for Poisson utilities, gives approximation guarantees under other distributional assumptions, and establishes hardness when agents’ utilities for an item may be correlated.
A.3. Proof of Corollary 4.7
- When each item has a common Poisson utility distribution across agents, an ex-ante EF allocation maximizes ex-post EF probability.The proof extends the result to real positive Poisson parameters by approximating them with rational parameters and taking a limit.Source: §A.3 · p. 27
A.4. Proof of Proposition 5.5
- For non-atomic symmetric utilities, the stated approximation guarantee specializes to exact optimality when there are two agents.The supplied passage also states an approximation guarantee for non-atomic log-concave utilities, but its factor is incomplete.Source: §A.4 · p. 27
A.5. Proof of Theorem 6.3
- Computing ex-post EF probability is strongly #P-hard when utilities for the same item may be correlated across agents, even for binary lottery items.For general dependent valuations, the passage also states that computation is not expected to be possible in pseudo-polynomial time.Source: §A.5 · p. 28