English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study incentive compatible mechanisms for Combinatorial Auctions where thebidders have submodular (or XOS) valuations and are budget-constrained. Ourobjective is to maximize the \emph{liquid welfare}, a notion of efficiency forbudget-constrained bidders introduced by Dobzinski and Paes Leme (2014). Weshow that some of the known truthful mechanisms that best-approximate thesocial welfare for Combinatorial Auctions with submodular bidders throughdemand query oracles can be adapted, so that they retain truthfulness andachieve asymptotically the same approximation guarantees for the liquidwelfare. More specifically, for the problem of optimizing the liquid welfare inCombinatorial Auctions with submodular bidders, we obtain a universallytruthful randomized $O(\log m)$-approximate mechanism, where $m$ is the numberof items, by adapting the mechanism of Krysta and V\"ocking (2012).  Additionally, motivated by large market assumptions often used in mechanismdesign, we introduce a notion of competitive markets and show that in suchmarkets, liquid welfare can be approximated within a constant factor by arandomized universally truthful mechanism. Finally, in the Bayesian setting, weobtain a truthful $O(1)$-approximate mechanism for the case where biddervaluations are generated as independent samples from a known distribution, byadapting the results of Feldman, Gravin and Lucier (2014).

A Bridge between Liquid and Social Welfare in Combinatorial Auctions with Submodular Bidders