DOC PREVIEW
CMU CS 15892 - Auctioning one item

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 41 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Auctioning one itemAuctionsAuction settingsAuction protocols: All-payAuction protocols: English (first-price open-cry = ascending)Auction protocols: First-price sealed-bidStrategic underbidding in first-price sealed-bid auctionStrategic underbidding in first-price sealed-bid auction…Auction protocols: Dutch (descending)Slide 10Auction protocols: Vickrey (= second-price sealed bid)Vickrey auction is a special case of Clarke tax mechanismResults for private value auctionsMore generally: revenue equivalence [version from Nisan’s review book chapter]Slide 15Revenue equivalence holds also for non-private values settings (settings with signals) as long as the setting is symmetric [see, e.g., Krishna: “Auction Theory”]Revenue equivalence ceases to hold if agents are not risk-neutralRevenue equivalence ceases to hold if agents have budget constraintsRevenue equivalence might not hold between 1st and 2nd-price auctions if distributions are asymmetricRevenue-maximizing (aka optimal) auction for private values setting [see Sec. 13.2 of “Algorithmic Game Theory”]Results for non-private value auctionsResults for non-private value auctions...Slide 24Slide 25Slide 26Slide 27Vulnerability to bidder collusion [even in private-value auctions]Vulnerability to shillsVulnerability to a lying auctioneerAuctioneer’s other possibilitiesUndesirable private information revelationUntruthful bidding with local uncertainty even in VickreyWasteful counterspeculationSnipingSlide 36Sniping…Slide 40Mobile bidder agents in eMediatorSlide 42Mobile bidder agents in eMediator...Conclusions on 1-item auctionsAuctioning one item Tuomas SandholmComputer Science Department Carnegie Mellon UniversityAuctions•Methods for allocating goods, tasks, resources...•Participants: auctioneer, bidders•Enforced agreement between auctioneer & winning bidder(s)•Easily implementable e.g. over the Internet–Many existing Internet auction sites•Auction (selling item(s)): One seller, multiple buyers–E.g. selling a bull on eBay•Reverse auction (buying item(s)): One buyer, multiple sellers–E.g. procurement•We will discuss the theory in the context of auctions, but same theory applies to reverse auctions –at least in 1-item settingsAuction settings•Private value : value of the good depends only on the agent’s own preferences–E.g. cake which is not resold or showed of•Common value : agent’s value of an item determined entirely by others’ values–E.g. treasury bills•Correlated value : agent’s value of an item depends partly on its own preferences & partly on others’ values for it–E.g. auctioning a transportation task when bidders can handle it or reauction it to othersAuction protocols: All-pay•Protocol: Each bidder is free to raise his bid. When no bidder is willing to raise, the auction ends, and the highest bidder wins the item. All bidders have to pay their last bid•Strategy: Series of bids as a function of agent’s private value, his prior estimates of others’ valuations, and past bids•Best strategy: ?•In private value settings it can be computed (low bids)•Potentially long bidding process•Variations–Each agent pays only part of his highest bid–Each agent’s payment is a function of the highest bid of all agents•E.g. CS application: tool reallocation [Lenting&Braspenning ECAI-94]Auction protocols: English (first-price open-cry = ascending)•Protocol: Each bidder is free to raise his bid. When no bidder is willing to raise, the auction ends, and the highest bidder wins the item at the price of his bid•Strategy: Series of bids as a function of agent’s private value, his prior estimates of others’ valuations, and past bids•Best strategy: In private value auctions, bidder’s ex post equilibrium strategy is to always bid a small amount more than current highest bid, and stop when his private value price is reached–No counterspeculation, but long bidding process•Variations–In correlated value auctions, auctioneer often increases price at a constant rate or as he thinks is appropriate–Open-exit: Bidder has to openly declare exit without re-entering possibility => More info to other bidders about the agent’s valuationAuction protocols: First-price sealed-bid•Protocol: Each bidder submits one bid without knowing others’ bids. The highest bidder wins the item at the price of his bid–Single round of bidding•Strategy: Bid as a function of agent’s private value and his prior estimates of others’ valuations•Best strategy: No dominant strategy in general–Strategic underbidding & counterspeculation–Can determine Nash equilibrium strategies via common knowledge assumptions about the probability distributions from which valuations are drawnStrategic underbidding in first-price sealed-bid auctionExample 1N risk-neutral biddersCommon knowledge that their values are drawn independently, uniformly in [0, vmax]Claim: In symmetric Nash equilibrium, each bidder i bids bi = b(vi) = vi (N-1) / NProof. First divide all bids by vmax so bids were in efect drawn from [0,1]. We show that an arbitrary agent, agent 1, is motivated to bid b1 = b(v1) = v1 (N-1) / N given that others bid b(vi) = vi (N-1) / NProb{b1 is highest bid} = Pr{b1 > b2} … Pr{b1 > bN}= Pr{b1 > v2 (N-1)/N} … Pr{b1 > vN (N-1)/N}= Pr{b1 > v2 (N-1)/N)}N-1 = Pr{b1 N / (N-1) > v2}N-1 = (b1 N / (N-1))N-1E[u1|b1] = (v1-b1) Prob{b1 is highest bid} = (v1-b1) (b1 N / (N-1))N-1dE[u1|b1] / db1 = (N/(N-1))N-1 (-N b1N-1 + v1 (N-1) b1N-2) = 0<=> N b1N-1 = v1 (N-1) b1N-2 | divide both sides by b1N-2  0 N b1 = v1 (N-1)<=> b1 = v1 (N-1) / N ■Strategic underbidding in first-price sealed-bid auction…•Example 2–2 risk-neutral bidders: A and B–A knows that B’s value is 0 or 100 with equal probability–A’s value of 400 is common knowledge–In Nash equilibrium, B bids either 0 or 100, and A bids 100 +  (winning more important than low price)Auction protocols: Dutch (descending)•Protocol: Auctioneer continuously lowers the price until a bidder takes the item at the current price•Strategically equivalent to first-price sealed-bid protocol in all auction settings•Strategy: Bid as a function of agent’s private value and his prior estimates of others’ valuations•Best strategy: No dominant strategy in general–Lying (down-biasing bids) & counterspeculation–Possible to determine Nash equilibrium strategies via common knowledge assumptions regarding the probability


View Full Document

CMU CS 15892 - Auctioning one item

Documents in this Course
Lecture

Lecture

35 pages

Load more
Download Auctioning one item
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 Auctioning one item 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 Auctioning one item 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?