Consensus estimate is a technique for designing truthful mechanisms in a prior-free mechanism design setting.
The technique was introduced for digital goods auctions[1] and later extended to more general settings.
[2] Suppose there is a digital good that we want to sell to a group of buyers with unknown valuations.
We want to determine the price that will bring us maximum profit.
Suppose we have a function that, given the valuations of the buyers, tells us the maximum profit that we can make.
However, in general the mechanism is not truthful, since the buyers can try to influence
To solve this problem, we can replace the exact
- that, with high probability, cannot be influenced by a single agent.
[3]: 349–350 As an example, suppose that we know that the valuation of each single agent is at most 0.1.
Intuitively, in "most cases", a single agent cannot influence the value of
To make the notion of "most cases" more accurate, define:
is a random variable drawn uniformly from
cannot be influenced by any single agent, so a mechanism that uses
is called a consensus estimate: The disadvantages of using a consensus estimate are: In practice, instead of rounding down to the nearest integer, it is better to use exponential rounding - rounding down to the nearest power of some constant.
[3]: 350 In the case of digital goods, using this consensus-estimate allows us to attain at least 1/3.39 of the optimal profit, even in worst-case scenarios.