Profit extraction mechanism

Summarize Timeline Fact Check

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.

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