Profit Maximization in Mechanism Design

Motivation: the designer wants money, not welfare

Mechanism design so far has usually maximized social welfare. But the party running the auction generally wants profit, and the two objectives are genuinely different — the whole subject is about the gap between them.

ExampleWhere efficiency and revenue part ways

A single item, one bidder with value drawn uniformly from $[0,1]$ . Efficient: give the item away for free, achieving welfare $\mathbb{E}[v]=1/2$ but zero revenue. Optimal for revenue: post a take-it-or-leave-it price of $1/2$ , earning $1/2\cdot1/2=1/4$ in expectation — but the item goes unsold half the time, and expected welfare falls to $3/8$ .

Revenue maximization deliberately destroys welfare. Understanding by how much, and how, is the content of this note.

ImportantTwo complementary settings

	Bayesian	Prior-free
Assumption	valuations drawn from a known distribution $F$	no distributional assumption at all
Goal	maximize expected revenue exactly	compete with a benchmark on every input
Tool	virtual valuations, Myerson’s auction	random sampling, competitive analysis
Result shape	an exactly optimal mechanism	a constant-factor approximation

The prior-free approach is the natural home of the worst-case analysis tradition in computer science; the Bayesian one is classical economics. Both reduce to the same underlying monotonicity characterization from introduction-to-mechanism-design.

ConventionThe setting throughout

$n$ bidders, each with a private value $v_i$ for winning. A mechanism has an allocation rule $x_i(v)\in\{0,1\}$ (or a probability) and a payment rule $p_i(v)$ ; utility is $u_i = v_ix_i(v) - p_i(v)$ . We restrict attention to single-parameter settings, where a bidder’s private information is the scalar $v_i$ and the feasible allocations are given by a known feasibility constraint — one winner for a single-item auction, any subset for a digital good, and so on.

Bayesian optimal mechanism design

Myerson’s characterization

TheoremMyerson’s lemma

A mechanism with allocation rule $x$ is truthful (dominant-strategy incentive compatible) if and only if

$x_i(v_i,v_{-i})$ is monotone nondecreasing in $v_i$ , and
the payment satisfies $p_i(v_i,v_{-i}) = v_ix_i(v_i,v_{-i}) - \int_0^{v_i}x_i(t,v_{-i})\,dt$ (up to an additive constant, fixed to zero by requiring a bidder with value 0 to pay 0).

NoteThis is the single-parameter characterization

It is exactly the randomized single-parameter theorem from introduction-to-mechanism-design, restated for this chapter’s notation. The allocation rule determines the payments, so designing a revenue-maximizing mechanism means designing an allocation rule — the payments follow.

DerivationExpected revenue as expected virtual surplus

Let $F_i$ be bidder $i$ ‘s value distribution with density $f_i$ , supported on $[0,h]$ . Taking the expectation of the payment formula over $v_i\sim F_i$ and integrating by parts:

$\mathbb{E}_{v_i}\big[p_i(v)\big] = \mathbb{E}_{v_i}\left[v_ix_i(v) - \int_0^{v_i}x_i(t,v_{-i})dt\right] = \mathbb{E}_{v_i}\left[\left(v_i - \frac{1-F_i(v_i)}{f_i(v_i)}\right)x_i(v)\right]$

The interchange of the two integrals is the whole step: the double integral $\int_0^h f_i(v)\int_0^v x_i(t)\,dt\,dv$ becomes $\int_0^h x_i(t)\big(1-F_i(t)\big)dt$ when the order is swapped.

DefinitionVirtual valuation

$\varphi_i(v_i) = v_i - \frac{1-F_i(v_i)}{f_i(v_i)}$

Then $\mathbb{E}_v\big[\sum_ip_i(v)\big] = \mathbb{E}_v\big[\sum_i\varphi_i(v_i)x_i(v)\big]$ .

ImportantThe reduction, stated plainly

Expected revenue equals expected virtual welfare. So the revenue-maximizing mechanism is the welfare-maximizing mechanism run on the virtual valuations instead of the real ones — provided the resulting allocation rule is monotone.

Everything we know about efficient mechanism design transfers, with $\varphi_i$ substituted for $v_i$ .

