In several e-commerce applications, non-truthful auctions have been preferred
over truthful weakly dominant strategy ones partly because of their simplicity
and scalability. Although non-truthful auctions can have weaker incentive
constraints than truthful ones, the question of how much more revenue they can
generate than truthful auctions is not well understood. We study this question
for natural and broad classes of non-truthful mechanisms, including
quasi-proportional sharing and weakly monotonic auctions. Quasi-proportional
sharing mechanisms allocate to each bidder i an amount of resource proportional
to a monotonic and concave function f(b_{i}) where b_{i} is the
bid of bidder i and ask for a payment of b_{i}. Weakly monotonic auctions
refer to a more general class of auctions which satisfy some natural continuity
and monotonicity conditions.

We prove that although weakly monotonic auctions are much broader and require weaker incentive constraints than dominant strategy auctions, they are not more powerful with respect to the revenue in the setting of selling a single item. Furthermore, we show that quasi-proportional sharing with multiple bidders cannot guarantee a revenue that is larger than the second highest valuation, asymptotically as the number of bidders grows large. However, in a more general single-parameter setting modeled by a downward-closed set system, a version of the proportional sharing mechanism can obtain a constant factor of the optimal social welfare of the game where the highest valuation is replaced by the second highest valuation, which is essentially the best revenue benchmark in the prior-free framework. This is in sharp contrast to weakly dominant strategy mechanisms that cannot achieve better than log n approximation for this benchmark.

}, author = {Thanh Nguyen and Milan Vojnovic}, month = {April}, number = {MSR-TR-2011-48}, publisher = {Microsoft Technical Report}, title = {Near Optimal Non-truthful Auctions}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=147635}, year = {2011}, }