Robust Auctions for Resource Allocation

Didac Busquets, Universitat Girona

The problem of resource allocation is present in a wide range of applications, from assigning memory to processes in an operating system, to assigning machines to production processes in a factory, or distributing personnel to perform a set of tasks, among others. The algorithms developed to solve the resource allocation problem have focused on obtaining optimal solutions. That is, the solution has to fulfill a set of constraints, while maximizing or minimizing a given objective function (such as cost, makespan, etc.). However, sometimes obtaining the optimal solution is not the best choice, since it could fail in case the environment changed (a machine breaking down, a process taking longer than expected, etc). In such cases, it would be much better to have a robust solution that could be still applicable even if unexpected events occurred. Obviously, the price of robustness is optimality, since usually a robust solution will be suboptimal. Therefore, there is a need of balancing the optimality and the robustness of the solutions. In this seminar I will first present an auction-based approach to deal with the resource allocation problem, and then I will introduce how to add robustness to the obtained solutions.