About: Consensus estimate     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : owl:Thing, within Data Space : dbpedia.demo.openlinksw.com associated with source document(s)
QRcode icon
http://dbpedia.demo.openlinksw.com/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2FConsensus_estimate&invfp=IFP_OFF&sas=SAME_AS_OFF

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: Such random variable is called a consensus estimate:

AttributesValues
rdfs:label
  • Consensus estimate (en)
rdfs:comment
  • 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: Such random variable is called a consensus estimate: (en)
dcterms:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
sameAs
dbp:wikiPageUsesTemplate
has abstract
  • 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 - the maximum profit possible given the valuations. 3. * Calculate a price that guarantees that we get a profit of . 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 by bidding strategically. To solve this problem, we can replace the exact with an approximation - - 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 = the value of rounded to the nearest integer below it. Intuitively, in "most cases", a single agent cannot influence the value of (e.g., if with true reports , then a single agent can only change it to between and , but in all cases ). To make the notion of "most cases" more accurate, define: , where is a random variable drawn uniformly from . This makes a random variable too. With probability at least 90%, cannot be influenced by any single agent, so a mechanism that uses is truthful with high probability. Such random variable 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 . 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. (en)
prov:wasDerivedFrom
page length (characters) of wiki page
foaf:isPrimaryTopicOf
is Link from a Wikipage to another Wikipage of
is foaf:primaryTopic of
Faceted Search & Find service v1.17_git139 as of Feb 29 2024


Alternative Linked Data Documents: ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3330 as of Mar 19 2024, on Linux (x86_64-generic-linux-glibc212), Single-Server Edition (378 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software