Essays In Optimization Methods For Resource Allocation

This dissertation proposes and investigates the use of mathematical programming techniques to solve resource allocation problems that are typically handled using other techniques. This approach both simplifies proofs of earlier results as well as extends them. The first setting addresses a network of agents, initially endowed with resources, exchanging goods and services via bilateral contracts. Under full substitutability of preferences, it is known via fixed point arguments that a competitive equilibrium exists in trading networks. I formulate the problem of finding an efficient set of trades as a generalized submodular flow problem in a suitable network. Existence of a competitive equilibrium follows directly from the optimality conditions of the flow problem. This formulation enables me to perform comparative statics with respect to the number of buyers, sellers, and trades. For instance, I establish that if a new buyer is added to the economy, at equilibrium the prices of all existing trades increase. In addition, a polynomial time algorithm for finding competitive equilibria in trading networks is given. The second setting relates to dynamic resource allocation with the presence of uncertainty for future rewards. Prophet inequalities involve a set of results relating the reward attained in an on-line selection setting to the reward generated by a prophet possessing perfect information. I develop new, approximately efficient rules leveraging the reduced-form representation of on-line selection problems. I apply the method in an on-line mechanism design problem with verification and the on-line fractional knapsack selection problem