IntuitionReading the virtual valuation

$\varphi_i(v_i)$ is the bidder’s value minus his information rent — the amount the seller must concede to keep him truthful. The term $(1-F_i(v_i))/f_i(v_i)$ is the inverse hazard rate: it is large when there is a lot of probability mass above $v_i$ relative to the density at $v_i$ , i.e. when the bidder could plausibly have had a much higher value and so must be paid to reveal that he does not.

Note $\varphi_i(v_i)$ can be negative — for $v_i$ small enough that the rent exceeds the value. Allocating to such a bidder loses money, which is exactly why the optimal auction withholds the item.

DefinitionRegularity and monotone hazard rate

$F_i$ is regular if $\varphi_i$ is monotone nondecreasing. It satisfies the monotone hazard rate (MHR) condition if $f_i(v)/(1-F_i(v))$ is nondecreasing; MHR implies regular, and most textbook distributions (uniform, exponential, normal) satisfy it.

ExampleThe uniform distribution

For $v_i\sim U[0,1]$ : $F(v)=v$ , $f(v)=1$ , so

$\varphi(v) = v - \frac{1-v}{1} = 2v-1$

This is increasing, so $U[0,1]$ is regular. The virtual value is negative exactly for $v<1/2$ — recovering the reserve price of the opening example.

Myerson’s optimal auction

TheoremThe optimal single-item auction

For regular distributions, the expected-revenue-maximizing truthful auction allocates to the bidder with the highest nonnegative virtual value, and allocates to nobody if all virtual values are negative. Payments are given by Myerson’s lemma — equivalently, the winner pays the smallest value he could have declared and still won.

ProofRegularity makes virtual-welfare maximization monotone

By the derivation, expected revenue is expected virtual welfare, so pointwise maximizing $\sum_i\varphi_i(v_i)x_i(v)$ over feasible allocations maximizes revenue among all rules. Since each $\varphi_i$ is nondecreasing (regularity), raising $v_i$ raises $\varphi_i(v_i)$ and can only help $i$ win, so the rule is monotone — and Myerson’s lemma then supplies truthful payments.

∎

ExampleI.i.d. uniform bidders: a second price auction with reserve

With all $v_i\sim U[0,1]$ , the virtual values are $2v_i-1$ , and maximizing the largest nonnegative one is the same as maximizing $v_i$ subject to $v_i\ge1/2$ . So the optimal auction is the second price auction with a reserve price of $1/2$ : the highest bidder above $1/2$ wins and pays the larger of the second highest bid and $1/2$ .

ImportantThree structural lessons

(1) With i.i.d. regular bidders, the optimal auction is always a second price auction with a reserve price — the reserve being $\varphi^{-1}(0)$ , the value at which the virtual value turns nonnegative. It does not depend on $n$ .

(2) With non-identical distributions the optimal auction discriminates. Maximizing $\varphi_i(v_i)$ rather than $v_i$ means a bidder from a “weaker” distribution can win against a higher actual bid. The optimal auction is therefore not efficient, and deliberately so.

(3) The reserve price matters more than the competition. A classical observation is that running a second price auction with one extra bidder yields at least as much revenue as the optimal auction with the original $n$ — so attracting participation is worth more than optimizing the mechanism.

NoteIrregular distributions: ironing

If $\varphi_i$ is not monotone, virtual-welfare maximization gives a non-monotone allocation rule, which is not implementable. Ironing replaces $\varphi_i$ with its “monotone hull”: integrate $\varphi_i$ to get a function of $q = F_i(v)$ , take the convex hull of that curve from below, and differentiate the hull to obtain the ironed virtual valuation $\bar\varphi_i$ . Maximizing $\bar\varphi_i$ -welfare is monotone, hence implementable, and yields the same expected revenue as the unironed objective. Over the intervals where ironing is active, the mechanism allocates by a tie-break that ignores the actual values.

WarningThe two costs of the Bayesian approach

It requires knowing $F$ , precisely and as common knowledge. In practice the designer often does not, and the optimal auction is sensitive to the prior — an incorrect reserve price loses revenue.

