Algorithms for fair division through competitive equilibrium

McGlaughlin, Peter

Permalink

https://hdl.handle.net/2142/112976 Copy

Description

Title

Algorithms for fair division through competitive equilibrium

Author(s)

McGlaughlin, Peter

Issue Date

2021-06-30

Director of Research (if dissertation) or Advisor (if thesis)

Garg, Jugal

Doctoral Committee Chair(s)

Garg, Jugal

Committee Member(s)

• Beck, Carolyn
• Srikant, Rayadurgam
• Stolyar, Alexander

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

fair division, equilibrium computation, mixed manna

Abstract

I study the age old problem of fair and efficient resource allocation. While many fairness notions exist, competitive equilibrium (CE) is often the most preferred as it satisfies multiple other fairness properties simultaneously. The approach creates a fictitious market for the items by endowing agents with virtual currency. In an equilibrium, aggregate demand equals aggregate supply when agents purchase utility maximizing bundles. My work explores two main directions: algorithms for computing CE of mixed manna (goods and bads), and applications to the fair division of indivisible goods. First, I examine the problem of allocating a mixed manna under additively separable piecewise linear concave (SPLC) utilities. A mixed manna contains goods that everyone likes and bars that everyone dislikes, as well as items that some like and other dislike. The seminal work of Bogomolnaia et al. (’17) argues why allocating a mixed manna is genuinely more complicated than a good or bad manna, and why CE is the best mechanism. They also prove the existence of equilibrium and establish its peculiar properties, e.g., non-convex and disconnected set of equilibria even under linear utilities, but leave the problem of computing an equilibrium open. My main result is a simplex-like algorithm based on Lemke’s scheme for computing a competitive allocation of a mixed manna under SPLC utilities. Experimental results on randomly generated instances suggest the algorithm will be fast in practice. The problem is known to be PPAD-hard for the case of good manna, and I also show a similar result for the case of bad manna. Given these PPAD-hardness results, designing such an algorithm is the only non-brute-force (non-enumerative) option known, e.g., the classical Lemke-Howson algorithm for computing a Nash equilibrium in a two player game is still the most widely used algorithm. My algorithm also yields several new structural properties of CE as simple corollaries. I obtain constructive proof of existence for a far more general setting, membership of the problem in PPAD, rational-valued solution, and odd number of solutions property (settling a conjecture of Bogomolnaia et al. in the affirmative). Furthermore, I show that if either the number of agents or the number of items is constant, then the number of pivots in the algorithm is strongly polynomial when the mixed manna contains only bads, providing additional evidence to the practicality of my approach. Second, I focus on the case of indivisible goods. Various fairness notions have been proposed with the rapidly growing field of fair division, but the Nash social welfare (NSW) serves as a focal point. In part, this follows from the ‘unreasonable’ fairness guarantees provided, in the sense that a max NSW allocation meets multiple other fairness metrics simultaneously. However, existing approximation algorithms fail to satisfy all of the remarkable fairness guarantees offered by a max NSW allocation, instead targeting only the specific NSW objective. I address this issue by presenting a 2 max NSW, Prop-1, 1/(2n) MMS, and Pareto optimal allocation in strongly polynomial time. My techniques are based on a market interpretation of a fractional max NSW allocation. I present novel definitions of fairness concepts in terms of market prices, and design a new scheme to round a variation of a CE into an integral allocation in way that provides most of the fairness properties of an integral max NSW allocation.

Graduation Semester

2021-08

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/112976

Copyright and License Information

Copyright 2021 Peter McGlaughlin

Owning Collections