CS535 HW2

(DevonThink) Assignment 2

Problem 1 §

In class algorithm uses regret bound of $\le 2\sqrt{T\ln N}$. Now consider this modified RWM algorithm. The game ends at time $\tau$ but we have no knowledge of it.

1. Initially $p_i^t=\frac{1}{N}\forall i\in X$
2. Let interval bound $T_i=2^i$. We start in the interval $T_0<t\le T_1$
   1. In this interval, we set $\eta =\text{min}\left(\sqrt{\frac{\ln N}{T_i}},\frac{1}{2}\right)$
   2. Then within this interval the regret $\le 2\sqrt{T_i\ln N}$
3. Once we reach the end of this interval, we move onto the next interval.
4. We reach the end of the algorithm when time is $\tau$. We are in the interval $T_k<t<T_{k+1}$ where $k$ is the largest integer that satisfies $2^k\le \tau$. Now, the regret at this point can be obtained by summing all regret from previous and current intervals:

$$\begin{array}{rl}\text{Regret}& \le \sum _{i=1}^{k}2\sqrt{2^i\ln N}\\ & \le 2\sqrt{2^{k+1}\ln N}\\ & =2\sqrt{T_{k+1}\ln N}\end{array}$$

Thus we have regret bound $2\sqrt{T_{k+1}\ln N}$ at time interval $\tau \le T_{k+1}$.

Problem 2 §

Problem 3 §

This is formulated as the online prediction problem, with the seller having the option to choose a price $\frac{1}{k},\frac{2}{k},\dots ,\frac{k-1}{k},\frac{k}{k}$ with the loss function what represents the foregone profit (that could have been captured).

$$l_i^t=\{\begin{array}{ll}{v}_i-k& \text{if sold, but at lower than willing to pay}\\ v_i& \text{if not sold}\end{array}$$

• Loss is zero when price is set to perfectly match the current buyer’s willingness to pay. Then, there are $n$ iterations of the game (since there are $n$ buyers), with $k$ different options for the seller. Thus the regret bound for a RWM Formulation of the game will be $\le 2\sqrt{n\ln k}$.

Problem 4 §

Problem 5 §

BNE §

The utility of player $i$ is

$${\mu }_i=\{\begin{array}{ll}{v}_i-b_i& \text{if gets item}\\ 0& \text{else}\end{array}$$

Then, assume other person bids $b_j=\frac{v_j}{2}$ where $v_j\sim \text{Unif}(0,1)$. Then, to maximize their expected utility player $i$ will:

$${\text{max}}_{b_i}\mathbb{E}({\mu }_i)=\text{max}(v_i-b_i)\cdot \underset{\text{ i’s bid is greater }}{\underbrace{\mathbb{P}\left(b_i>\frac{v_j}{2}\right)}}$$

Where $\mathbb{P}\left(b_i>\frac{v_j}{2}\right)=2b_i$ since $v_j$ is a uniform distribution. Then solve the maximization problem:

$${\text{max}}_{b_i}(v_i-b_i)2b_i$$

Solving this problem will yield $b_i=\frac{v_i}{2}$. This is shown symmetrically for the other agent.

Revenue §

The revenue of the seller is

$$\begin{array}{rl}R& =\{\begin{array}{ll}\frac{v_1}{2}& \text{given }{v}_1>v_2\\ \frac{v_2}{2}& \text{given }{v}_1<v_2\end{array}\\ \mathbb{E}(R)& =\mathbb{E}\left(\frac{v_1}{2}\mid v_1>v_2\right)+\mathbb{E}\left(\frac{v_2}{2}\mid v_1<v_2\right)\\ & =2\cdot {\int }_0^1\frac{v_1}{2}\cdot \underset{=\frac{f(v_1>v_2|v_1)}{f(v_1)}p(v_1>v_2)=\frac{v_1}{2}}{\underbrace{p(v_1|v_1>v_2)}}dx\\ & =\end{array}$$