It is a per-instance-in-expectation guarantee, not a per-instance one. On any particular realization the mechanism may do badly.

These two objections are what motivate the prior-free program.

Prior-free approximation: the benchmark problem

The setup. Drop all distributional assumptions. The mechanism sees only the bid vector $v$ and must perform well on every input. The immediate difficulty is deciding what “well” means.

WarningThe obvious benchmark is unachievable

Compare against $\mathcal{V} = \max_i v_i$ , the maximum revenue extractable by an omniscient seller who knows all the values? No truthful mechanism gets within any factor of this. With one bidder, extracting close to $v_1$ requires charging close to $v_1$ , which a truthful mechanism cannot do without knowing $v_1$ — and knowing $v_1$ requires asking, which destroys truthfulness.

So the benchmark must be weakened. The question is by exactly how much.

DefinitionThe single-price benchmarks

Order the bids $v_1\ge v_2\ge\cdots\ge v_n$ . The optimal single-price revenue is

$\mathcal{F}(v) = \max_{i}\ i\cdot v_i$

— the best revenue from posting one take-it-or-leave-it price to everyone. The restricted version excludes the top bidder:

$\mathcal{F}^{(2)}(v) = \max_{i\ge2}\ i\cdot v_i$

ImportantWhy $\mathcal{F}^{(2)}$ is the right benchmark

$\mathcal{F}$ itself is still unachievable: on the input $(v_1,\epsilon,\ldots)$ it reduces to the one-bidder impossibility above. $\mathcal{F}^{(2)}$ excludes exactly that degenerate case — it requires at least two winners, so there is always a second bidder whose value provides usable information.

The analogy with the single-item case is exact: just as no auction beats the highest value but the second price auction gets the second highest, $\mathcal{F}^{(2)}$ is the profit benchmark obtainable by learning from the competition.

DefinitionCompetitive ratio

A truthful mechanism $M$ is $\beta$ -competitive if for every bid vector,

$\mathbb{E}\big[\text{revenue of }M(v)\big]\ \ge\ \frac{\mathcal{F}^{(2)}(v)}{\beta}$

the expectation over the mechanism’s own coin flips. (This is worst-case analysis in the computer science tradition, with $\mathcal{F}^{(2)}$ playing the role of the offline optimum.)

Random sampling

The idea. The obstacle is that a truthful mechanism cannot use a bidder’s own bid to set his price. The resolution: split the bidders into two groups, and use each group’s bids to price the other.

AlgorithmRandom Sampling Optimal Price (RSOP)

Assign each bidder independently and uniformly at random to $A$ or $B$ .
Compute $p_A = \arg\max_p(\text{revenue of price } p \text{ on } A)$ and likewise $p_B$ .
Offer price $p_B$ to every bidder in $A$ , and price $p_A$ to every bidder in $B$ .

ProofRSOP is truthful

Fix bidder $i\in A$ . His price is $p_B$ , computed entirely from bids in $B$ , so it is independent of $v_i$ ; he wins iff $v_i\ge p_B$ . This is a posted price from $i$ ‘s perspective, and posted prices are truthful. Symmetrically for $B$ . Since the partition is also independent of the bids, truthfulness holds for every realization — RSOP is universally truthful, not merely truthful in expectation.

∎

IntuitionWhy it should work, and where it can fail

Each half is a random sample of the population, so the optimal price on $A$ should be nearly optimal on $B$ and vice versa. The failure mode is imbalance: if the high-value bidders land disproportionately in one half, that half’s price is badly wrong for the other.

The analysis is essentially a concentration argument, and the difficulty is that the revenue is a maximum over prices, so a union bound over prices is needed.

TheoremRSOP is competitive

RSOP is $\beta$ -competitive for a constant $\beta$ . The best known bound is 4, and the worst case known is $\approx 2.42$ — attained in the limit on inputs with two distinct bid values.

NoteThe state of the analysis

The original analysis gave a large constant; successive refinements brought it to 4, and closing the gap to 2.42 is open. The lower bound comes from a two-valued input on which the random partition is imbalanced with constant probability.

WarningThe single-price restriction is not free

