  For decision making under uncertainty, min-max regret has been established as
a popular methodology to find robust solutions. In this approach, we compare
the performance of our solution against the best possible performance had we
known the true scenario in advance. We introduce a generalization of this
setting which allows us to compare against solutions that are also affected by
uncertainty, which we call balanced regret. Using budgeted uncertainty sets,
this allows for a wider range of possible alternatives the decision maker may
choose from. We analyze this approach for general combinatorial problems,
providing an iterative solution method and insights into solution properties.
We then consider a type of selection problem in more detail and show that,
while the classic regret setting with budgeted uncertainty sets can be solved
in polynomial time, the balanced regret problem becomes NP-hard. In
computational experiments using random and real-world data, we show that
balanced regret solutions provide a useful trade-off for the performance in
classic performance measures.
