3
$\begingroup$

I'm reading Tim Roughgarden's Twenty Lectures on Algorithmic Game Theory. Lecture 5 is on revenue-maximizing auctions. It claims that in the single-parameter qusilinear environment, for the extremely simple example with only one item to sell and one potential buyer:

The space of direct-revelation DSIC auctions is small: they are precisely the posted prices, meaning take-it-or-leave-it offers.

Question 1: how this is concluded? Is it by Myerson's Lemma?

Assuming the above is correct, in the lecture's video, Tim Roughgarden also mentioned randomization over posted prices.

Question 2: how to do randomization over posted prices? Is the randomized posted prices mechanism is still DSIC?

$\endgroup$

1 Answer 1

4
$\begingroup$

Yes, this follows from Myerson's lemma. A monotone function from an interval to $\{0,1\}$ must be constant or a threshold function that is zero up to a certain point and then one (actually, there are two options, depending on whether the function is continuous from the left or right, but the difference is inessential).

More generally, one can allow for nondeterministic allocation rules. In that case, Myerson's lemma implies that the probability of the single bidder getting the good must be (weakly) increasing, so there are more DSIC mechanisms then. Nevertheless, one can show that a posted price mechanism is optimal even without this restriction using some heavy math (the seller's problem is linear and continuous, and the posted price mechanisms are the extreme points of the compact and convex set of random mechanisms with increasing probability in the $L_1$-norm topology).

$\endgroup$
3
  • $\begingroup$ The textbook I'm reading does not cover the nondeterministic allocation rules and the math you mentioned. And I couldn't find any nice material. Could you please direct me to some resources or links? Thanks in advance! $\endgroup$
    – Mengfan Ma
    Mar 9, 2022 at 16:03
  • $\begingroup$ Here is my understanding: For the general case, $x$ maps the bids to a distribution over all feasible allocations. For the single-item single-bidder case, $x$ maps the single bid $b$ to the probability that the bidder gets the item, that is, $x: \mathbb{R}_{\ge0} \rightarrow [0, 1]$. $x$ is monotone if and only $x$ is implementable. If $x$ is monotone, then payment rule is $p(b)=\int_0^b z\cdot x'(z) dz$. However, I'm confused by the payment rule here: is it the expected payment? If so, what is the payment if the bidder gets the item? Is it $p(b)/x(b)$? $\endgroup$
    – Mengfan Ma
    Mar 9, 2022 at 16:11
  • 1
    $\begingroup$ Yes, the usual rule for payments pins down expected payments. The book "An Introduction to Mechanism Design" by Tilman Börgers covers the nondeterministic case and the extreme point argument. $\endgroup$ Mar 9, 2022 at 18:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.