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. [1]:347

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:

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:

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:

randomly partition the bidders to two groups, such that each bidder has a chance of 1/2 to go to each group. Let R1 be the maximum revenue in group 1 and R2 the maximum revenue in group 2. Run R1-profit-extractor in group 2, and R2-profit-extractor in group 1.

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.[1]:348

2. Consensus estimate:

Calculate the maximum revenue in the entire population; apply a certain random rounding process that guarantees that the calculation is truthful with-high-probability. Let R be the estimated revenue; run R-profit-extractor in the entire population.

This mechanism guarantees a profit of at least 1/3.39 the maximum profit, in a digital goods auction.[1]:350

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). [2] The following mechanism is an approximate profit extractor:

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 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.[3] It was adapted from the cost-sharing literature to the auction setting.[4][5]

References

  1. 1 2 3 Jason D. Hartline and Anna R. Karlin, "Profit Maximization in Mechanism Design". Chapter 13 in Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva (2007). Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. ISBN 0-521-87282-0.
  2. Deshmukh, Kaustubh; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R. (2002). "Truthful and Competitive Double Auctions". Algorithms — ESA 2002. Lecture Notes in Computer Science. 2461. p. 361. doi:10.1007/3-540-45749-6_34. ISBN 978-3-540-44180-9.
  3. Moulin, Hervé; Shenker, Scott (2001). "Strategyproof sharing of submodular costs:budget balance versus efficiency". Economic Theory. 18 (3): 511. doi:10.1007/pl00004200.
  4. 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.
  5. Fiat, Amos; Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R. (2002). "Competitive generalized auctions". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing - STOC '02. p. 72. doi:10.1145/509907.509921. ISBN 1581134959.
This article is issued from Wikipedia - version of the 6/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.