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:

• Ask each agent how much he is willing to pay for the movie.
• For each integer ${\displaystyle k=1,2,...}$, let ${\displaystyle N_{k}}$ be the number of agents willing to pay at least ${\displaystyle R/k}$. Note that ${\displaystyle N_{k}}$ is weakly increasing with ${\displaystyle k}$.
• If there exists ${\displaystyle k}$ such that ${\displaystyle N_{k}\geq k}$, then find the largest such ${\displaystyle k}$ (which must be equal to ${\displaystyle N_{k}}$), sell the movie to these ${\displaystyle k}$ agents, and charge each such agent a price of ${\displaystyle R/k}$.
• If no such ${\displaystyle 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 ${\displaystyle k}$ weakly increases and the agent is still one of the ${\displaystyle k}$ highest bidders, so he still wins.
• A winning agent pays ${\displaystyle 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 ${\displaystyle R}$. Ideally, we would like ${\displaystyle 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:

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:

• Order the buyers by descending price and the sellers by ascending price.
• Find the largest ${\displaystyle k}$ such that ${\displaystyle k\cdot (b_{k}-s_{k})\geq R}$.
• The ${\displaystyle k-1}$ high-value buyers buy an item at price ${\displaystyle b_{k}}$. The ${\displaystyle k-1}$ low-cost sellers sell an item at price ${\displaystyle 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 ${\displaystyle (k-1)\cdot (b_{k}-s_{k})\geq {k-1 \over k}R}$, 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.[3] It was adapted from the cost-sharing literature to the auction setting.[4][5]

References

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