Narrow Results

In this paper, we consider how to maximize the liquid welfare in a combinatorial auction where bidders have monotone valuations and are budget constrained. We study the setting that budgets are public information and present a universally truthful, budget feasible and computationally-efficient randomized $O(\sqrt{mn})$-approximate mechanism, where $m$ is the number of items and $n$ is the number of bidders, respectively.