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, let be the number of agents willing to pay at least. Note that is weakly increasing with.
If there existssuch that, then find the largest such , sell the movie to these agents, and charge each such agent a price of.
If no such exists, then the auction is canceled and there are no winners.
If a winning agent increases his bid, then weakly increases and the agent is still one of the highest bidders, so he still wins.
A winning agent pays, which is exactly the threshold price - the price under which the bid stops being a winner.
Estimating the maximum revenue
The main challenge in using an auction based on a profit-extractor is to choose the best value for the parameter. Ideally, we would like to be the maximum revenue that can be extracted from the market. However, we do not know this maximum revenue in advance. We can try to estimate it using one of the following ways: 1. Random sampling: This mechanism guarantees a profit of at least 1/4 the maximum profit. A variant of this mechanism partitions the agents to three groups instead of two, and attains at least 1/3.25 of the maximum profit. 2. Consensus estimate: This mechanism guarantees a profit of at least 1/3.39 the maximum profit, in a digital goods auction.
The profit-extraction idea can be generalized to arbitrary single-parameter utility agents. In particular, it can be used in a double auction where several sellers sell a single unit of some item and several buyers want at most a single unit of that item. The following mechanism is an approximate profit extractor:
Order the buyers by descending price and the sellers by ascending price.
Find the largest such that.
The high-value buyers buy an item at price. The low-cost sellers sell an item at price.
The mechanism is truthful - this can be proved using a monotonicity argument similar to the digital-goods auction. The auctioneer's revenue is, which approaches the required revenue when it is sufficiently large. Combining this profit-extractor with a consensus-estimator gives a truthful double-auction mechanism which guarantees a profit of at least 1/3.75 of the maximum profit.
History
The profit extractor mechanism is a special case of a cost sharing mechanism. It was adapted from the cost-sharing literature to the auction setting.