RSOP competes with $\mathcal{F}^{(2)}$ , the best single-price revenue. An omniscient seller charging personalized prices earns $\sum_iv_i$ , which can be arbitrarily larger. We have weakened the benchmark twice — once to single prices, once to exclude the top bidder — and both weakenings are necessary.

Prior-free optimal mechanism design

The refinement. Competitive analysis asks for a constant-factor guarantee. Prior-free optimal design asks for the best possible mechanism — the one minimizing the competitive ratio — and requires a different technique.

The decision problem

ImportantReducing profit maximization to a decision

Fix a target revenue $R$ and ask: can we extract revenue $R$ ? If we can solve this decision problem truthfully, a search over $R$ gives a profit-maximizing mechanism.

The key subroutine is profit extraction: given a target $R$ , find a set of bidders willing to share the cost $R$ equally.

AlgorithmProfit extraction (cost sharing)

Given a target $R$ , find the largest $k$ such that the top $k$ bidders each have value at least $R/k$ , and charge each of them $R/k$ . If no such $k$ exists, allocate to nobody and earn zero.

This is the Moulin–Shenker cost-sharing mechanism applied to a fixed cost $R$ .

ProofProfit extraction is truthful, and extracts

R

when it can

The set of winners and the price are determined by the standard cost-sharing descending-price argument: lowering one’s bid can only remove one from the winning set (never lower the price), and raising it can only add one at a price he has already declared acceptable. It extracts exactly $R$ whenever $\mathcal{F}(v)\ge R$ — some price $p=R/k$ has $k$ bidders above it.

∎

IntuitionThe composition

Profit extraction turns “how much can we make?” into “guess a target, then extract it.” The whole difficulty moves into choosing the target truthfully — which is where consensus estimates come in.

Consensus estimates

DefinitionConsensus estimate

A function $\hat R$ of the bids is a consensus estimate of $\mathcal{F}^{(2)}$ if, with high probability, every bidder’s exclusion leaves it unchanged: $\hat R(v) = \hat R(v_{-i})$ for all $i$ simultaneously.

ImportantWhy consensus is exactly what is needed

If the target $R$ is the same whether or not bidder $i$ participates, then from $i$ ‘s perspective the target is exogenous — so profit extraction at that target is truthful for him. Consensus is the prior-free substitute for the distributional independence that made random sampling work.

AlgorithmConsensus estimation by randomized rounding

Pick $\alpha$ uniformly at random from $[0,1)$ and round $\mathcal{F}^{(2)}(v)$ down to the nearest power of a base $c$ , offset by $\alpha$ :

$\hat R(v) = c^{\lfloor \log_c\mathcal{F}^{(2)}(v) - \alpha\rfloor + \alpha}$

Since removing a bidder changes $\mathcal{F}^{(2)}$ by a bounded multiplicative factor, the rounded value is unchanged unless the offset happens to fall in a narrow window — which occurs with probability proportional to $\log_c(\text{the change})$ .

AlgorithmConsensus Revenue Estimate (CORE)

Compute the consensus estimate $\hat R$ , then run profit extraction at target $\hat R$ . If consensus fails, the mechanism earns nothing on that run.

TheoremCORE and the optimal ratio

The CORE family of mechanisms achieves a competitive ratio approaching the optimal one for the benchmark $\mathcal{F}^{(2)}$ . The optimal ratio is known exactly for small $n$ — it is 2 for $n=2$ — and approaches a constant around 3.24 as $n\to\infty$ .

NoteThe lower bound technique

The impossibility side comes from an averaging argument over a distribution of inputs: construct a distribution on bid vectors such that every truthful mechanism has expected revenue at most $1/\beta$ times the expected $\mathcal{F}^{(2)}$ . Since a truthful mechanism’s revenue is pinned down by its allocation rule (Myerson’s lemma again), this becomes an optimization over monotone allocation rules — which is precisely the Bayesian machinery used in reverse, to prove a prior-free impossibility.

ImportantThe unifying observation

Prior-free optimal design and Bayesian optimal design are two views of the same object. The optimal prior-free mechanism is, in a precise sense, the Bayesian optimal mechanism for the worst-case prior — the distribution that makes the designer’s problem hardest. The connection runs through Myerson’s lemma in both directions.

