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/

Zendy Plus

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

Zendy Tools

Zendy Open

We show that every universally truthful randomized mechanism forcombinatorial auctions with submodular valuations that provides $m^{\frac 1 2-\epsilon}$ approximation to the social welfare and uses value queries onlymust use exponentially many value queries, where $m$ is the number of items. Incontrast, ignoring incentives there exist constant ratio approximationalgorithms for this problem. Our approach is based on a novel \emph{directhardness} approach and completely skips the notoriously hard characterizationstep. The characterization step was the main obstacle for proving impossibilityresults in algorithmic mechanism design so far.  We demonstrate two additional applications of our new technique: (1) animpossibility result for universally-truthful polynomial time flexiblecombinatorial public projects and (2) an impossibility result fortruthful-in-expectation mechanisms for exact combinatorial public projects. Thelatter is the first result that bounds the power of polynomial-time truthful inexpectation mechanisms in any setting.

An Impossibility Result for Truthful Combinatorial Auctions with Submodular Valuations