Resource Allocation Under Uncertainty

Effective resource allocation is a central challenge in operations research and economics. In practice, allocation decisions are often made under uncertainty, making it important to design mechanisms that perform well under different scenarios. From a practical point of view, it is also important that these mechanisms are easy to understand and implement in real-world settings. This dissertation explores decision-making in two problems of resource allocation under uncertainty in the domains of market design and revenue management. In the first part, we investigate an auction design problem where a seller aims to allocate a single item among multiple bidders with independent private values. In our setting, the seller has only limited information on the distribution of the bidders’ values in that they only know an upper bound on their values. The goal is to design a deterministic auction mechanism that performs well across a wide class of distributions. We propose a second-price auction with a reserve price equal to half of the upper bound. While no deterministic mechanism can guarantee
a positive fraction of the maximum achievable expected revenue across all possible distributions, we prove that our mechanism secures at least one-quarter of the maximum achievable expected revenue when bidders’ values are independent, and the guarantee improves to one-half under the additional assumption that the bidders’ values are identically distributed. Numerical experiments with randomly generated distributions show that our mechanism outperforms benchmarks from the literature in approximately 95% of the tested instances. We also account for estimation errors in the upper bound and demonstrate that a slight adjustment to the reserve price results in similar robustness guarantees. The second part studies the capacity allocation problem for a maritime asset provider who allocates vessel capacity between requests for capacity from contracted clients whose demand is uncertain but priced at pre-specified unit rates—and a spot market. Motivated by the operations of a major European ferry operator, we model the problem as an integer program with a concave objective function capturing expected revenues from both channels. We analyze a convex relaxation of the problem and characterize the optimality conditions, which reveal that optimal solutions equate the marginal revenues across contracted customers while ensuring these exceed or match the marginal revenue of the spot market. Building on this insight, we design a computationally efficient algorithm and prove that it yields optimal allocations. Using real data, we show that the algorithm consistently improves revenues in comparison to current practices of the ferry operator, with expected gains of 13% to 55% across sailings.