|
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 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: # Ask the buyers to tell their valuations. # Calculate R_ - the maximum profit possible given the valuations. # Calculate a price that guarantees that we get a profit of R_. 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_ by bidding strategically. To solve this problem, we can replace the exact R_ with an approximation - R_ - that, with ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Truthful Mechanism
In game theory, an asymmetric game where players have private information is said to be strategy-proof or strategyproof (SP) if it is a weakly-dominant strategy for every player to reveal his/her private information, i.e. given no information about what the others do, you fare best or at least not worse by being truthful. SP is also called truthful or dominant-strategy-incentive-compatible (DSIC), to distinguish it from other kinds of incentive compatibility. An SP game is not always immune to collusion, but its robust variants are; with group strategyproofness no group of people can collude to misreport their preferences in a way that makes every member better off, and with strong group strategyproofness no group of people can collude to misreport their preferences in a way that makes at least one member of the group better off without making any of the remaining members worse off. Examples Typical examples of SP mechanisms are majority voting between two alternatives, second- ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prior-free Mechanism Design
A prior-free mechanism (PFM) is a mechanism in which the designer does not have any information on the agents' valuations, not even that they are random variables from some unknown probability distribution. A typical application is a seller who wants to sell some items to potential buyers. The seller wants to price the items in a way that will maximize his profit. The optimal prices depend on the amount that each buyer is willing to pay for each item. The seller does not know these amounts, and cannot even assume that the amounts are drawn from a probability distribution. The seller's goal is to design an auction that will produce a reasonable profit even in worst-case scenarios. PFMs should be contrasted with two other mechanism types: * Bayesian-optimal mechanisms (BOM) assume that the agents' valuations are drawn from a known probability distribution. The mechanism is tailored to the parameters of this distribution (e.g, its median or mean value). * Prior-independent mechanisms ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Digital Goods Auction
In auction theory, a digital goods auction is an auction in which a seller has an unlimited supply of a certain item. A typical example is when a company sells a digital good, such as a movie. The company can create an unlimited number of copies of that movie in a negligible cost. The company's goal is to maximize its profit; to do this, it has to find the optimal price: if the price is too high, only few people will buy the item; if the price is too low, many people will buy but the total revenue will be low. The optimal price of the movie depends on the ''valuations'' of the potential consumers - how much each consumer is willing to pay to buy a movie. If the valuations of all potential consumers are known, then the company faces a simple optimization problem - selecting the price that maximizes the profit. For concreteness, suppose there is a set S of consumers and that they are ordered by their valuation, so that the consumer with the highest valuation (willing to pay the larg ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Profit Extraction Mechanism
In mechanism design and auction theory, a profit extraction mechanism (also called profit extractor or revenue extractor) is a truthful mechanism whose goal is to win a pre-specified amount of profit, if it is possible. Jason D. Hartline and Anna R. Karlin, "Profit Maximization in Mechanism Design". Chapter 13 in Profit extraction in a digital goods auction Consider a digital goods auction in which a movie producer wants to decide on a price in which to sell copies of his movie. A possible approach is for the producer to decide on a certain revenue, R, that he wants to make. Then, the ''R-profit-extractor'' works in the following way: * Ask each agent how much he is willing to pay for the movie. * For each integer k=1,2,..., let N_k be the number of agents willing to pay at least R/k. Note that N_k is weakly increasing with k. * If there exists k such that N_k\geq k, then find the largest such k (which must be equal to N_k), sell the movie to these k agents, and charge each suc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Random-sampling Mechanism
A random-sampling mechanism (RSM) is a truthful mechanism that uses sampling in order to achieve approximately-optimal gain in prior-free mechanisms and prior-independent mechanisms. Suppose we want to sell some items in an auction and achieve maximum profit. The crucial difficulty is that we do not know how much each buyer is willing to pay for an item. If we know, at least, that the valuations of the buyers are random variables with some known probability distribution, then we can use a Bayesian-optimal mechanism. But often we do not know the distribution. In this case, random-sampling mechanisms provide an alternative solution. RSM in large markets Market-halving scheme When the market is large, the following general scheme can be used: # The buyers are asked to reveal their valuations. # The buyers are split to two sub-markets, M_L ("left") and M_R ("right"), using simple random sampling: each buyer goes to one of the sides by tossing a fair coin. # In each sub-market M_s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |