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

edit

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 exists   such that  , then find the largest such   (which must be equal to  ), 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.

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   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

edit

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

edit

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:

  • 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

edit

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

edit
  1. ^ a b c 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. Vol. 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. CiteSeerX 10.1.1.25.4285. 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.