1
$\begingroup$

I'm simulating a auction game with sealed single bid, where each of the $n$ players has winning probability $p_i,i=1,...,n$, and their bids $b_i$ have to be calculated to meet the $p_i$. Supposing that the value $v_i$ of each player is uniformly distributed in the interval $[0,1)$ and $b_i$ is a function of $v_i$ (as usual), how could I calculate their bids to match the $p_i$?

$\endgroup$
0
$\begingroup$

Given $b_i(V_i)$ define $G_i(b)=\Pr[b_i(V_i)\le b]$ and $g_i=G^\prime_i(b)$, you want to find $b_i$ that solves $$p_i=\int_0^{\overline b} \Pi_{j\neq i} G_j(b)\cdot g_i(b) db\quad \forall i \tag{*}$$

You should also have $\sum_i p_i=1$.

It seems there should be an infinite number of $G_i$ and so an infinite number of $b_i$ that are compatible with (*) since you are not imposing equilibrium conditions...

$\endgroup$
  • $\begingroup$ What is exactly $G_i\prime$? It seems to be the probability density function of $G_i$, however for that one particular $g_i$ we would need the pdf of the complementary event, Pr[$b_i(V_i)>b$], woundn't we? $\endgroup$ – IRO Jan 29 '15 at 11:06
  • $\begingroup$ Actually it is improper saying "the pdf of an event", because the pdf depends on the random variable only. What varies with the event is the interval of integration. I thought it about this question over and came up with a response which I will share below in the list of responses. $\endgroup$ – IRO Feb 1 '15 at 17:37
0
$\begingroup$

The goal is to simulate a sealed first-price auction game, where each of the $n$ players has winning probability $p_i$, with $\sum_{i=1}^{n}p_i=1$, and their bid functions $b_i:[0,1] \mapsto\mathbb{R}^+$ have to be calculated to meet the $p_i$; $b_i$ is a function of the player's valuation $v_i$, as usual. Supposing that the value $v_i$ of each player is stochastically distributed according to a probability density function $g_i$: \begin{equation}\def\arraystretch{2.2} g_i:[0,\infty) \mapsto\mathbb{R}^+\quad \textrm{s.t.} \left\{ \begin{array}{ccc} \int_0^1{\! g_i(v)\mathrm{d}v}=1 \\ g_i(v)=0 & \mathrm{for} & v > 1 \end{array} \right.\mathrm{,(Eq.01)} \end{equation} how can the bid functions $b_i(v_i)$ be determined to match the $p_i$?

Without loss of generality, it can be assumed that $b_1(1)\leq b_2(1)\leq ... \leq b_n(1)$. For a better understanding of the problem, initially it is defined that $n=2$. Being $p_2$ the probability of the player 2 winning, this event can be partitioned in two sub-events: \begin{equation} p_2=\Pr\{b_1(v_1)<b_2(v_2)\}\quad\mathrm{(Eq.02)} \end{equation} \begin{equation} =\Pr\{b_1(v_1)<b_2(v_2)\wedge b_2(v_2)<b_1(1)\}+\Pr\{b_1(v_1)<b_2(v_2)\wedge b_2(v_2)\geq b_1(1)\}\quad\mathrm{(Eq.03)} \end{equation} and each of the terms can be treated separately. The second one is simpler, because one event in the conjunction is consequence of the other (approximately, however it can be assumed that probabilities of exact values are zero), thus the consequence event can be eliminated: \begin{equation} \Pr\{b_1(v_1)<b_2(v_2)\wedge b_2(v_2)\geq b_1(1)\}=\Pr\{b_2(v_2)\geq b_1(1)\}\quad\mathrm{(Eq.04)} \end{equation} These probabilities can be calculated using the $g_i$'s, as long as the events to be measured determine the limits of integration. For (Eq.04), the calculation is: \begin{equation} \Pr\{b_2(v_2)\geq b_1(1)\}=\int_{b_2^{-1}(b_1(1))}^{1}\!g_2(v_2)\mathrm{d}v_2\quad\mathrm{(Eq.05)} \end{equation} The first term of (Eq.03) is a little more elaborate and needs a double integral on $v_1$ and $v_2$: \begin{equation} \Pr\{b_1(v_1)<b_2(v_2)\wedge b_2(v_2)<b_1(1)\}=\int_{0}^{b_2^{-1}(b_1(1))}\int_{0}^{b_1^{-1}(b_2(v_2))}g_2(v_2)g_1(v_1)\mathrm{d}v_1\mathrm{d}v_2\quad\mathrm{(Eq.06)} \end{equation} Thus the equation for $p_2$ described by the pdf's is: \begin{equation} p_2=\int_{0}^{b_2^{-1}(b_1(1))}\int_{0}^{b_1^{-1}(b_2(v_2))}g_2(v_2)g_1(v_1)\mathrm{d}v_1\mathrm{d}v_2\!+\!\int_{b_2^{-1}(b_1(1))}^{1}\!g_2(v_2)\mathrm{d}v_2\mathrm{. (Eq.07)} \end{equation} Complementarily, the obtention of $p_1$ initiates by defining \begin{equation} p_1=\Pr\{b_1(v_1)>b_2(v_2)\wedge b_2(v_2)<b_1(1)\}\mathrm{, (Eq.08)} \end{equation} because $\Pr\{b_1(v_1)>b_2(v_2)\wedge b_2(v_2)\geq b_1(1)\}=0$. From that, one obtains \begin{equation} p_1=\int_{0}^1\int_{0}^{b_2^{-1}(b_1(v_1))}g_1(v_1)g_2(v_2)\mathrm{d}v_2\mathrm{d}v_1\quad\mathrm{(Eq.09)} \end{equation} This deduction can be generalized for any integer $n$, and the outline of this generalization is: start by defining \begin{equation} P_{m|q}= \Pr\left\{\left(\bigwedge_{r\neq m}b_m(v_m)> b_r(v_r)\right)\bigwedge b_{q-1}(1)\leq b_m(v_m) < b_q(1)\right\}\quad\mathrm{(Eq.10)} \end{equation} where, by definition, $b_0(1)=0$, and it is implied that $b_r(v_r)<b_q(1),\forall r$. The rightmost event in (Eq.10), when varied in $q$, defines a partition of the probability space, so it is possible to define the probability $p_i$ of a player as \begin{equation} p_m=\sum\limits_{q=1}^{m} P_{m|q}\mathrm{, (Eq.11)} \end{equation} having in mind that $\Pr\{b_m(v_m)\geq b_q(1)\}=0$ for $q>m$. This fact has to be used when defining the limits of the nested integrals of the $g_i$'s.

In order to take better grasp on how this formulation can be concretized, the pdf's can be defined as $g_i=1,\forall i$, which corresponds to a uniform distribution in the interval $[0,1]$, and the bid functions defined as $b_i(v_i)=B_i v_i$, with $B_i$ scalar constant in the same interval $[0,1]$. This conducts to perhaps the simplest way to answer to the question on how to define the bid functions $b_i$'s when the winning probabilities $p_i$'s are given. However, the equations elaborated above are explicit for $p_i$ given $b_i$, so if it is assumed the other way around, as it was in the question initially posed, the equations have to be gathered in a system of equations that, when solved, allow to determine $B_i$'s for given $p_i$'s. Besides that, one of the $B_i$'s has to be arbitrated, because one of the probability equations is dependent on the others, since $p_i=1-\sum_{j\neq i}p_j$.

$\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.