The missing element in this intuition is
that regret-minimization dynamics need not converge to a Nash equilibrium (or even a correlated
equilibrium) but may reach an arbitrary coarse correlated equilibrium, and it turns out that the first price auction also has other
coarse correlated equilibria [1]}, and in many of these coarse correlated
equilibria the revenue is well below the second price and sometimes even the low player wins.
While in [1]} these coarse correlated equilibria were analyzed in a continuous setting, they also
exist with simple discrete bidding levels. For example, consider an auction with \(v=w=1\) ;
the reader may verify that the distribution that gives equal weights to the following four
pairs of bids is a coarse correlated equilibrium: \(\lbrace (0,0), (0.46, 0.46), (0.64,0.64), (0.73,0.73)\rbrace \) .
It is true in general that for every CCE
there exist some regret-minimizing algorithms that converge to it. Specifically, in our setting, consider agents that start by playing a sequence of bids that converge to
the desired CCE (according to some some fixed-in-advance schedule), each
software agent
proceeds this way as long as the other agent does, and in the case of any deviation
reverts to a standard
regret-minimizing algorithm. Thus, regret-minimizing agents need not converge to the “second-price outcome”
in general. We are able to prove, however, that a large class of regret-minimizing algorithms,
defined in [3]} and
called “mean-based” algorithms, do so. Informally, algorithms from this class cannot put too much
probability on actions that previously performed poorly.
