1
$\begingroup$

Hey, everyone. I desperately need help understanding some math in auction theory. I have been writing a paper as an undergrad for auction theory, and after all of my research I just cannot understand one step the author of a book uses to derive the equilibrium strategy for first-price auctions under independent private value conditions.
The steps in the derivation process essentially follow this: Let x = the chosen player's personal valuation, G(x) = the probability that the highest opposing bid, an order statistic, Y_1, is < x. \begin{equation} \beta(x) = x - \int_0^x\frac{G(y)}{G(x)} \, dy \\ \end{equation} Then without much explanation, other than "values are uniformly distributed on [0,1]" he just converts this equation to \begin{equation} \beta(x) = \frac{N-1}{N}, \end{equation} Which makes sense and is usable.

The book I am using is Vijay Krishna's Auction Theory, and I would extremely appreciate someone helping me understand this last step.

$\endgroup$
  • $\begingroup$ Looks like @KitsuneCavalry ended up writing up what I was planning to, and more! I suggest you read my answer first for a small hint, and try to work it out for yourself first. If you find yourself struggling, or if you've worked it all out, read KC's answer for more hints/a possibly different perspective. $\endgroup$ – Theoretical Economist Nov 29 '16 at 12:17
2
$\begingroup$

I remember slaving over the notation in this book when I was a bad undergraduate. It brings up some interesting memories, some which may help you.

  • $F(x)$ is the cumulative distribution of a single bidder's valuation.
  • $G(x)$ is the cumulative distribution of the highest bidder's valuation, given $N$ bidders.

For the example you are referring to, values being uniformly distributed along $[0,1]$ implies $F(x) = x.$ That's pretty straightforward. The chance of you having a valuation of $\frac{1}{2}$ or less for the object is, well, $\frac{1}{2}$. The chance of you having at least a value of $1$ should be a probability of $1$.

But why is $G(x) = x^{N-1}$ ?

For $n =1$, the chance of your valuation being the largest valuation or less is...well, $1 \ (= x^0)$.

For $n = 2$, the chance of your valuation being the largest valuation or less is just the chance that the other bidder has a valuation lower than you, or exactly $x$.

For $n = 3$, the chance of your valuation being the biggest or less is just the chance that both other bidders value the object less. Since you're working with independent private values, you can think of their valuations as independent (duh) events, so you can just multiply the events together. (More on conditional probability here). So for example the chance of someone having a smaller value than you is $x$, but there is another person who also has to have a smaller value than you, with the same chance $x$. The chance of both of them having smaller values than you is $x \cdot x = x^2$.

So it goes, the more bidders (independent valuations) you have.


So we have your general formula for an optimal bid under a first-price auction:

$$\beta^1(x) = x - \int^x_0 \frac{G(y)}{G(x)} dy$$

So substitute in $G(x)$:

$$\beta^1(x) = x - \int^x_0 \frac{y^{N-1}}{x^{N-1}} dy$$

Evaluate:

$$= x \ - \ \biggr\lvert \frac{y^N}{Nx^{N-1}} + c\biggr\rvert^x_0$$ $$= x - \frac{x}{N} = \frac{Nx}{N} - \frac{x}{N}$$ $$\boxed{\beta^1(x) = x\frac{N - 1}{N}}$$


The next example in Krishna's book has an exponential distribution, but only with two bidders. If you try using the same line of reasoning as I used above to find $G(x)$, you'll notice things appear a bit difficult, but the author doesn't explicitly state $G(x)$ in this case in fact. Try seeing for yourself if you understand why Krishna gives the helpful statement:

$$\frac{G(y)}{G(x)} = \left[\frac{F(y)}{F(x)}\right]^{N-1}$$

for the generic case where there is no functional form for the distributions.

$\endgroup$
  • $\begingroup$ Hey, Kitsune Cavalry, thank you so much for your very helpful detailed post! That does actually make more sense now, with $G(x) = x^{N-1}$. Before I completely become ebullient at your help, I still have one more question. What does G(y) mean for Krishna? I know it somehow refers to the order statistics, but I do not really understand its usage, and he (seemingly) does not explain it anywhere as far I can tell. The introduction of "y'' seems unnecessary if x and the cdf's account for the order statistics. $\endgroup$ – Coolio2654 Dec 1 '16 at 0:24
  • $\begingroup$ I believe $x$ denotes "your" bid, and $y$ denotes the largest bid in Krishna's book. $\endgroup$ – Kitsune Cavalry Dec 1 '16 at 0:27
  • $\begingroup$ Ok, but then how can $G(y)$ make sense, if that is the distribution of Prob$[Y_1 < y]$? Understanding how that makes sense and why Krishna replaces $x$ with $y$ when deriving the strategy earlier are the last aspects I'm still struggling to understand. This is the part I'm talking about $yg(y)$. $\endgroup$ – Coolio2654 Dec 1 '16 at 20:04
  • $\begingroup$ I have the book with me. What page number? $\endgroup$ – Kitsune Cavalry Dec 1 '16 at 23:54
  • $\begingroup$ Sorry for the late reply, other finals kept me busy. It is on page 17 right in the middle of the page before proposition 2.2 in his book. That is where he introduces using $y$, without giving any reason, so I do not understand the rationale at all. $\endgroup$ – Coolio2654 Dec 4 '16 at 5:17
2
$\begingroup$

I think you have a typo -- the equilibrium bidding strategy in the first-price auction you specify should be $$ \beta(x) = \frac{N-1}{N}x $$

Here's a hint that might help. The CDF of the order statistic, $Y_1$, is $$G(x) = x^{N-1}$$

To see why this is the case, notice that this is exactly the probability that some given quantity $x$ is greater than or equal to $N-1$ independently drawn random variables that are uniformly distributed on $[0,1]$.

I'll write something in more detail when I have more time tomorrow, but I think this should tide you over for now. (At the very least, it'll help you evaluate the integral.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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