Pricing Mechanisms and the Riemann-Stieltjes Integral

Imagine we are trying to sell a sack of rice. We want to make as much money from this sale as possible. What should we do? This is an important problem in the field of mechanism design, which is a part of game theory. I was studying this problem in a very simple setting, and came across some very interesting math while doing so. In this article, I will share my mathematical journey. I won't talk much about the mechanism design part to keep this article accessible to a broad audience.

Posted-Price Mechanisms¶

Let's consider the simplest case where there is exactly one person in the world who wants to buy what we're selling. One of the simplest and most obvious mechanisms is a posted-price mechanism. Here we set a price $p$ for the item. We then offer two options to the buyer:

1. purchase: The buyer gets the item and pays us $p$ dollars.
2. decline: The buyer doesn't get the item and we don't get any money.

We expect the buyer to pick the option that's more preferable to them. Specifically, the buyer has a value $v$ for the item. If $v\ge p$, they will purchase it, otherwise they will decline.

If we knew $v$, we would set the price as $v$, so that we can earn as much money as possible. Unfortunately, we often do not know $v$. But sometimes we know a probability distribution over $v$ (e.g., based on past data or experience), and we want to maximize the expected value of our revenue.

Let us take an example. Suppose $v$ is 2 with probability $1/3$ and 4 with probability $2/3$.

• If the price is more than 4, the buyer would not want to purchase, so our revenue would be $0$.
• If the price is at most 2, the buyer will definitely purchase, so our revenue would be $p$.
• If the price is more than 2 and at most 4, the buyer will purchase with probability $2/3$, and our expected revenue would be $(2/3)\cdot p$.

If we set $p=4$, our revenue would be $8/3$, and it is easy to see that there is no other way to set the price $p$ such that the revenue is more than $8/3$. Hence, $p=2$ is the optimal price and the optimal expected revenue is $8/3$.

In general, our revenue is $p$ with probability $\mathrm{Pr}(v\ge p)$ and $0$ with probability $\mathrm{Pr}(v<p)$. Hence, the expected value of our revenue is $p\cdot \mathrm{Pr}(v\ge p)$. We should set $p$ to a value such that this expression is maximized.

Truthful Single-Parameter Mechanisms¶

Now let's consider a totally different kind of mechanism, called a single-parameter mechanism. We give the buyer $a(v)$ fraction of the good and charge them $r(v)$ dollars. Here $a:R_{\ge 0}\to [0,1]$ is called the allocation function and $r:R_{\ge 0}\to R_{\ge 0}$ is called the revenue function. We require $r(0)$ to be 0.

Now you may wonder, "To charge them $r(v)$ dollars, we would need to know the value of $v$. How would we know that?". That's a good question, but answering that is beyond the scope of this article. If you're curious, read Tim Roughgarden's lectures 3 and 5 on Algorithmic Game Theory [1]. For now, assume that we can know the value of $v$ if the mechanism $(a,r)$ is truthful, i.e., for every $0\le x_1<x_2$, we have $$a(x_1)\le \frac{s(x_2)-s(x_1)}{x_2-x_1}\le a(x_2),$$ where $s(x):=xa(x)-r(x)$.

Observe that posted-price mechanisms can also be viewed as single-parameter mechanisms. If the item has price $p$, then $a(v)=1(v\ge p)$ and $r(v)=p1(v\ge p)$. (Here $1(P)$ is defined to be 1 if proposition $P$ is true and 0 if $P$ is false.) One can check that posted-price mechanisms are also truthful.

Now comes the main question: Are there truthful single-parameter mechanisms that can give us a larger expected revenue than posted price mechanisms? In other words, we want to find a mechanism $(a,r)$ such that $E(r(v))$ is maximized. Here $v$ is a random variable from a known distribution.

An Informal Solution¶

I'll first solve this problem without regards to mathematical rigor. This will provide the necessary intuition. We will then look at how to formalize these arguments, and that's where things get really interesting if you like real analysis.

We first give a characterization of all truthful mechanisms.

Lemma 1: Mechanism $(a,r)$ is truthful iff $a$ is non-decreasing and $$r(x)=xa(x)-{\int }_0^{x}a(y)dy.$$

Proof. Suppose $(a,r)$ is truthful. Then, by definition, $a$ must be non-decreasing. By making $x_2$ get arbitrarily close to $x_1$, we get $s^{\prime }(x_1)=a(x_1)$ (i.e., the derivative of $s$ at $x_1$ is $a(x_1)$). $r(0)=0$ implies $s(0)=0$. Hence, $s(x)={\int }_0^{x}a(y)dy$, and so, $r(x)=xa(x)-{\int }_0^{x}a(y)dy$.

