  We study combinatorial auctions where each item is sold separately but
simultaneously via a second price auction. We ask whether it is possible to
efficiently compute in this game a pure Nash equilibrium with social welfare
close to the optimal one.
  We show that when the valuations of the bidders are submodular, in many
interesting settings (e.g., constant number of bidders, budget additive
bidders) computing an equilibrium with good welfare is essentially as easy as
computing, completely ignoring incentives issues, an allocation with good
welfare. On the other hand, for subadditive valuations, we show that computing
an equilibrium requires exponential communication. Finally, for XOS (a.k.a.
fractionally subadditive) valuations, we show that if there exists an efficient
algorithm that finds an equilibrium, it must use techniques that are very
different from our current ones.
