Proofs for Section 3 (Multi-Unit Posted-Price Mechanisms)

Table of Links

Abstract and 1. Introduction

2. The Soup Kitchen Problem

   2.1 Model and 2.2 Limits of Throughput and Availability

   2.3 Analysis of Throughput and Availability

3. Multi-Unit Posted-Price Mechanisms

   3.1 Model

   3.2 Results

4. Transaction fee mechanism design

5. Conclusions and future work, and References

A. Proofs for Section 2 (The Soup Kitchen Problem)

B. Proofs for Section 3 (Multi-Unit Posted-Price Mechanisms)

B Proofs for Section 3 (Multi-Unit Posted-Price Mechanisms)

with the last step following from the fact that agents, no matter how much is left on the shelf when they arrive at the mechanism, can always choose to buy nothing at all and obtain 0 utility. More formally,

We will now proceed to upper bound OPT. We compute as follows:

The last step follows from the fact that no allocation, including the optimal allocation, can use more than the total stock of K goods.

Combining our lower and upper bounds for APX and OPT, respectively, we have

This splits our welfare bound into two cases; a high δ case, where the term 1 − δ is smaller, and a low δ case, where the term E[B]/K is smaller.

Our goal now becomes finding a lower bound for E[B]/K in terms of D. We begin by applying the law of total expectation to E[B], yielding

Multiplying both sides by exp(λκ) − 1 and adding 1 to both sides, and we obtain

δ exp(λκ) + (1 − δ) ≤ E[exp(λY )].

Using the formula for the moment-generating function of a Poisson-distributed variable, we have E[exp(λY )] = exp(κτ (exp(λ) − 1)). Inserting this into the above inequality and rearranging gives us

This bound holds for any positive λ, but would be stronger for some selections of λ than others. The optimal λ does not have a closed form, but it can be very closely approximated. Consider that

Close approximations to the optimal λ on the right-hand side will tend to be underestimates of the optimal λ on the left-hand side. Thus, we will demonstrate a bound on the optimal λ for the left-hand side. We begin by taking the first derivative with respect to λ and setting it equal to 0:

Rearranging gives us