Now suppose $a$ is non-decreasing and $r(x)=xa(x)-{\int }_0^{x}a(y)dy$. Then $s(x)={\int }_0^{x}a(y)dy$, so for any $0\le x_1<x_2$, we get $$\begin{array}{rl}& s(x_2)-s(x_1)={\int }_{x_1}^{x_2}a(x)dx\\ & \in [a(x_1)(x_2-x_1),a(x_2)(x_2-x_1)].\square \end{array}$$

Now let's compute the expected revenue. Assume that the cumulative distribution of $v$ is $F$ and the probability density function of $v$ is $f$, i.e., $F(x):=\mathrm{Pr}(v\le x)$ and $f(x):=dF(x)/dx$.

Lemma 2: The expected revenue of a truthful mechanism $(a,r)$ is $${\int }_0^{\infty }x(1-F(x))a^{\prime }(x)dx.$$

Proof. First, using integration by parts, we get $${\int }_0^{x}y{a}^{\prime }(y)dy=xa(x)-{\int }_0^{x}a(y)dy=r(x).$$ Then, $$\begin{array}{rl}E(r(v))& ={\int }_0^{\infty }\left({\int }_0^{u}x{a}^{\prime }(x)dx\right)f(u)du\\ & ={\int }_0^{\infty }x{a}^{\prime }(x)\left({\int }_x^{\infty }f(u)du\right)dx\\ & ={\int }_0^{\infty }x{a}^{\prime }(x)(1-F(x))dx.\end{array}$$ (Here we swapped the integration order.) $\square$

Lemma 3: $(a,r)$ is a revenue-maximizing truthful mechanism iff $a(x)=1(x\ge p)$ and $r(x)=1(x\ge p)$, where $p$ is the value for which $p(1-F(p))$ is maximum.

(Does this solution look familiar? This is exactly the posted-price mechanism at price $p$! Hence, no truthful single-parameter mechanism does better than the best posted-price mechanism.)

Proof. We need to find a non-decreasing allocation function $a$ for which ${\int }_0^{\infty }x(1-F(x))a^{\prime }(x)dx$ is maximized. This means $a^{\prime }(x)\ge 0$ for all $x$ and ${\int }_0^{\infty }{a}^{\prime }(x)dx\le 1$.

This is similar to the problem where we are given a vector $b\in R^n$ and we must find a vector $x\in R_{\ge 0}^n$ such that ${\sum }_{i=1}^n{x}_i\le 1$ and $b^{T}x$ is maximized. The solution is to find the index $i^{\ast }$ at which $b$ is maximum, i.e., $b_{i^{\ast }}\ge b_i$ for all $i$, and then set $x_i=1(i=i^{\ast })$. Then $b^{T}x$ would equal ${\max }_{i=1}^n{b}_i$.

We just carry over this idea from sums to integrals. We first find $p\in R_{\ge 0}$ such that $p(1-F(p))$ is maximized. Then we want to concentrate all the mass at $p$, i.e., $a^{\prime }(p)$ is extremely large and $a^{\prime }(x)=0$ for all $x\ne p$. This is the same as saying $a(x)=1(x\ge p)$. Using Lemma 1, we get $r(x)=xa(x)-{\int }_0^{x}a(y)dy=p1(x\ge p)$. Then the pair $(a,r)$ gives us the maximum revenue among all truthful single-parameter mechanisms. $\square$

Another result, which would be useful later, is that in truthful mechanisms, the revenue function is non-decreasing.

Lemma 4: If $(a,r)$ is a truthful mechanism, then $r(x)$ is non-decreasing in $x$.

Proof. Since $(a,r)$ is truthful, for all $0\le x_1<x_2$, we get $$a(x_1)\le \frac{s(x_2)-s(x_1)}{x_2-x_1}\le a(x_2)$$ $$⟹x_1(a(x_2)-a(x_1))\le r(x_2)-r(x_1)\le x_2(a(x_2)-a(x_1)).$$ Since $a$ is non-decreasing in truthful mechanisms, we get that $r(x_2)-r(x_1)\ge 0$ for all $0\le x_1<x_2$. Hence, $r$ is non-decreasing. $\square$

Need for Mathematical Rigor¶

You may have noticed a lot of problems with the proofs above.

• In Lemma 1's proof, we assumed that $s^{\prime }(x_1)$ is well-defined, i.e., $s$ is differentiable at $x_1$.
• In Lemmas 2 and 3, we assumed that $a$ is differentiable. (But for posted-price mechanisms, we know that $a$ is not differentiable!)
• We assumed that $v$ is a continuous random variable. What if $v$ is a discrete random variable, or it is neither discrete nor continuous?

