New version page

# Stanford CS 206 - Homework

Pages: 2
Documents in this Course

4 pages

41 pages

23 pages

61 pages

Unformatted text preview:

Homework 5: Auctions due Tuesday, May 21, 2002, in classCS206 Technical Foundations of Electronic CommerceHomework 5: Auctions due Tuesday, May 21, 2002, in class1. Consider a combinatorial auction in which n distinct goods are offered. Alice, a bidder in the auction, has a downward-sloping valuation: she values any of the n goods at p1; having won any one good, she values a second good at p2, having won any two goods she values a third at p3, and having won any three goods she values all additional goods at 0. In addition, p1 > p2 > p3. Of course, the bid she submits to the auctioneer will depend on the bidding language used in the auction. For each of the following bidding languages, state whether Alice’s valuation can be represented and ifso describe the most compact representation and its size as a function of n. You are not required to formally prove that you have found the most compact representation, but please justify your answer.a. Explicitly listing all subsets for which she has a non-zero valuation.b. OR with no dummy goods.c. OR with dummy goods.d. OR of XOR.e. XOR of OR.2. Consider a combinatorial auction for five goods, 1, 2, 3, 4, and 5, with bids from four bidders, A, B, C, and D. They submit the following bids, using the OR bidding language:Bidder Bids (goods, amount)A (124, \$45); (1, \$9); (24, \$19); (2, \$7); (4, \$8)B (235, \$39); (135, \$36); (35, \$28); (3, \$10); (5, \$8)C (2345, \$42); (23, \$20); (24, \$18); (25, \$17); (2, \$12)D (1, \$40)Bidders’ payments are determined according to the Generalized Vickrey Auction (or “VCG”) as described in class. What are the winning bids, and what does each bidder pay? (To refer to a bid, give the bidder’s name and the order in the list above; e.g., B’sbid for the bundle 135 is B-2.) You may solve this problem by hand or with the aid of a computer.3.A three-month period of a Hawaiian timeshare is auctioned off. People can bid for anynumber of consecutive whole months during the period Jan-Mar. The following bidsare in (all durations are inclusive of the first and last month):Bid 1: (Jan, \$50)Bid 2: (Jan-Feb, \$80)Bid 3: (Jan-Mar, \$150)Bid 4: (Feb, \$40)Bid 5: (Feb-Mar, \$110)Bid 6: (Mar, \$20)A naïve combinatorial auction is conducted. What is the outcome of the auction?Show how you arrive at your answer by simulating the operation of an O(n2)algorithm on the bids.4. A combinatorial auction is carried out for three items -- apple (A), orange (O), andbanana (B). Two bids are in -- Alice bids for {AB} and Bob for {OB}. a. Show the LP constraint for this problem in matrix form.b. Is the bid matrix TU? Justify your

View Full Document