Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Mathematics

Faculty/School

Faculty of Science

First Advisor

D. Marc Kilgour

Advisor Role

Supervisor of PhD

Abstract

In studies of collective decision-making, the problem of allocating indivisible items fairly and efficiently is widely acknowledged as particularly challenging. Our study assesses various algorithms for finding balanced allocations based on their ability to achieve desirable properties such as envy-freeness, Pareto-optimality, maximin, maximum Borda sum, and Borda maximin.

Two players with additive preferences allocate an even number of indivisible items, given only each other's strict preference ordering. The algorithms under study include both naive and sophisticated versions of Alternating selection, bottom-up Alternating selection (or Alternating rejection), Zigzag selection, bottom-up Zigzag alternation, and fallback bargaining. The results suggest that fallback bargaining, the only simultaneous algorithm, satisfies most fairness and efficiency criteria but has some distinctive drawbacks.

We consider how the quality of possible allocations depends on the properties of the players’ preferences. Specifically, we examine how the rank correlation of preferences, as measured by Kendall Tau, relates to properties associated with fair allocation, such as the availability of envy-free, Pareto-optimal, maximin, and maximum Borda sum allocations. We also explore the relationship between rank correlation and features of fallback bargaining, such as the depth of agreement and the probability of a (two-way) tie. Furthermore, we categorize the players into two types—risk-averse and risk-acceptant—and analyze how player type affects various fair division properties. Our results, limited so far to the case of 4 items and 2 players, suggest that increasing similarity of preferences tends to increase the number of Pareto-optimal and maximin allocations while decreasing the number of envy-free allocations. Higher rank correlation also makes fallback bargaining less compelling.

Understanding how the similarity of preference rankings influences the trade-offs among allocation properties provides new insights into the difficulties of fair allocation of indivisible items with more items and more players. The fallback bargaining algorithm is suggested as a promising approach for achieving fairness by finding scenarios that satisfy both parties' interests as much as possible. However, a significant drawback emerges when a large number of items are to be allocated, as the length of the fallback bargaining input resembles a prolonged negotiation process. We introduce a novel approach aimed at accelerating the fallback bargaining algorithm, enhancing its overall performance and making it more applicable in real-world allocation scenarios.

Convocation Year

2025

Convocation Season

Spring

Share

COinS