Rahul Sharma (Editor)

Profit extraction mechanism

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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.

Contents

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 ≥ k , then find the largest such k (which must be equal to N k ), sell the movie to these k agents, and charge each such agent a price of R / k .
  • If no such k exists, then the auction is canceled and there are no winners.

    • This is a truthful mechanism. Proof: Since the agents have single-parametric utility functions, truthfulness is equivalent to monotonicity. The profit extractor is monotonic because:

  • If a winning agent increases his bid, then k weakly increases and the agent is still one of the k highest bidders, so he still wins.
  • A winning agent pays R / k , 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 R . Ideally, we would like R 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.

    Profit extraction in a double 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 (with different costs) and several buyers want at most a single unit of that item (with different valuations). The following mechanism is an approximate profit extractor:

  • Order the buyers by descending price and the sellers by ascending price.
  • Find the largest k such that k ⋅ ( b k − s k ) ≥ R .
  • The k − 1 high-value buyers buy an item at price b k . The k − 1 low-cost sellers sell an item at price s k .

    • The mechanism is truthful - this can be proved using a monotonicity argument similar to the digital-goods auction. The auctioneer's revenue is ( k − 1 ) ⋅ ( b k − s k ) ≥ k − 1 k R , which approaches the required revenue when it is sufficienly large.

    Combining this profit-extractor with a consensus-estimator gives a truthful double-auction mechanism which guarnatees 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.

    References

    Profit extraction mechanism Wikipedia
    (Text) CC BY-SA