Virtual valuation when the distribution is discrete

The virtual valuation of a buyer in an auctin is a function used to calculate the expeced revenue of a seller from that buyer. When the buyer's value comes from a continuous distribution with pdf $f$ and cdf $F$, the virtual valuation is: $$r(v) := v - \frac{1-F(v)}{f(v)}$$ How exactly should the virtual valuation be calculated when the distribution is discrete?

For example, suppose the valuation of a buyer can take three values: 1 USD - with probability 0.3, 2 USD - with probability 0.3, 3 USD - with probability 0.4. What exactly are $F$ and $f$ in this case?

Virtual valuation is the derivative of the expected revenue function with respect to the quantile $q$ that is then evaluated at value $v$. The Revenue function is

$$R(q) = q\cdot v(q),\;\;\; q = 1-F(v),\;\;\; v(q) = F^{-1}(1-q) \tag{1}$$

and

$$r(v(q)): = \frac{dR(q)}{dq}= \frac{d}{dq}\big[q\cdot F^{-1}(1-q)\big] \tag{2}$$

written, after the calculations, in terms of $v$, so

$$r(v)=v - \frac{1-F(v)}{f(v)} \tag{3}$$

If $v$ is discrete we have

$$q_j = 1-F(v\leq v_j),\;\;\; j=1,...,k \tag{4}$$

where now $F$ is a distribution function of a discrete rv, an where $j$ counts the ordered discrete values that $v$ may take, $v \in \{v_1,...,v_k\}$.

Discretizing the relationship we could define

$$r(v(q_j, q_{j+1})):= \frac{R(q_{j+1})-R(q_j)}{q_{j+1}-q_j} \tag{5}$$

which in terms of $v$ becomes

$$r(v(q_j, q_{j+1})):= \frac{v_{j+1}\cdot [1- F(v\leq v_{j+1})] -v_{j}\cdot [1- F(v\leq v_{j})]}{1- F(v\leq v_{j+1})-1+F(v\leq v_{j})}$$

$$=\frac{v_{j+1}\cdot Pr(v > v_{j+1}) -v_{j}\cdot Pr(v > v_{j})}{-Pr(v=v_{j+1})}$$

Using

$$Pr(v > v_{j}) = Pr(v=v_{j+1}) + Pr(v>v_{j+1})$$

we get

$$r(v_j,v_{j+1}) = v_{j} - (v_{j+1}-v_j)\cdot \frac{Pr(v>v_{j+1})}{Pr(v=v_{j+1})}$$

or

$$r(v_j,v_{j+1}) = v_{j} - (v_{j+1}-v_j)\cdot \frac{1-F(v_{j+1})}{Pr(v=v_{j+1})} \tag{6}$$

Since to a first approximation, if $v$ is continuous, and $v_j,v_{j+1}$ are "close enough" we have

$$Pr[v \in (v_j,v_{j+1})] \approx f(v_{j+1}) \cdot (v_{j+1}-v_{j})$$

It is clear how the obtained relation for the discrete case can be seen as the analogue of the continuous case.

For practical applications, one could think also of using a "continuity correction" for the probability in the denominator of $(6)$.

And since $r(v)$ is defined via $f(v)$ virtual valuations also do not exist in this case. Even if one were to approximate the discrete distribution $X$ with continuous distributions $X_n$ in such a manner that $$\forall v: \lim_{n \to \infty} F_n(v) = F(v),$$ the limit $\lim_{n \to \infty} r_n(v)$ would not exist where $\lim_{n \to \infty} f_n(v) = 0$.

• So, is there a way to use the optimal auction theory when buyers' valuations come from discrete distributions? – Erel Segal-Halevi Jun 1 '18 at 13:06
• It depends on the distribution. But that was not your question, was it? – Giskard Jun 1 '18 at 13:15