Constant Approximation for Private Interdependent Valuations

The celebrated model of auctions with interdependent valuations, introduced by Milgrom and Weber in 1982, has been studied almost exclusively under private signals $s_{1}, \ldots, s_{n}$ of the n bidders and public valuation functions $v_{i}\left(s_{1}, \ldots, s_{n}\right)$. Recent work in TCS has shown that this setting admits a constant approximation to the optimal social welfare if the valuations satisfy a natural property called submodularity over signals (SOS). More recently, Eden et al. (2022) have extended the analysis of interdependent valuations to include settings with private signals and private valuations, and established $O\left(\log ^{2} n\right)$-approximation for SOS valuations. In this paper we show that this setting admits a constant factor approximation, settling the open question raised by Eden et al. (2022).

Authors

• Alon Eden
• Michal Feldman
• Kira Goldner
• Simon Mauras
• Divyarthi Mohan

Keywords

• Computer science
• Cost accounting
• Constant Approximation
• Value Function
• Discretion
• Functional Properties
• True Value
• Data Privacy
• Normalization Factor
• Random Permutations
• Oilfield
• Amount Of Oil
• Power-of-two
• Signal Profiles
• Identical Items
• Allocation Rule
• Permutations Of Order
• truthful
• interdependent
• submodular