  In many natural settings agents participate in multiple different auctions
that are not simultaneous. In such auctions, future opportunities affect
strategic considerations of the players. The goal of this paper is to develop a
quantitative understanding of outcomes of such sequential auctions. In earlier
work (Paes Leme et al. 2012) we initiated the study of the price of anarchy in
sequential auctions. We considered sequential first price auctions in the full
information model, where players are aware of all future opportunities, as well
as the valuation of all players. In this paper, we study efficiency in
sequential auctions in the Bayesian environment, relaxing the informational
assumption on the players. We focus on two environments, both studied in the
full information model in Paes Leme et al. 2012, matching markets and matroid
auctions. In the full information environment, a sequential first price cut
auction for matroid settings is efficient. In Bayesian environments this is no
longer the case, as we show using a simple example with three players. Our main
result is a bound of $1+\frac{e}{e-1}\approx 2.58$ on the price of anarchy in
both matroid auctions and single-value matching markets (even with correlated
types) and a bound of $2\frac{e}{e-1}\approx 3.16$ for general matching markets
with independent types. To bound the price of anarchy we need to consider
possible deviations at an equilibrium. In a sequential Bayesian environment the
effect of deviations is more complex than in one-shot games; early bids allow
others to infer information about the player's value. We create effective
deviations despite the presence of this difficulty by introducing a bluffing
technique of independent interest.
