CAREER: AF: New Algorithmic Foundations for Fair Division through Competitive Equilibrium

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Fair division is the age-old problem of allocating a set of (scarce) resources among several agents in a fair and efficient way. It arises naturally in a wide range of real-life settings such as dispute resolution, seats in courses/schools, computing-resources management, airport-traffic management, and spectrum allocation. Competitive equilibrium is a central solution concept in economics to study markets, and due to its remarkable fairness and efficiency properties, it is also one of the most preferred mechanisms for solving fair-division problems even though there may be no money involved in the latter case. With the advent of the Internet and the influence of computing systems on all parts of modern life, applications of fair division have grown immensely with a plethora of variants based on utility models, allocation constraints, and new fairness notions. The resulting equilibrium problems require complex constraints and generalizations so that most of the tools and techniques developed for markets in the last several decades do not seem to be applicable, and hence the corresponding fair-division problems remain unresolved. This project aims to explore many of these fundamental open questions. The project will support and engage both undergraduate and graduate students from diverse backgrounds and integrate the findings into multiple courses the investigator teaches. Unlike markets, in fair-division problems items are both goods (e.g., cake) and bads (e.g., chores), and allocation needs to satisfy additional constraints, e.g., students are assigned to exactly one school. The main research thrust of the project is to understand the structure and computational complexity of competitive equilibrium of (i) goods and bads, (ii) constrained allocation, (iii) divisible and indivisible items, and their various combinations. The challenges posed are of fundamental importance not only in fair division but also in equilibrium computation, mechanism design, and continuous and discrete optimization. Work on this project will bring significant algorithmic and complexity-theoretic insights into problems from these diverse areas. The techniques developed will contribute to the burgeoning literature on approximation, non-convex optimization, mathematical programming, scheduling, and auction theory, and will open up new avenues for further exploration. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.