New version page

Stanford CS 206 - Homework

Documents in this Course
Load more
Upgrade to remove ads
Upgrade to remove ads
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
Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?