  Interdependent values make basic auction design tasks -- in particular
maximizing welfare truthfully in single-item auctions -- quite challenging.
Eden et al. recently established that if the bidders valuation functions are
submodular over their signals (a.k.a. SOS), a truthful 4-approximation to the
optimal welfare exists. We show existence of a mechanism that is truthful and
achieves a tight 2-approximation to the optimal welfare when signals are
binary. Our mechanism is randomized and assigns bidders only 0 or 0.5
probabilities of winning the item. Our results utilize properties of submodular
set functions, and extend to matroid settings.