Applications

Digital goods

DefinitionThe digital good auction

A seller with unlimited supply — copies of software, a downloadable file, pay-per-view — faces $n$ bidders, each wanting one copy. Feasibility imposes no constraint: any subset may win.

ImportantWhy this is the canonical case

With unlimited supply there is no allocation problem at all — the entire question is pricing, so the setting isolates revenue maximization from every other concern. Everything above was implicitly stated for it: $\mathcal{F}$ and $\mathcal{F}^{(2)}$ are the natural benchmarks, RSOP applies directly, and CORE gives the optimal ratio.

In the Bayesian version with i.i.d. bidders, the optimal mechanism is simply the monopoly price $\arg\max_p\ p(1-F(p))$ posted to everyone — the virtual-value condition $\varphi(p)=0$ rearranges to exactly the monopolist’s first-order condition.

Multicast pricing

DefinitionThe multicast setting

A rooted tree network; users at the leaves each have a private value for receiving a transmission. Serving a user requires paying for every edge on the path from the root, and edges are shared — once paid for, an edge serves all users below it.

The mechanism must choose a set of users to serve and prices to charge, covering the cost of the induced subtree and maximizing the surplus.

ImportantWhere the shared cost changes the problem

This is a cost-sharing problem layered on top of profit maximization: the “cost” of serving a user depends on which other users are served. Two requirements pull apart:

Budget balance: payments cover the cost of the transmitted subtree.
Efficiency: serve the users whose values exceed the marginal cost.

No truthful mechanism achieves both, which is the Myerson–Satterthwaite-flavour impossibility for this setting. The Moulin–Shenker cost-sharing mechanism — essentially the profit extractor above, applied recursively up the tree — gives budget balance and a logarithmic approximation to efficiency.

NoteConnection to the rest of the note

The profit extractor used in CORE is a cost-sharing mechanism with a fixed cost; multicast is the case where the cost function is induced by a network. See cost-sharing for the general treatment.

Frugality

The reverse direction. In a procurement auction the mechanism buys rather than sells: agents own resources and have private costs, and the mechanism must purchase a feasible set. The objective flips — the designer now wants to pay as little as possible.

DefinitionThe setting

A set system: agents $1,\ldots,n$ with private costs $c_i$ , and a collection of feasible sets the mechanism may hire (e.g. all $s$ – $t$ paths in a graph, all spanning trees). A truthful mechanism selects a feasible set and pays each hired agent.

The canonical mechanism is VCG: hire the cheapest feasible set, and pay each hired agent his threshold bid — the highest cost at which he would still be hired.

ExampleVCG can overpay badly

Two parallel $s$ – $t$ paths, one of cost 1 and one of cost $1+\epsilon$ . VCG hires the cheap one and pays $1+\epsilon$ — fine. But now make the cheap path a single edge of cost 1 and the expensive path $k$ edges each of cost $1/k+\epsilon'$ . VCG hires the single edge and pays it the full $1+k\epsilon'$ .

Worse: with two parallel single edges of costs $1$ and $B$ for large $B$ , VCG pays $B$ for a resource worth 1. The payment is governed by the absence of competition, not by the cost.

DefinitionFrugality ratio

The frugality of a mechanism is the worst-case ratio of its total payment to some benchmark measuring the “fair” cost of the purchased set. The naive benchmark — the cost of the cheapest feasible set — is wrong, since with genuinely no competition any truthful mechanism must overpay.

DefinitionThe $\nu$ benchmark

Let $S$ be the cheapest feasible set. Define $\nu(c)$ as the value of the following: find payments $b_i\ge c_i$ to the members of $S$ such that

$S$ is a cheapest feasible set at the payments $b$ , and
each member of $S$ is paid the minimum consistent with that.

$\nu(c) = \sum_{i\in S}b_i$ . This is the smallest total payment at which the hired set can still be justified as the winner, a Nash-equilibrium-style benchmark rather than a cost.

IntuitionWhat $\nu$ captures

It measures how much the structure of competition forces the buyer to pay, independent of any particular mechanism. In the two-parallel-edges example with costs $1$ and $B$ , $\nu = B$ — VCG is perfectly frugal there, and the apparent overpayment is intrinsic to the market, not a flaw of the mechanism.

