Consensus estimate

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. We can use in in the following way:

• Ask the buyers to tell their valuations.
• Calculate $R_{max}$ - the maximum profit possible given the valuations.
• Calculate a price that guarantees that we get a profit of $R_{max}$.

This algorithm is not strategyproof, since the buyers can try to influence $R_{max}$ by bidding strategically. To solve this problem, we can replace the exact $R_{max}$ with an approximation - $R_{app}$ - 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. As a first attempt of a consensus-estimate, let $R_{app} = \lfloor R_{max} \rfloor$ = the value of $R_{max}$ rounded to the nearest integer below it. Intuitively, in "most cases", a single agent cannot influence the value of $R_{app}$ (e.g, if with true reports $R_{max}=56.7$, then a single agent can only change it to between $R_{max}=56.6$ and $R_{max}=56.8$, but in all cases $R_{app}=56$).

To make the notion of "most cases" more accurate, define: $R_{app} = \lfloor R_{max} + U \rfloor$, where $U$ is a random variable drawn uniformly from $[0,1]$. This makes $R_{app}$ a random variable too. With probability at least 90%, $R_{app}$ cannot be influenced by any single agent, so a mechanism that uses $R_{app}$ is truthful with high probability.

Such random variable $R_{app}$ is called a consensus estimate:

• "Consensus" means that, with high probability, a single agent cannot influence the outcome, so that there is an agreement between the outcomes with or without the agent.
• "Estimate" means that the random variable is near the real variable that we are interested in - the variable $R_{max}$.

The disadvantage of using a consensus estimate is that it does not give us the optimal profit. However, it gives us an approximate profit.

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.

See also

• Random-sampling mechanism - an alternative approach to prior-free mechanism design.

References

1. Andrew V. Goldberg, Jason D. Hartline (2003). "Competitiveness via Consensus". Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 03. Retrieved 14 March 2016.
2. Ha, Bach Q.; Hartline, Jason D. (2013). "Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction". ACM Transactions on Economics and Computation 1 (2): 1. doi:10.1145/2465769.2465773.
3. Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.