Misplaced Pages

Consensus estimate

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

Consensus estimate is a technique for designing truthful mechanisms in a prior-free mechanism design setting. The technique was introduced for digital goods auctions and later extended to more general settings.

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 m a x {\displaystyle R_{max}} - the maximum profit possible given the valuations.
  3. Calculate a price that guarantees that we get a profit of R m a x {\displaystyle 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 m a x {\displaystyle R_{max}} by bidding strategically. To solve this problem, we can replace the exact R m a x {\displaystyle R_{max}} with an approximation - R a p p {\displaystyle R_{app}} - that, with high probability, cannot be influenced by a single agent.

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 a p p = R m a x {\displaystyle R_{app}=\lfloor R_{max}\rfloor } = the value of R m a x {\displaystyle R_{max}} rounded to the nearest integer below it. Intuitively, in "most cases", a single agent cannot influence the value of R a p p {\displaystyle R_{app}} (e.g., if with true reports R m a x = 56.7 {\displaystyle R_{max}=56.7} , then a single agent can only change it to between R m a x = 56.6 {\displaystyle R_{max}=56.6} and R m a x = 56.8 {\displaystyle R_{max}=56.8} , but in all cases R a p p = 56 {\displaystyle R_{app}=56} ).

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

Such random variable R a p p {\displaystyle 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 m a x {\displaystyle 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).

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

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. arXiv:1108.4744. 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.
Category: