[SOLVED] Cs3333 game theory with computer science applications homework 3

Problem 1. Suppose we modify the multiplicative weights algorithm for the best expert problem given in the lecture notes so that the weight update step is ωt+1(i) := ωt(i)(1 − ϵct(i))
(rather than ωt+1(i) := ωt(i)(1−ϵ)
ct(i)
). Show that this algorithm also has regret O(
p
T lnn).Problem 2. Consider a first-price auction with two bidders, whose valuations are i.i.d. with
uniform distribution, i.e., vi ∼ Uniform[0,1]. Let µi (vi) be the bid of bidder i when its valuation is vi
. Assume that the bidders use only affine µi
, i.e., µi (vi) = cvi +d. Find c, and d such
that ©
µi
,i = 1,2ª
form a Bayesian-Nash equilibrium for this game.Problem 3. Consider the following Cournot competition with I firms. For each firm i, the
strategy is to choose a quantity qi ∈ (0,∞), and the payoff function is ui(qi
,q−i) = qi(P(Q)−c),
where P(Q) with Q =
PI
i=1
qi denotes the inverse demand (price) function.Show that this
game is an ordinal potential game. The definition of ordinal potential game is as follows: An
ordinal potential game exists if there is a potential function Φ : S → R such that for all agents
i with strategy si
,
Φ(si
,s−i)−Φ
¡
s
′
i
,s−i
¢
> 0 iff ui (si
,s−i)−ui
¡
s
′
i
,s−i
¢
> 0.Problem 4. Consider an online learning setting where loss vectors ℓ
1
,ℓ
2
,… ∈ [0,1]d
are
observed. Prove that we could always choose weights w
1
,w
2
,… ∈ ∆
d
(probability simplex) so
that
∀ϵ > 0, ∃T s.t.
1
T
Ã
X
T
t=1
ℓ
t
·w
t −
X
T
t=1
ℓ
t
i
!
≤ ϵ, ∀i.(Hint: Reduce the above problem to apply the Blackwell Approachability Theorem. Utilize the
equivalence between the following two conditions: (1) ∀q∃p s.t. r (p,q) ∈ S; and (2) For all
half-spaces H containing S, ∃p s.t. ∀q, r (p,q) ∈ H.)Problem 5. Prove the revenue equivalence theorem between second-price auction and allpay auction for N bidders with i.i.d. uniform distribution vi ∼ Uniform[0,1] on single item. In
all-pay auction, each bidder pay his/her bid, regardless of whether being allocated, and the
bidder with the highest bid is allocated the item. (Hint: First prove the equilibrium bidding
function is bi(vi) =
N−1
N
v
N
i
.)