Even though the above proofs are wrong, I think the facts are still true, we just have to find proper proofs.

There is one more problems with the above proofs: we need to define integration appropriately.

High school math generally defines integrals like this: ${\int }_a^{b}f(x)dx$ is defined to be $F(b)-F(a)$, where $F$ is the anti-derivative of $f$, i.e., $F^{\prime }(x)=f(x)$ for all $x\in [a,b]$. But this definition is problematic.

For posted-price mechanisms, $a(x)=1(x\ge p)$. To compute $r(x)$, we must find ${\int }_0^{x}a(y)dy$. We can't use the high-school definition since there is no differentiable function whose derivative at $y$ is $a(y)$ for all $y\in [0,x]$. Intuitively, ${\int }_0^{x}a(y)dy$ should be $(x-p)1(x\ge p)$, but this function is not differentiable at $p$ (the left derivative is 0 and the right derivative is 1).

We have used integrals extensively in the proofs above, but for them to make sense, we must first define integration appropriately. I had taken a course in real analysis at UIUC, so this wasn't hard for me: one can just use Darboux integrals or Riemann integrals here, and that would easily fix Lemma 1.

But fixing Lemmas 2 and 3 is really tough.

Preliminaries: sup and inf¶

If you have taken a course in real analysis, you can skip this section (and maybe the next one too). Otherwise, to understand the rest of the post, you must have a good grasp over infimum and supremum, which I will explain here.

Some sets do not have a minimum. E.g., the smallest element in the interval $[3,4]$ is 3, but $(3,4]$ does not have a smallest element. In situations where we require a set to have a minimum but it doesn't have one, we can generally use the infimum instead.

Let $X\subseteq R$ and $a\in R$. $a$ is called a lower bound on $X$ if $a\le x$ for all $x\in X$. A number $b$ is called the greatest lower bound of $X$ (aka the infimum of $X$, denoted as $\inf (X)$) if $b\ge a$ for every lower bound $a$ of $X$. E.g., the greatest lower bound of $(3,4]$ is 3.

Does every set $X\subseteq R$ have an infimum? If $X$ is empty, then no. But what if $X$ is non-empty? $X$ may not have any lower bound, e.g., the set $(-\infty ,1]$. In that case we say that $\inf (X)=-\infty$. But what if $X$ has a lower bound? Then yes, $X$ always has an infimum, and this is an axiom of real numbers: If a non-empty set $X$ of real numbers has a lower bound, then it has a greatest lower bound.

We can similarly define the least upper bound of $X$, also called the supremum of $X$, denoted as $\sup (X)$. If $X\ne \varnothing$, then $\sup (X)$ always exists: $\sup (X)=\infty$ if $X$ has no upper bound, and $\sup (X)$ is a real number otherwise.

Darboux Integrals and the Proof of Lemma 1¶

A standard way to define integration is through Darboux integrals. You will find this in many textbooks and lecture notes on real analysis [2].

For any integer $n\ge 0$, define $[n]$ as the set $\{1,2,\dots ,n\}$.

Definition 1 (Darboux integral):

• Let $f:[a,b]\to R$ be a function.
• Let $P:=(x_0,x_1,\dots ,x_n)$ be a sequence of numbers where $a=x_0<x_1<\dots <x_n=b$. The lower and upper Darboux sums of $f$ on $P$, denoted by $L_f(P)$ and $U_f(P)$, respectively, are defined as follows: If $a=b$, then $L_f(P)=U_f(P)=0$. Otherwise, $$\begin{array}{rl}{L}_f(P)& :=\sum _{i=1}^n(x_i-x_{i-1})\left(\underset{x\in [x_{i-1},x_i]}{\inf }f(x)\right),\\ U_f(P)& :=\sum _{i=1}^n(x_i-x_{i-1})\left(\underset{x\in [x_{i-1},x_i]}{\sup }f(x)\right).\end{array}$$
• Let $\mathcal{P}(a,b):=\{(x_0,\dots ,x_n):n\in \mathbb{N},a=x_0<\dots <x_n=b\}$. Then $\mathcal{P}(a,b)$ is called the set of partitions of $[a,b]$.
• The lower and upper Darboux integrals of $f$ are $$\begin{array}{rl}{L}_f(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\sup }{L}_f(P),\\ U_f(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\inf }{U}_f(P).\end{array}$$
• If $L_f(a,b)=U_f(a,b)$, then $f$ is said to be Darboux integrable on $[a,b]$, and we denote $L_f(a,b)$ and $U_f(a,b)$ by ${\int }_a^{b}f(x)dx$ or ${\int }_a^{b}f$.