The benchmark thus separates unavoidable overpayment from mechanism-specific waste, which is exactly what a frugality theory needs.

TheoremFrugality results

Set system	VCG frugality	Best known truthful
Spanning trees	1 — VCG is optimally frugal	1
$s$ – $t$ paths	$\Theta(n)$ in the worst case	$\Theta(\sqrt n)$ by a randomized mechanism, and $\Omega(\sqrt n)$ is a lower bound
Vertex cover	unbounded relative to $\nu$	constant-factor mechanisms exist

ImportantWhy paths and trees differ so sharply

For spanning trees the feasible sets form a matroid, and matroid structure makes the threshold payments tight — swapping one edge out admits exactly one replacement, so competition is local and VCG pays the right amount.

For paths there is no matroid structure: removing one edge from a path may require replacing the entire path, so a single edge can hold up the whole purchase. The $\sqrt n$ gap between VCG and the optimum reflects exactly this lack of exchange structure.

NoteOpen directions

Characterizing the set systems for which VCG is frugal, and determining the optimal frugality ratio for general systems, remain open. The connection to matroid structure is suggestive but not a complete characterization.

Quick reference

Object	Statement
Myerson’s lemma	truthful $\iff$ monotone $x_i$ and $p_i = v_ix_i - \int_0^{v_i}x_i(t)dt$
Virtual valuation	$\varphi_i(v) = v - \frac{1-F_i(v)}{f_i(v)}$
Revenue identity	$\mathbb{E}[\sum_ip_i] = \mathbb{E}[\sum_i\varphi_i(v_i)x_i]$
Optimal auction	maximize virtual welfare; allocate only to nonnegative $\varphi_i$
Regular / MHR	$\varphi_i$ nondecreasing; MHR $\Rightarrow$ regular
I.i.d. regular case	second price auction with reserve $\varphi^{-1}(0)$
Irregular case	ironing — convex hull of the integrated virtual value
Bulow–Klemperer flavour	one extra bidder beats optimizing the mechanism
$\mathcal{F}(v)$	$\max_i\ i\cdot v_i$ — best single price; unachievable
$\mathcal{F}^{(2)}(v)$	$\max_{i\ge2}\ i\cdot v_i$ — the prior-free benchmark
RSOP	random halves price each other; universally truthful; 4-competitive, lower bound 2.42
Profit extraction	largest $k$ with top $k$ bids $\ge R/k$ ; each pays $R/k$
Consensus estimate	$\hat R(v) = \hat R(v_{-i})$ w.h.p.; randomized rounding to offset powers of $c$
CORE	consensus estimate $+$ profit extraction; approaches the optimal ratio $\approx3.24$
Digital goods	unlimited supply; pure pricing problem; Bayesian answer is the monopoly price
Multicast	shared edge costs; budget balance and efficiency are incompatible
Frugality benchmark $\nu$	minimum payments at which the hired set is still cheapest
Frugality of VCG	1 for spanning trees (matroid); $\Theta(n)$ for paths, where $\Theta(\sqrt n)$ is optimal

Facts to keep to hand:

Revenue maximization is welfare maximization on virtual values. That single substitution converts every efficient-mechanism result into a revenue result.
The virtual value is value minus information rent, and it goes negative for low values — which is why optimal auctions withhold goods and why revenue and efficiency diverge.
Myerson’s lemma is used three times here: to derive the revenue identity, to justify the prior-free payment rules, and in reverse to prove prior-free lower bounds.
The prior-free benchmark must be weakened twice — to single prices, and to exclude the top bidder — and each weakening is forced by an explicit impossibility.
Random sampling and consensus estimation solve the same problem by different means: making the price a bidder faces independent of his own bid.
In procurement, overpayment is not automatically the mechanism’s fault; the $\nu$ benchmark exists to separate market structure from mechanism waste, and matroid structure is what makes VCG frugal.

References

Nisan, Roughgarden, Tardos & Vazirani, Algorithmic Game Theory — chapter 13 (Hartline & Karlin)

Related