Simple combinatorial auctions with budget constraints (Q2006772)

The author studies the efficiency of auctions for the allocation of a set of discrete items to a set of budget-constrained agents with combinatorial preferences over the items, expressed via valuation functions. The following statement is precisely proved Lemma 1. Consider a player \(i\) with a subadditive valuation function \(\nu_i\) and budget \(c_i\). Let \(S\) be a set of items, and \(b_{-i}\) be the bid matrix containing the bids of the other players \(l\neq i\) for all items. Then, there exists a bid vector \(y_i = (y_i)_{j\in [m]}\) such that the utility of player \(i\) when she unilaterally deviates to \(y_i\) is \[ u_i(y_i,b_{-i})\ge \min \{\nu_i(S), c_i\}-\sum_{j\in S}\max_{l\neq i} b_{lj}, \] if her total payment does not exceed \(c_i\). Otherwise, \[ \min\{\nu_i(S),c_i\} <\sum_{j\in S}\max_{l\neq i} b_{lj}. \] Using this lemma, the author formulates the main result Theorem 1. The pure liquid price of anarchy of any auction in \(S\) with subadditive valuation functions is at most 2.