(DevonThink) Assignment 2

Problem 1

In class algorithm uses regret bound of . Now consider this modified RWM algorithm. The game ends at time but we have no knowledge of it.

  1. Initially
  2. Let interval bound . We start in the interval
    1. In this interval, we set
    2. Then within this interval the regret
  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 . We are in the interval where is the largest integer that satisfies . Now, the regret at this point can be obtained by summing all regret from previous and current intervals:

Thus we have regret bound at time interval .

Problem 2

Problem 3

This is formulated as the online prediction problem, with the seller having the option to choose a price with the loss function what represents the foregone profit (that could have been captured).

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

Problem 4

Problem 5


The utility of player is

Then, assume other person bids where . Then, to maximize their expected utility player will:

Where since is a uniform distribution. Then solve the maximization problem:

Solving this problem will yield . This is shown symmetrically for the other agent.


The revenue of the seller is