On revenue monotonicity in combinatorial auctions

DOI10.1007/978-3-319-99660-8_1zbMATH Open1415.91146arXiv1709.03223OpenAlexW2963314002MaRDI QIDQ1617635

Could not fetch data.

Publication date: 8 November 2018

Abstract: Along with substantial progress made recently in designing near-optimal mechanisms for multi-item auctions, interesting structural questions have also been raised and studied. In particular, is it true that the seller can always extract more revenue from a market where the buyers value the items higher than another market? In this paper we obtain such a revenue monotonicity result in a general setting. Precisely, consider the revenue-maximizing combinatorial auction for $m$ items and $n$ buyers in the Bayesian setting, specified by a valuation function $v$ and a set $F$ of $nm$ independent item-type distributions. Let $REV(v,F)$ denote the maximum revenue achievable under $F$ by any incentive compatible mechanism. Intuitively, one would expect that $REV(v,G)geqREV(v,F)$ if distribution $G$ stochastically dominates $F$. Surprisingly, Hart and Reny (2012) showed that this is not always true even for the simple case when $v$ is additive. A natural question arises: Are these deviations contained within bounds? To what extent may the monotonicity intuition still be valid? We present an {approximate monotonicity} theorem for the class of fractionally subadditive (XOS) valuation functions $v$, showing that $REV(v,G)geqc,REV(v,F)$ if $G$ stochastically dominates $F$ under $v$ where $c>0$ is a universal constant. Previously, approximate monotonicity was known only for the case $n=1$: Babaioff et al. (2014) for the class of additive valuations, and Rubinstein and Weinberg (2015) for all subaddtive valuation functions.

Full work available at URL: https://arxiv.org/abs/1709.03223

zbMATH Keywords

mechanism designmaximum revenuesubadditive valuation

Mathematics Subject Classification ID

Auctions, bargaining, bidding and selling, and other market models (91B26)

This page was built for publication: On revenue monotonicity in combinatorial auctions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1617635)