Maximize liquid welfare in combinatorial auctions with monotone valuations (Q6542876)

In this article, the authors study a public budget model where the auctioneer knows each bidder's budget. More precisely, the authors concentrate on finding mechanisms that satisfy the following properties: \N\begin{itemize}\N\item[i)] Universal truthful -- for any fixed outcome made by the random mechanism, reporting their true private information still is a dominant strategy.\N\item[ii)] Budget feasible -- the bidder will not pay more than his budget.\N\item[iii)] Computationally-efficient -- the mechanism can run in polynomial time.\N\end{itemize}\NA universal truthful, budget feasible and computationally-efficient mechanism for combinatorial auctions with monotone valuations that achieve an \(O(\sqrt{mn})\)-approximation to the maximum liquid welfare in expectation is presented. Approximation ratio of the mechanism is discussed in Section 4.