Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids
<|reference_start|>Private Interdependent Valuations: New Bounds for Single-Item Auctions and Matroids: We study auction design within the widely acclaimed model of interdependent values, introduced by Milgrom and Weber [1982]. In this model, every bidder $i$ has a private signal $s_i$ for the item for sale, and a public valuation function $v_i(s_1,\ldots,s_n)$ which maps every vector of private signals (of all bidders) into a real value. A recent line of work established the existence of approximately-optimal mechanisms within this framework, even in the more challenging scenario where each bidder's valuation function $v_i$ is also private. This body of work has primarily focused on single-item auctions with two natural classes of valuations: those exhibiting submodularity over signals (SOS) and $d$-critical valuations.   In this work we advance the state of the art on interdependent values with private valuation functions, with respect to both SOS and $d$-critical valuations. For SOS valuations, we devise a new mechanism that gives an improved approximation bound of $5$ for single-item auctions. This mechanism employs a novel variant of an "eating mechanism", leveraging LP-duality to achieve feasibility with reduced welfare loss. For $d$-critical valuations, we broaden the scope of existing results beyond single-item auctions, introducing a mechanism that gives a $(d+1)$-approximation for any environment with matroid feasibility constraints on the set of agents that can be simultaneously served. Notably, this approximation bound is tight, even with respect to single-item auctions.<|reference_end|>
@article{eden2024private,
    title={Private Interdependent Valuations: New Bounds for Single-Item Auctions
  and Matroids},
    author={Alon Eden, Michal Feldman, Simon Mauras, Divyarthi Mohan},
    journal={arXiv preprint arXiv:2402.12017},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.12017},
    primaryClass={cs.GT cs.DS}
}