It is well known that in any game and for any regret-minimizing dynamics the distribution of tuples of bids
approaches a “coarse correlated equilibrium” [1]}, [2]}, [3]} (CCE),
but as the space of CCE's
is quite wide, this often does not suffice for an analysis of parameters of interest like the revenue
or social welfare. For example, both for the first and second price auctions, there exist multiple
(full information) CCE's with different revenues and different social welfare [4]}.
One of the contributions of this work, presented in Section
, is the identification of a refinement of the class of CCE's which we term co-undominated,
to which a large class of regret-minimizing algorithms
(“Mean-Based” ones, as defined in [5]}) may only converge. In some cases
this refinement suffices for an analysis, and for specific regret-minimization algorithms like “Multiplicative Weights”
we may get an even finer analysis.
