Choice Functions, Digraphs, and Balanced Allocations

Abstract

In this thesis, we consider broadly the concept of choice in a variety of settings, focusing on equity in selection. In particular, we introduce the concept of (pair-wise) domination graphs for hypergraphs endowed with a choice function on edges, and are interested, for instance, in minimal numbers of edges for associated domination graphs. Theorems regarding the existence of balanced (zero-edge) domination graphs are presented. In addition, we consider fairness for choice functions, from a sequential perspective, prove existence of fair choice, and consider connections with balanced allocation, path-connected directed graphs and cyclic preference. Several open questions are posed.