ﻻ يوجد ملخص باللغة العربية
We provide the first separation in the approximation guarantee achievable by truthful and non-truthful combinatorial auctions with polynomial communication. Specifically, we prove that any truthful mechanism guaranteeing a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $exp(Omega(varepsilon^2 cdot m))$ communication, whereas a non-truthful algorithm by Dobzinski and Schapira [SODA 2006] and Feige [2009] is already known to achieve a $frac{3}{4}$-approximation in $poly(m)$ communication. We obtain our separation by proving that any {simultaneous} protocol ({not} necessarily truthful) which guarantees a $(frac{3}{4}-frac{1}{240}+varepsilon)$-approximation requires communication $exp(Omega(varepsilon^2 cdot m))$. The taxation complexity framework of Dobzinski [FOCS 2016] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).
We study a central problem in Algorithmic Mechanism Design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski, Nisan, and Schapira provided the first mechanism that guarantees a non
We consider the problem of fitting a linear model to data held by individuals who are concerned about their privacy. Incentivizing most players to truthfully report their data to the analyst constrains our design to mechanisms that provide a privacy
We consider a fundamental dynamic allocation problem motivated by the problem of $textit{securities lending}$ in financial markets, the mechanism underlying the short selling of stocks. A lender would like to distribute a finite number of identical c
We study the following communication variant of local search. There is some fixed, commonly known graph $G$. Alice holds $f_A$ and Bob holds $f_B$, both are functions that specify a value for each vertex. The goal is to find a local maximum of $f_A+f
We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1,