Swap regret

Short description: Concept of game theory

Swap regret is a concept from game theory. It is a generalization of regret in a repeated, n-decision game.

Definition

A player's swap-regret is defined to be the following:

[math]\displaystyle{ \mbox{swap-regret}= \sum_{i=1}^n \max_{j \leq n}\frac{1}{T}\sum_{t=1}^T x^t_i \cdot (p^t_j-p^t_i). }[/math]

Intuitively, it is how much a player could improve by switching each occurrence of decision i to the best decision j possible in hindsight. The swap regret is always nonnegative. Swap regret is useful for computing correlated equilibria.

References

• "From external to internal regret", Journal of Machine Learning Research 8: 1307–1324, 2007, http://www.jmlr.org/papers/volume8/blum07a/blum07a .