Auctions with interdependence and SOS: improved approximation (Q2670904)

The authors announce the existence of an ex post incentive compatible, individually rational randomized mechanism which achieves a tight 2-approximation to the optimal welfare in single-item auctions if bidders' valuation functions are submodular over their binary signals. This relates to results announced by \textit{A. Eden} et al. [``Combinatorial auctions with interdependent valuations: SOS to the rescue'', in: Proceedings of the 20th ACM Conference on Economics and Computation, EC'19. New York, NY: Association Computing Machinery. 19--20 (2019; \url{doi:10.1145/3328526.3329759})] where a 4-approximation to the optimal welfare is announced in a more general setting, and it is also stated that no truthful mechanism can achieve a better approximation factor than 2. The authors consider single-item auctions with \(n\) bidders. The private information about the item of bidder \(i\) is a binary signal \(s_{i} \in \{0, 1\}\). A signal profile \(s = (s_1, \dots , s_n)\) is identified with its corresponding set \(S = \{i | s_i = 1\}\). The valuation function of bidder \(i\) is a non-negative function of all bidders' signals \(v_i = v_i(s_1, \dots , s_n) \geq 0\). The valuation functions \(v_i\) are weakly increasing in each coordinate, strongly increasing in \(s_i\), and submodular: for every \(S, T \subseteq \{1,\dots,n\}\) with \(S \subseteq T\) and \(i \in \{1,\dots,n\}\setminus T\) it holds that \[ v_i(S \cup \{i\}) - v_i(S) \geq v_i(T \cup \{i\}) - v_i(T). \] While the signal \(s_i\) is known only to bidder \(i\), the valuation functions \(v_1,\dots,v_n\) are publicly known. A randomized mechanism \(M = (x, p)\) for interdependent values is a pair of allocation rule \(x= (x_1, \dots, x_n)\geq 0\) and payment rule \(p= (p_1, \dots, p_n)\). The mechanism solicits signal reports from the bidders, and maps a reported signal profile \(s\) to \(x\) and \(p\) such that \(\sum_{i=1}^{n}x_i(s) \leq 1\). \(M\) is ex post incentive compatible (IC) and individually rational (IR) if for every bidder \(i\), true signal profile \(s\) and reported signal \(s'_i\), \[ x_i(s_1,\dots, s_{i-1},s_{i}',s_{i+1},\dots,s_n)\cdot v_{i}(s)-p(s_1,\dots, s_{i-1},s_{i}',s_{i+1},\dots,s_n)\geq 0 \] and is maximized by \(s_{i}'=s_{i}\); that is, expected utility is non-negative and maximized by truthfully reporting. The mechanism \(M\) achieves a \(c\)-approximation to the optimal welfare for a given setting if for every signal profile \(s\), \[ \sum_{i=1}^{n}x_{i}(s)\cdot v_{i}(s) \geq c \cdot \max_{i}v_{i}(s). \] The authors announce the result that for every single-item auction with \(n\) bidders, binary signals, and valuations as above, there exists an ex post IC-IR mechanism that achieves a 2-approximation to the optimal welfare. The proof of this result is constructive: an algorithm is designed which gets as input the valuation functions \(v_1, \dots , v_n\), and outputs an allocation rule \(x\). The mechanism is randomized but uses only the \(0\) and \(1/2\) allocation probabilities. The authors extend their result to a matroid auction setting and state that if there exists a monotone feasible allocation rule that achieves a 2-approximation to the optimal welfare for single item auctions then there exists such an allocation rule for the matroid auction setting, as well. For the entire collection see [Zbl 1487.91002].