Games of incomplete information Flashcards
Auction
Any protocol that allows agents to indicate their interest in one or more resources, and that uses these indications to determine both the resource allocation and payments of the agents.
Auction variants
Single-item auctions: n bidders compete for a single indivisible item that can be allocated to just one of them. Each bidder has his own private value of the item in case he wins. Typically the highest bidder wins.
Multiunit auctions: Fixed number of identical units of a homogeneous commodity are sold. Each bidder submits both the number of units and the unit price he is willing to pay. Here also usually the highest bidders win, but it is unclear how much should they pay.
Combinatorial auctions: Bidders compete for a set of distinct goods.
Single-item auctions
Open auctions:
The English auction: the price of the item goes up as long as someone is willing to bid higher.
The Dutch auction: the price starts at a prohibitively high value and the value goes down. Once a bidder shouts buy, it stops.
Sealed-bid auctions (k-th price): Each bidder writes down his bid and places it in an envelope, the envelopes are opened simultaneously. The highest bidder wins and then pays the k-th maximum bid.
Strict incomplete information game
G = (N, (Ai), (Ti), (ui))
N = {1, …, n} set of players
Ai is a set of actions available to player i. A is the set of all action profiles a = (a1, …, an)
Ti is a set of possible types of player i. T is the set of all type profiles t = (t1, …, tn)
ui is a type-dependent payoff function ui: A1 x A2 x … x An x Ti -> R
Pure strategy in an incomplete information game
A pure strategy of player i is a function si: Ti -> Ai.
Dominance in an incomplete information game
A pure strategy si very weakly dominates si’ if for every ti the following holds: For all a-i we have that ui(si(ti), a-i; ti) >= ui(si’,a-i;ti).
A pure strategy si weakly dominates si’ != si if for every ti satisfying si(ti) != si’(ti) the following holds: For all a-i we have that ui(si(ti), a-i; ti) >= ui(si’,a-i;ti), and the inequality is strict for at least one a-i.
A pure strategy si weakly dominates si’ != si if for every ti satisfying si(ti) != si’(ti) the following holds: For all a-i we have that ui(si(ti), a-i; ti) > ui(si’,a-i;ti).
Ex-post Nash equilibrium
A strategy profile s = (s1,…,sn) is an ex-post Nash equilibrium if for every t1,…,tn we have that (s1(t1),…sn(tn)) is a NE in the strategic-form game defined by tis.
Formally, s is an ex-post NE if for all i and all t1,…,tn and all ai: ui(s1(t1),…,sn(tn); ti) >= ui(ai, s-i; ti)
Second-price auction ex-post NE
For every player i we have that vi is a weakly dominant strategy, so v is also an ex-post NE.
1] case bi < vi
A: If bi > max_i!=j bj then ui(bi,b-i;vi) = vi - max_i!=j bj = ui(vi,b-i;vi)
B: If there is k!=i such that bk > max_k!=j bj then ui(bi,b-i;vi) = 0 <= ui(vi,b-i;vi)
C: If there are k!=l such that bk = bl = max_j bj then ui(bi,b-i;vi) = 0 <= ui(vi,b-i;vi)
2] case bi > vi
A: If bi > max_j!=i bj > vi, then ui(bi, b-i;vi) = vi - max_J!=i bj < 0 = ui(vi,b-i;vi)
B: If bi > vi >= max_j!=i bj > vi, then ui(bi, b-i;vi) = vi - max_J!=i bj = ui(vi,b-i;vi)
C: If there is k!=i such that bk > max_k!=j bj > vi then ui(bi,b-i;vi) = 0 = ui(vi,b-i;vi)
D: If there are k!=k’ such that bk = bk’ = max_j bj > vi then ui(bi,b-i;vi) = 0 = ui(vi,b-i;vi)
First-price auction NE
Has no NE
Assume that s is a NE. Consider 0<v1<…<vn-1 and define M = max si(vi). Consider vn = M+1. In player n wins, i.e. sn(vn) > M, then un(sn(vn), s-n(v-n);vn) = vn - sn(vn) < vn - (sn(vn) - eps) = un(sn(vn) - eps, s-n(v-n); vn) for eps > 0 small enough to satisfy sn(vn)-eps > M.
If player n does not win, i.e. sn(vn) <= M < M+1 = vn then for eps=1/2: un(sn(vn),s-n(v-n);vn) = 0 < eps = un(vn-eps, s-n(vn); vn)
Bayesian game
G = (N, (Ai), (Ti), (ui), P)
N = {1, …, n} set of players
Ai is a set of actions available to player i. A is the set of all action profiles a = (a1, …, an)
Ti is a set of possible types of player i. T is the set of all type profiles t = (t1, …, tn)
ui is a type-dependent payoff function ui: A1 x A2 x … x An x Ti -> R
P is a (joint) distribution over T called a common prior
P(t-i|ti)
Given a type profile t, we denote by P(t-i|ti) the conditional probability that the oponents of player i have type profile t-i conditioned on player i having ti, i.e. P(t-i|ti) = P(ti, t-i)/Sum_t’-i P(ti, t’-i)
Expected payoff in Bayesian games
Given a pure strategy profile s and a type ti of player i the expected payoff for player i is ui(s;ti) = Sum_t-i P(t-i|ti) * ui(s1(t1),…,sn(tn);ti)
Pure strategy Bayesian NE
A pure strategy profile s is a pure strategy Bayesian NE if for each player i and each type ti of player ei and every strategy si’, we have that ui(si,s-i;ti) >= ui(si’,s-i;ti)
Bayesian NE in auctions
Second-price auction: bidding vi
First-price auction: bidding (n-1)/n * vi
Revenue equivalence
Assume that each of n risk-neutral players has independent private values drawn from a common cumulative distribution function F(x) which is continuous and strictly increasing on an interval [vmin, vmax]. Then any efficient auction mechanism in which any player with value vmin has an expected payoff of zero yields the same expected revenue.
*Efficient = has a symmetric and increasing Bayesian NE and always allocates the item to the player with the highest bid.
