The celebrated Interdependent values (IDV) model captures settings where buyers have partial information regarding their value for the item being sold. In the IDV model, each buyer $i$ has a private piece of information, a signal $s_i$, and their value is determined by all signals. This is represented by a valuation function $v_i(s_1, …, s_n)$. While this model is more realistic than the private values model (that assumes buyers know their value), it is much less understood. Most works in the IDV model assume that there’s only one type of item being sold, and that the valuation function $v_i$ is public information.
In this talk, I will present the first positive results relaxing these assumptions. In order to obtain these results, we identify an interesting condition on the structure in which information affects valuations—submodularity over signals. Using this condition, we obtain a mechanism that achieves a 4-approximation to general combinatorial auction settings, and $O(log^2 n)$-approximation to a single item auction, when the valuation $v_i$ is private information.
Based on joint works with Michal Feldman, Amos Fiat, Kira Goldner, Anna Karlin, and Shuran Zheng.