Robust Budget Allocation

Abstract

We consider at the problem of optimal budget allocation, where we are given a fixed budget to distribute amongst sources in order to maximally influence targeted individuals. In practice, situations may arise where the influence process is unknown to us, motivating us to look at the robust budget allocation problem. In this setting, influence functions, which capture the expected number of influenced targets, are known only up to an uncertainty set and the goal is to find an allocation that maximizes the worst-case influence function. We extend the results of previous work on the related problem of robust submodular maximization to the integer lattice domain, formulating a polynomial-time algorithm approximation algorithm, SaturateDR. We prove hardness of approximation results for both the robust budget allocation problem as well as the bi-criteria approximation obtained by SaturateDR. Finally, we present experimental results that demonstrate our robust solution performs favorably in comparison to non-robust methods, with respect to influence obtained as well as runtime.