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{{cite conference | url=http://portal.acm.org/citation.cfm?id=644145 | title=Competitiveness via Consensus | access-date=14 March 2016 | author=Andrew V. Goldberg, Jason D. Hartline | book-title=Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | year=2003 | conference=SODA 03}} and later extended to more general settings.{{cite journal|doi=10.1145/2465769.2465773|title=Mechanism Design via Consensus Estimates, Cross Checking, and Profit Extraction|journal=ACM Transactions on Economics and Computation|volume=1|issue=2|pages=1|year=2013|last1=Ha|first1=Bach Q.|last2=Hartline|first2=Jason D.|arxiv=1108.4744}}

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 it in the following way:

1. Ask the buyers to tell their valuations.
2. Calculate $R\_\{max\}$ - the maximum profit possible given the valuations.
3. Calculate a price that guarantees that we get a profit of $R\_\{max\}$.

Step 3 can be attained by a profit extraction mechanism, which is a truthful mechanism. However, in general the mechanism is not truthful, 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.{{Cite Algorithmic Game Theory 2007}}{{rp|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\}\; =\; \backslash lfloor\; R\_\{max\}\; \backslash 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\}\; =\; \backslash lfloor\; R\_\{max\}\; +\; U\; \backslash 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 disadvantages of using a consensus estimate are:

• It does not give us the optimal profit - but it gives us an approximately-optimal profit.
• It is not entirely truthful - it is only "truthful with high probability" (the probability that an agent can gain from deviating goes to 0 when the number of winning agents grows).{{rp|349}}

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.{{rp|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.