A Constant Approximation for Private Interdependent Valuations

The interdependent values model [Milgrom Weber '82] captures when one buyer's private information about an item impacts how much another buyer is willing to pay for it, and that without this information, a buyer may not know their own value.  While this model is more realistic than those which assume each buyer's value is fully known and independent from other buyers, it still assumes that the way in which each buyer aggregates the information (signals) about the item into a numerical value (their valuation function) is public information.

I will present recent work in the model where both a buyer's signal and valuation function are considered to be private information. In this setting, satisfying incentive-compatibility is not only challenging, but extremely non-trivial to do so while obtaining any sort of welfare-approximation.  I will discuss how the Submodularity-over-Signals (SOS) condition on valuations can be leveraged to obtain a constant-factor approximation to the optimal welfare.

Based on joint work with Alon Eden, Michal Feldman, Simon Mauras, and Divyarthi Mohan.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.