A theorem due to Scarf in 1967 is examined in detail. Several versions of this theorem exist, some which appear at first unrelated. Two versions can be shown to be equivalent to a result due to Sperner in 1928: for a proper labelling of the vertices in a simplicial subdivision of an n-simplex, there exists at least one elementary simplex which carries all labels {0,1,..., n}. A third version is more akin to Dantzig's simplex method and is also examined. In recent years many new applications in combinatorics have been found, and we present several of them. Two applications are in the area of fair division: cake cutting and rent partitioning. Two others are graph theoretic: showing the existence of a fractional stable matching in a hypergraph and the existence of a fractional kernel in a directed graph. For these last two, we also show the second implies the first.

A theorem due to Scarf in 1967 is examined in detail. Several versions of this theorem exist, some which appear at first unrelated. Two versions can be shown to be equivalent to a result due to Sperner in 1928: for a proper labelling of the vertices in a simplicial subdivision of an n-simplex, there exists at least one elementary simplex which carries all labels {0,1,..., n}. A third version is more akin to Dantzig's simplex method and is also examined. In recent years many new applications in combinatorics have been found, and we present several of them. Two applications are in the area of fair division: cake cutting and rent partitioning. Two others are graph theoretic: showing the existence of a fractional stable matching in a hypergraph and the existence of a fractional kernel in a directed graph. For these last two, we also show the second implies the first.

How should we divide a good or set of goods among a set of agents? There are various constraints that we can consider. We consider two particular constraints. The first is fairness - how can we find fair allocations? The second is truthfulness - what if we do not know agents valuations for the goods being allocated? What if these valuations need to be elicited, and agents will misreport their valuations if it is beneficial? Can we design procedures that elicit agents' true valuations while preserving the quality of the allocation? We consider truthful and fair resource allocation procedures through a computational lens. We first study fair division of a heterogeneous, divisible good, colloquially known as the cake cutting problem. We depart from the existing literature and assume that agents have restricted valuations that can be succinctly communicated. We consider the problems of welfare-maximization, expressiveness, and truthfulness in cake cutting under this model. In the second part of this dissertation we consider truthfulness in settings where payments can be used to incentivize agents to truthfully reveal their private information. A mechanism asks agents to report their private preference information and computes an allocation and payments based on these reports. The mechanism design problem is to find incentive compatible mechanisms which incentivize agents to truthfully reveal their private information and simultaneously compute allocations with desirable properties. The traditional approach to mechanism design specifies mechanisms by hand and proves that certain desirable properties are satisfied. This limits the design space to mechanisms that can be written down and analyzed. We take a computational approach, giving computational procedures that produce mechanisms with desirable properties. Our first contribution designs a procedure that modifies heuristic branch and bound search and makes it usable as the allocation algorithm in an incentive compatible mechanism. Our second contribution draws a novel connection between incentive compatible mechanisms and machine learning. We use this connection to learn payment rules to pair with provided allocation rules. Our payment rules are not exactly incentive compatibility, but they minimize a measure of how much agents can gain by misreporting. / Engineering and Applied Sciences