Abstract:

We consider a setting where an auctioneer sells a single item to n potential agents with {\em interdependent values}. That is, each agent has her own private signal, and the valuation of each agent is a function of all n private signals. This captures settings such as valuations for oil fields, broadcast rights, art, etc.

In the interdependent value setting, all previous work has assumed a so-called *single-crossing condition*. Single-crossing essentially means that one's own private signal has a greater effect on her valuation than on anyone else's valuation. Without single-crossing, one cannot maximize social welfare. We show that without single-crossing, effectively, the best one can do is to assign the item to a random bidder.

To the best of our knowledge, this is the first paper that deals with approximating social welfare without the single-crossing condition. We consider a relaxed version of single-crossing, c-single-crossing, with some parameter c (c=1 is single-crossing), and obtain many positive results.

These include a prior-free universally truthful \sqrt{n}c^{1.5}-approximation to welfare, and a prior-free deterministic (n-1)c-approximation to welfare. Under appropriate concavity conditions, we improve this to a prior-free universally truthful O(c)-approximation to welfare as well as a prior-free universally truthful O(c^2)-approximation to the optimal revenue.

Joint work with Alon Eden, Amos Fiat and Kira Goldner.