Here are some useful properties of Darboux integrals of the function $f:[a,b]\to R$. Proofs can be found in standard texts on real analysis (e.g., [2]).

1. $U_f(a,b)\ge L_f(a,b)$.
2. For $a\le b\le c$, we have $L_f(a,b)=L_f(a,c)+L_f(c,b)$ and $U_f(a,b)=U_f(a,c)+U_f(c,b)$.
3. Suppose $\alpha \le f(x)\le \beta$ for all $x\in [a,b]$. Then $\alpha (b-a)\le L_f(a,b)\le U_f(a,b)\le \beta (b-a)$.
4. If $f$ is non-decreasing, then $f$ is integrable over $[a,b]$.

Armed with these results, we are ready to prove Lemma 1 rigorously.

Proof of Lemma 1.
Suppose $a$ is non-decreasing and $r(x)=xa(x)-{\int }_0^{x}a(y)dy$ for all $x\ge 0$. We have to prove that $(a,r)$ is truthful. For any $0\le x_1<x_2$, we get $$\frac{s(x_2)-s(x_1)}{x_2-x_1}=\frac{{\int }_{x_1}^{x_2}a(y)dy}{x_2-x_1}\in [a(x_1),a(x_2)].$$ Hence, $(a,r)$ is truthful.

Suppose $(a,r)$ is truthful. Then $a$ is non-decreasing, and for all $0\le y<z$, we have $$a(y)\le \frac{s(z)-s(y)}{z-y}\le a(z),$$ where $s(x):=xa(x)-r(x)$.

Pick any $t\in R_{\ge 0}$. Let $P=(x_0,\dots ,x_n)\in \mathcal{P}(0,t)$. Then for all $i\in [n]$, we get $$a(x_{i-1})(x_i-x_{i-1})\le s(x_i)-s(x_{i-1})\le a(x_i)(x_i-x_{i-1}).$$ Hence, $$\begin{array}{rl}{L}_a(P)& =\sum _{i=1}^n(x_i-x_{i-1})\left(\underset{x\in [x_{i-1},x_i]}{\inf }a(x)\right)\\ & =\sum _{i=1}^n(x_i-x_{i-1})a(x_{i-1})\\ & =\sum _{i=1}^n(s(x_i)-s(x_{i-1}))=s(t)-s(0),\end{array}$$ and $$\begin{array}{rl}{U}_a(P)& =\sum _{i=1}^n(x_i-x_{i-1})\left(\underset{x\in [x_{i-1},x_i]}{\sup }a(x)\right)\\ & =\sum _{i=1}^n(x_i-x_{i-1})a(x_i)\\ & =\sum _{i=1}^n(s(x_i)-s(x_{i-1}))=s(t)-s(0).\end{array}$$ Since $r(0)=0$, we get $s(0)=0$, and thus, $U_a(P)=L_a(P)=s(t)$. Hence, $U_a(0,t)\le U_a(P)=s(t)$ and $L_a(0,t)\ge L_a(P)=s(t)$.

Since $a$ is non-decreasing, $a$ is integrable over $[0,t]$, and so, $U_a(0,t)=L_a(0,t)=s(t)$. Hence, for any $x\ge 0$, we have $r(x)=xa(x)-{\int }_0^{x}a(y)dy$. $\square$

The Weighted Darboux Integral¶

Proving Lemma 2 is trickier. We need to somehow deal with $a^{\prime }(x)$ in the lemma statement.

My original idea was to modify the Darboux integral. For any function $f:[a,b]\to R$ and any non-decreasing function $W:[a,b]\to R$, to change ${\int }_a^{b}f(x)dx$ to ${\int }_a^{b}f(x)W^{\prime }(x)dx$, in $L_f(P)$ and $U_f(P)$, I changed $(x_i-x_{i-1})$ to $(W(x_i)-W(x_{i-1}))$.

I initially thought that I had come up with a nice generalization of Darboux integrals, which I named weighted Darboux integrals, but I later realized that this idea has been studied before by Riemann and Stieltjes.

Definition 2 (Weighted Darboux integral):

• Let $f,W:[a,b]\to R$ be functions where $W$ is non-decreasing.
• Let $P:=(x_0,x_1,\dots ,x_n)$ where $a=x_0<x_1<\dots <x_n=b$. Then the lower and upper weighted Darboux sums of $f$ on $P$ with weight $W$, denoted by $L_{f,W}(P)$ and $U_{f,W}(P)$, respectively, are defined as follows: If $a=b$, then $L_{f,W}(P)=U_{f,W}(P)=0$. Otherwise, $$\begin{array}{rl}{L}_{f,W}(P)& :=\sum _{i=1}^n(W(x_i)-W(x_{i-1}))\left(\underset{x\in (x_{i-1},x_i)}{\inf }f(x)\right),\\ U_{f,W}(P)& :=\sum _{i=1}^n(W(x_i)-W(x_{i-1}))\left(\underset{x\in (x_{i-1},x_i)}{\sup }f(x)\right).\end{array}$$
• Let $\mathcal{P}(a,b):=\{(x_0,\dots ,x_n):n\in \mathbb{N},a=x_0<\dots <x_n=b\}$. $\mathcal{P}(a,b)$ is called the set of partitions of $[a,b]$.
• The lower and upper weighted Darboux integrals of $f$ with weight $W$ are $$\begin{array}{rl}{L}_{f,W}(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\sup }{L}_{f,W}(P),\\ U_{f,W}(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\inf }{U}_{f,W}(P).\end{array}$$
• If $L_{f,W}(a,b)=U_{f,W}(a,b)$, then $f$ is said to be $W$-Darboux integrable on $[a,b]$, and we denote $L_{f,W}(a,b)$ and $U_{f,W}(a,b)$ by ${\int }_a^{b}f(x)dW(x)$.
• When $W$ is the identity function, we write $L_f$ and $U_f$ instead of $L_{f,W}$ and $U_{f,W}$, respectively. If $L_f(a,b)=U_f(a,b)$, we denote them by ${\int }_a^{b}f(x)dx$.

Once again, we can prove some simple properties for $f,W:[a,b]\to R$, where $W$ is non-decreasing:

1. $U_{f,W}(a,b)\ge L_{f,W}(a,b)$.
2. For $a\le b\le c$, we have $L_{f,W}(a,b)=L_{f,W}(a,c)+L_{f,W}(c,b)$ and $U_{f,W}(a,b)=U_{f,W}(a,c)+U_{f,W}(c,b)$.
3. Suppose $\alpha \le f(x)\le \beta$ for all $x\in [a,b]$. Then $\alpha (W(b)-W(a))\le L_{f,W}(a,b)\le U_{f,W}(a,b)\le \beta (W(b)-W(a))$.

Unfortunately, every non-decreasing function may not be integrable now if the weight function $W$ is discontinuous.

Example 1:

• Let $g(x)=0$ for $x<1/2$, $g(1/2)=1/2$, and $g(x)=1$ for $x>1/2$.
• Let $W(x)=0$ for $x<1/2$ and $W(x)=1$ for $x\ge 1/2$.

Pick any partition $P=(x_0,\dots ,x_n)\in \mathcal{P}(0,1)$. We now have two cases:

1. $x_{i-1}<1/2<x_i$ for some $i$. Then $L_{g,W}(P)=0$ and $U_{g,W}(P)=1$.
2. $x_i=1/2$ for some $i$. Then $L_{g,W}(P)=0$ and $U_{g,W}(P)=1/2$.

Hence, $L_{g,W}(0,1)=0$ and $U_{g,W}(0,1)=1/2$, so $g$ is not $W$-integrable over $[0,1]$.

But why is this example concerning? We can prove that if either $g$ or $W$ is continuous, and $g$ is non-decreasing, then $g$ is $W$-integrable, so in Lemma 1, ${\int }_0^{x}a(y)dy$ is still well-defined.

However, I was thinking of using weighted Darboux integrals to define expected value. For a positive random variable $X$ with cumulative distribution function $F$ (i.e., $F(x):=\mathrm{Pr}(X\le x)$), one could define $E(g(X))$ as $$\underset{T\to \infty }{\lim }{\int }_0^{T}g(x)dF(x).$$

