<p>Yes, this follows from Myerson's lemma. A monotone function from an interval to <span class="math-container">$\{0,1\}$</span> 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).</p>
<p>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 <span class="math-container">$L_1$</span>-norm topology).</p>

CC BY-SA 4.0
2022-03-09T16:03:28.937Z
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!
Mengfan Ma
CC BY-SA 4.0
2022-03-09T16:11:24.313Z
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)$?
Mengfan Ma
CC BY-SA 4.0
2022-03-09T18:25:04.350Z
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.
Michael Greinecker
CC BY-SA 4.0
2022-03-08T08:40:03.037Z
2022-03-08T08:40:03.037Z
Michael Greinecker
<p>I'm reading Tim Roughgarden's <em>Twenty Lectures on Algorithmic Game Theory</em>. 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:</p>
<blockquote>
<p>The space of direct-revelation DSIC auctions is small: they are precisely the <em>posted prices</em>, meaning take-it-or-leave-it offers.</p>
</blockquote>
<p>Question 1: how this is concluded? Is it by Myerson's Lemma?</p>
<p>Assuming the above is correct, in the <a href="https://www.youtube.com/watch?v=jQsAoMcxlIo&amp;list=PLEGCF-WLh2RJBqmxvZ0_ie-mleCFhi2N4&amp;index=5&amp;t=943s" rel="nofollow noreferrer">lecture's video</a>, Tim Roughgarden also mentioned randomization over posted prices.</p>
<p>Question 2: how to do randomization over posted prices? Is the randomized posted prices mechanism is still DSIC?</p>

<auctions><mechanism-design>
Single-item single-bidder: why posted price is the only possible DSIC mechanism?
Mengfan Ma
# Single-item single-bidder: why posted price is the only possible DSIC mechanism?

(Asked by: username_0 on 2022-03-08)

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](https://www.youtube.com/watch?v=jQsAoMcxlIo&list=PLEGCF-WLh2RJBqmxvZ0_ie-mleCFhi2N4&index=5&t=943s), 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?

**Tags:** auctions, mechanism-design


---

## 1 answers

### Answer by username_1 on 2022-03-08. Score: 4 | Accepted answer

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

> **Comments:**
> **username_0**: 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!  
> **username_0**: 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)$?  
> **username_1**: 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.  

---

