Communication NetworksMechanism DesignIntroduction to AuctionsSlide 4Slide 5Envelope TheoremSlide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Vickrey-Clarke-GroveSlide 15Slide 16Bidding for QoSSlide 18Slide 19Communication NetworksA Second CourseJean WalrandDepartment of EECSUniversity of California at BerkeleyMechanism Design•Introduction to Auctions•First Price•Second Price•Revenue Equivalence•Vickrey-Clarke-Grove•Bidding for QoSIntroduction to Auctions•Example:•Alice and Bob bid for a House.•Alice values the house at v1, Bob at v2.•Alice bids b1, Bob bids b2.•We examine two auctions: •Sealed Bid, First Price•Sealed Bid, Second PriceIntroduction to AuctionsSealed Bid – First Price:Item goes to highest bidder who pays the highest bid.Alice’s net reward is (v1 – b1)1{b1 > b2}.There is no dominant strategy: Alice’s best bid is min{v1, b2 + ,which depends on b2. The unique Nash Equilibrium is b1 = min{v1, v2 + } b2 = min{v2, v1 + }Introduction to AuctionsSealed Bid – First Price: Incomplete information, symmetric. Sealed Bid – First Price: Incomplete information, symmetric.Envelope TheoremEnvelope TheoremEnvelope TheoremEnvelope TheoremIntroduction to AuctionsSealed Bid – First Price: Incomplete information, symmetric. Sealed Bid – First Price: Incomplete information, symmetric.Introduction to AuctionsSealed Bid – Second Price:Item goes to highest bidder who pays the second highest bid.[Equivalent to ascending public auction.] Fact (Vickrey): Dominant strategy: Alice bids truthfully: b1 = v1. [Incentive compatible] Proof: Alice’s reward is A = (v1 – z)1{b1 > z} where z is the second highest bid. Note that (v1 – z)1{v1 > z} ≥ (v1 – z)1{b1 > z}, as you see by looking at v1 > z and v1 < z.Sealed Bid – Second Price:Item goes to highest bidder who pays the second highest bid.[Equivalent to ascending public auction.] Fact (Vickrey): Dominant strategy: Alice bids truthfully: b1 = v1. [Incentive compatible] Proof: Alice’s reward is A = (v1 – z)1{b1 > z} where z is the second highest bid. Note that (v1 – z)1{v1 > z} ≥ (v1 – z)1{b1 > z}, as you see by looking at v1 > z and v1 < z.Introduction to AuctionsIncomplete information, symmetric – Revenue Equivalence. Incomplete information, symmetric – Revenue Equivalence.Introduction to AuctionsIncomplete information, symmetric – Revenue Equivalence. Incomplete information, symmetric – Revenue Equivalence.Vickrey-Clarke-GroveIn second price, the winning agent pays the reduction in declared welfare of the other agents.Indeed, if the bids are b1 > b2 > …>bn, the first agent gets the item instead of the second. Consequently, the declared welfare of agents {2, 3, …, n} is now zero whereas it would be equal to b2 if agent 1 were not there. The reduction in welfare of agents {2, 3, …, n} caused by agent 1 is b2, which is the payment of agent 1 when she wins the bid.This payment internalizes the externality caused by agent 1 and forces her to bid truthfully. The VCG mechanisms generalize this idea.In second price, the winning agent pays the reduction in declared welfare of the other agents.Indeed, if the bids are b1 > b2 > …>bn, the first agent gets the item instead of the second. Consequently, the declared welfare of agents {2, 3, …, n} is now zero whereas it would be equal to b2 if agent 1 were not there. The reduction in welfare of agents {2, 3, …, n} caused by agent 1 is b2, which is the payment of agent 1 when she wins the bid.This payment internalizes the externality caused by agent 1 and forces her to bid truthfully. The VCG mechanisms generalize this idea.Vickrey-Clarke-GroveVickrey-Clarke-GroveBidding for QoS•Assume there are K different service classes•Class k can accept N(k) connections and offers them a loss rate 1 – p(k). Assume N(K) is infinite.•User i bids xi for his connection, i = 1, …, m. Here, xi is the declared value per unit rate of the connection for user i.•Mechanism: •Assume b(1) > b(2) > ….•Place the first N(1) users in class 1, the next N(2) in class 2, and so on.•Price: C(i) for user i where C(i) is the reduction in declared value of all the customers i + 1, …, m caused by the presence of i.Bidding for QoSBidding for QoSShu and Varaiya, to appear in JSAC 06.Shu and Varaiya, to appear in JSAC
View Full Document
Unlocking...