Let $X$ be a random variable that takes value $1/2$ with probability 1 (i.e., it's not random at all). Then its cumulative distribution function is $W$ from Example 1. Then one would expect $E(g(X))$ to equal $g(1/2)$, which is $1/2$, but the integral defining $E(g(X))$ doesn't exist by Example 1.

Also, in Lemma 2, I want the integral $${\int }_0^{T}x(1-F(x))da(x)$$ to exist for all $T\ge 0$, but I can't think of a way of guaranteeing that (unless we change the definition of weighted Darboux integrals.)

A Second Attempt at Weighted Darboux Integrals¶

Let's try to define Darboux integrals again, but this time, we will explicitly take discontinuities into account.

Let $f:[a,b]\to R$ be a non-decreasing function. For any $c\in (a,b]$, let $f^{-}(c):={\sup }_{x\in (a,c)}f(x)$, and for any $c\in [a,b)$, let $f^{+}(c):={\inf }_{x\in (c,b)}f(x)$.

One can easily show that $f^{+}(c)\ge f(c)$ for all $c\in [a,b)$, $f^{-}(c)\le f(c)$ for all $c\in (a,b]$, and $f^{+}(x_1)\le f((x_1+x_2)/2)\le f^{-}(x_2)$ for all $a\le x_1<x_2\le b$.

Definition 3 (Jump-aware weighted Darboux integral):

• Let $f,W:[a,b]\to R$ be functions where $W$ is non-decreasing.
• Let $P:=(x_0,x_1,\dots ,x_n)$ where $a=x_0<x_1<\dots <x_n=b$. Then the jump, lower, and upper weighted Darboux sums of $f$ on $P$ with weight $W$, denoted by $J_{f,W}(P)$, $L_{f,W}(P)$, and $U_{f,W}(P)$, respectively, are defined as follows: If $a=b$, then $J_{f,W}(P)=L_{f,W}(P)=U_{f,W}(P)=0$. Otherwise, $$\begin{array}{rl}{J}_{f,W}(P)& :=f(x_0)(W^{+}(x_0)-W(x_0))+\sum _{i=1}^{n-1}f(x_i)(W^{+}(x_i)-W^{-}(x_i))\\ & +f(x_n)(W(x_n)-W^{-}(x_n)),\\ L_{f,W}(P)& :=J_{f,W}(P)+\sum _{i=1}^n(W^{-}(x_i)-W^{+}(x_{i-1}))\left(\underset{x\in (x_{i-1},x_i)}{\inf }f(x)\right),\\ U_{f,W}(P)& :=J_{f,W}(P)+\sum _{i=1}^n(W^{-}(x_i)-W^{+}(x_{i-1}))\left(\underset{x\in (x_{i-1},x_i)}{\sup }f(x)\right).\end{array}$$
• Let $\mathcal{P}(a,b):=\{(x_0,\dots ,x_n):n\in \mathbb{N},a=x_0<\dots <x_n=b\}$. $\mathcal{P}(a,b)$ is called the set of partitions of $[a,b]$. The lower and upper weighted Darboux integrals of $f$ with weight $W$ are $$\begin{array}{rlrl}{L}_{f,W}(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\sup }{L}_{f,W}(P),& U_{f,W}(a,b)& :=\underset{P\in \mathcal{P}(a,b)}{\inf }{U}_{f,W}(P).\end{array}$$
• If $L_{f,W}(a,b)=U_{f,W}(a,b)$, then $f$ is said to be $W$-Darboux integrable on $[a,b]$, and we denote $L_{f,W}(a,b)$ and $U_{f,W}(a,b)$ by ${\int }_a^{b}f(x)dW(x)$.

Most simple properties that one might expect weighted Darboux integrals to have, the jump-aware weighted Darboux integrals have them too. See my notes [4] for formal statements and proofs.

Additionally, one can show that all monotone functions are integrable in this model [4]. It also evaluates ${\int }_0^{1}g(x)dW(x)$ as $1/2$ in Example 1. So far, this new definition of weighted Darboux integrals seems to have fixed the problems that the previous definition had. Now let's get back to trying to formalize Lemma 2.

Formalizing Lemma 2¶

First, let's show that integration by parts holds in our model, because we use it in the first step of our proof. We would like to show that for two non-decreasing functions $f,g:[a,b]\to R$, we have $${\int }_a^{b}f(x)dg(x)+{\int }_a^{b}g(x)df(x)=f(b)g(b)-f(a)g(a).$$ Unfortunately, this isn't true, even when $f=g$.

Example 2: Let $g(x)=0$ if $x<1/2$, $g(1/2)=1/5$, and $g(x)=1$ for $x>1/2$. Then one can show that ${\int }_0^{1}g(x)dg(x)=1/5$, but $2/5=2{\int }_0^{1}g(x)dg(x)\ne g(1{)}^2-g(0{)}^2=1$.

Fortunately, I could prove that integration by parts holds if either $f$ or $g$ is continuous [4]. And in Lemma 2, we apply integration by parts on $x$ and $a(x)$, and $x$ is continuous. So things still work out (for now), and we get that $r(x)={\int }_0^{y}yda(y)$ for all $x\ge 0$.

First, we would like to ensure that $E(r(v))$ is well-defined. Or at least, we want to ensure that ${\int }_0^{T}r(x)dF(x)$ exists for all $T\ge 0$, where $F$ is the cumulative distribution function of $v$. This integral exists since $r$ is non-decreasing by Lemma 4.

Next, I wanted to prove that we can exchange the order of integration. But I couldn't prove it.

And then it struck me; Lemma 2 is wrong! Consider posted price mechanisms. There, the expected revenue is $p\mathrm{Pr}(v\ge p)$. But for all $T>p$, ${\int }_0^{T}x(1-F(x))da(x)$ evaluates to $p(1-F(p))=p\mathrm{Pr}(v>p)$. Maybe we should use $x(1-G(x))$ instead of $x(1-F(x))$ in Lemma 2's statement, where $G(x):=\mathrm{Pr}(v<x)$? (Note that $G(x)=F^{-}(x)$ for all $x>0$ and $G^{+}(x)=F(x)$ for all $x\ge 0$. $G(0)=0$, but $F^{-}(0)$ is not defined.)

I discovered an edge case that was spoiling the definition of expected value. For a positive random variable $X$, defining $E(g(X))$ as ${\lim }_{T\to \infty }{\int }_0^{T}g(x)dF(x)$, where $F(x):=\mathrm{Pr}(X\le x)$ seems to work fine, but if $X$ is non-negative, and can take a value of 0 with positive probability, then this definition doesn't work. We can fix it by adding the term $F(0)g(0)$ to the integral, or we can define $E(g(X))$ as ${\lim }_{T\to \infty }{\int }_0^{T}g(x)dG(x)$, where $G(x):=\mathrm{Pr}(X<x)$.

With these fixes, Lemma 2 seems to be true for posted price mechanisms, i.e., for $a(x)=1(x\ge p)$ and $r(x)=p1(x\ge p)$, we get $E(r(v))=p\mathrm{Pr}(v\ge p)$ and ${\int }_0^{T}x(1-G(x))da(x)=p\mathrm{Pr}(v\ge p)$ for all $T>p$.

However, Lemma 2 is still wrong. Consider a different mechanism: for any $p,\gamma \in (0,1)$, define $$a(x)=\{\begin{array}{ll}0& x<p\\ \gamma & x=p\\ 1& x>p\end{array}.$$ Then $$r(x)=\{\begin{array}{ll}0& x<p\\ p\gamma & x=p\\ p& x>p\end{array}.$$ Suppose $v$ is $p$ with probability 1. Then $E(r(v))=p\gamma$. However, for any function $h:R_{\ge 0}\to R$ and any $T\ge 1$, we have ${\int }_0^{T}h(x)da(x)=h(p)$. For this integral to equal $E(r(v))$, we must have $h(p)=p\gamma$. Hence, we cannot have $h(x)$ be $x(1-F(x))$ or $x(1-G(x))$ or anything independent of $a(x)$.

Fixing Lemma 2¶

We will soon see that Lemma 2 doesn't hold only if $a^{+}(x)>a(x)$ for some $x\ge 0$.

Let $(a,r)$ be a truthful mechanism. Then $a$ is non-decreasing and $r(x)=xa(x)-{\int }_0^{x}a(y)dy$ for all $x\ge 0$ by Lemma 1. Let $b=a^{+}$ be a different allocation function. Note that $b$ is also non-decreasing. Let $\hat{r}(x)=xb(x)-{\int }_0^{x}b(y)dy$ for all $x\ge 0$. Then $(b,\hat{r})$ is also a truthful mechanism by Lemma 1.

Lemma 5: $\hat{r}(x)\ge r(x)$ for all $x\ge 0$.

Proof. $\hat{r}(x)-r(x)=x(b(x)-a(x))-{\int }_0^{x}y(b(y)-a(y))dy$. Let $g(x):=x(b(x)-a(x))$ for all $x\ge 0$. We will show that $U_g(0,T)\le 0$ for all $T\ge 0$, which would complete the proof.

Pick any $n\ge 1$. Let $x_i=T(i/n)$ for $0\le i\le n$. Then $P=(x_0,\dots ,x_n)\in \mathcal{P}(0,T)$, and $$\begin{array}{rl}{U}_g(P)& =\sum _{i=1}^n(x_i-x_{i-1})\left(\underset{x\in (x_{i-1},x_i)}{\sup }y(b(y)-a(y))\right)\\ & \le (T^2/n)\sum _{i=1}^n\underset{x\in (x_{i-1},x_i)}{\sup }(b(y)-a(y))\\ & \le (T^2/n)\sum _{i=1}^n(b(x_i)-a^{+}(x_{i-1}))\\ & =(T^2/n)(a^{+}(T)-a^{+}(0)).\end{array}$$ By making $n$ arbitrarily large, we can make $U_g(P)$ infinitesimally small. Hence, $U_g(0,T)={\inf }_{P\in \mathcal{P}(0,T)}{U}_g(P)\le 0$. Hence, $\hat{r}(x)\ge r(x)$ for all $x\ge 0$. $\square$

Lemma 6: Let $f:R_{\ge 0}\to R$ and let $g=f^{+}$. Then $g$ is right-continuous, i.e., $g^{+}(c)=g(c)$ for all $c\ge 0$.

Proof. Pick any $\epsilon >0$. Then $\exists z\in (c,b)$ such that $f(z)<f^{+}(c)+\epsilon$. Now, $g(c)\le g^{+}(c)\le g((c+z)/2)=f^{+}((c+z)/2)\le f(z)<f^{+}(c)+\epsilon =g(c)+\epsilon$. Since we can make $\epsilon$ as small as we want, we get $g^{+}(c)=g(c)$. $\square$

Lemmas 5 and 6 tell us that for every allocation function, there is a right-continuous allocation function whose revenue is greater or equal. Hence, from now on, we assume that the allocation function is right-continuous.

In my notes [4], I prove that the product of two bounded integrable functions is also integrable. Moreover, I prove the following result, that helps us do double integration.

Lemma 7: Let $V,W:[a,b]\to R$ be non-decreasing functions and $V$ be right continuous, i.e., $V^{+}(x)=V(x)$ for all $x\in [a,b)$. Let $f:[a,b]\to [0,M]$ for some $M\in R_{\ge 0}$ such that $L_{f,V}(a,b)=U_{f,V}(a,b)$. Let $r:[a,b]\to R_{\ge 0}$, where $r(x):={\int }_a^{x}f(y)dV(y)$. (Then $r$ is monotonic by $f$'s non-negativity, so $r$ is $W$-integrable over $[a,b]$.)

Let $h(x):=f(x)(W(b)-W^{-}(x))$ for all $x\in (a,b]$, and let $h(a):=f(x)(W(b)-W(a))$. (Then $h$ is $V$-integrable over $[a,b]$, since $f$ is $V$-integrable and $W$ is non-increasing.) Then ${\int }_a^{b}r(x)dW(x)={\int }_a^{b}h(x)dV(x)$.

Using Lemma 7, we get that if $(a,r)$ is truthful and $a$ is right-continuous, then the expected revenue is $$\begin{array}{rl}E(r(v))& =\underset{T\ge 0}{\sup }{\int }_0^{T}r(x)dF(x)\\ & =\underset{T\ge 0}{\sup }{\int }_0^{T}x(F(T)-F^{-}(x))da(x).\end{array}$$ (Recall that $F$ is the cumulative distribution function of $v$.) Hence, Lemma 2 holds after slight modification.

Lemma 3¶

Let's now get to Lemma 3.

Define $r_{\max }:={\sup }_{p\ge 0}p(1-F^{-}(p))$. Then for any truthful mechanism $(a,r)$ where $a$ is right-continuous, we get $$\begin{array}{rl}E(r(v))& =\underset{T\ge 0}{\sup }{\int }_0^{T}x(F(T)-F^{-}(x))da(x)\\ & \le \underset{T\ge 0}{\sup }{\int }_0^T{r}_{\max }da(x)\\ & =\underset{T\ge 0}{\sup }{r}_{\max }(a(T)-a(0))\le r_{\max }.\end{array}$$

Hence, the expected revenue of any truthful mechanism is at most $r_{\max }$. Moreover, if $(a,r)$ is the posted-price mechanism with price $p$, then $E(r(v))=p(1-F^{-}(p))$, so the maximum revenue we can get using posted-price mechanisms is $r_{\max }$. Hence, posted-price mechanisms are optimal.

Conclusion¶

This took several days to figure out and almost drove me mad. The informal proof is so simple, yet the formal proof is so long and requires deep insight into real analysis.

References¶

1. Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory.
   Cambridge University Press, 2016, ISBN: 9781316781173.
   Link to free versions:
   • Lecture 1: Introduction and Examples
   • Lecture 2: Mechanism Design Basics
   • Lecture 3: Myerson's Lemma
   • Lecture 4: Algorithmic Mechanism Design
   • Lecture 5: Revenue-Maximizing Auctions
   • Lecture 6: Simple Near-Optimal Auctions
2. David Galvin. Section 10: The Darboux Integral.
   Lecture notes for Math 10860 (Honors Calculus II) at the University of Notre Dame, Spring 2020.
3. Joel Feldman. Lecture notes for Math 321 (Real Variables II),
   University of British Columbia, 2016.
4. Eklavya Sharma. My notes on weighted Darboux integrals.