Papers for

digital advertising auction teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Mechanism design achieves threefold approximate consumer surplus

Artificial Currency and Separate Selling: A 3-Approximation for Consumer Surplus

Abstract: We study the allocation of indivisible items to buyers with additive values drawn from independent distributions. The objective is consumer surplus net of burnt payments. We consider artificial-currency mechanisms: buyers receive personalized budgets of a currency worthless outside the mechanism and use them to bid across items. The better of separate selling and artificial-currency mechanisms provides a 3-approximation to optimal consumer surplus. The guarantee holds at every Bayes--Nash equilibrium, without equilibrium selection. Both branches are necessary: either alone may capture only a vanishing share of the optimum. The proof decomposes benchmark surplus into a stable part captured by artificial currency and a variation covered by separate selling.

Tue 10 NovComputer Science and Game Theory

The gist

This paper looks at how to give people different items based on how much they value them when those values are uncertain. The authors study a system where buyers receive fake money they can use only inside the system to bid on items. They show that using either selling items separately or this fake money system gets close to the best possible total happiness for buyers. Combining these two methods guarantees a result within three times the best, no matter how the buyers behave strategically. The proof breaks down the total value into parts that each method can handle well.

Open → 2611.14509v1