Swap regret
From Theory
Notes for CS 8803 - Game Theory and Computer Science. Spring 2008
Swap regret is a generalization of regret in the repeated n-decision game. (See the definition of the setting there.)
The decision-maker's swap-regret is defined to be:
|
Intuitively, it is how much one could improve by switching each occurence of decision i to the best decision j in hindsight, simultaneously for all decisions. Note that the swap regret, unlike regret, is always nonnegative.
Swap regret will be useful in computing correlated equilibrium.
The production of this material was supported in part by NSF award SES-0734780.
