DOC PREVIEW
CMU CS 15892 - Multi-item auctions and exchanges

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 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 22 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 22 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 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Multi-item auctions & exchanges (multiple distinguishable items for sale)Multi-item auctionsInefficient allocation in interrelated auctionsLying in interrelated auctionsMechanism design for multi-item auctionsMechanism design for multi-item auctions...Slide 7Space of allocationsDynamic programming for winner determinationNP-completenessPolynomial time approximation algorithms with worst case guaranteesSlide 12Restricting the allowable combinations that can be bid on to get polytime winner determination [Rothkopf et al. Mgmt Sci 98]Slide 14Item graphs [Conitzer, Derryberry, Sandholm AAAI-04]Clearing with item graphsApplication: combinatorial rentingApplication: conditional awarding of itemsGeneralization: substitutability [Sandholm IJCAI-99, AIJ-02]Side constraints in marketsComplexity implications of side constraints [Sandholm & Suri IJCAI-01 workshop on Distributed Constraint Reasoning]That’s all for today…Multi-item auctions & exchanges (multiple distinguishable items for sale)Multi-item auctions•Auctioning multiple distinguishable items when bidders have preferences over combinations of items: complementarity & substitutability•Example applications–Allocation of transportation tasks–Allocation of bandwidth•Dynamically in computer networks•Statically e.g. by FCC–Manufacturing procurement–Electricity markets–Securities markets–Liquidation–Reinsurance markets–Retail ecommerce: collectibles, flights-hotels-event tickets–Resource & task allocation in operating systems & mobile agent platformsInefficient allocation in interrelated auctionsProp. [Sandholm ICMAS-96]. If agents with deterministic valuations treat Vickrey auctions of interdependent goods without lookahead regarding later auctions, and bid truthfully, the resulting allocation may be suboptimalt1 auctioned firstAgent 1 bids c1({t1}) = 2Agent 2 bids c2({t1}) = 1.5t1 allocated to Agent 2t2 auctioned nextAgent 1 bids c1({t2}) = 1Agent 2 bids c2({t2}) = 1.5t2 allocated to Agent 1(or Agent 2 bids c2({t1,t2}) - c2({t1}) = 1=> either agent may get t2)t2t1Agent 1Agent 20.50.51.0Optimal allocation: Agent 1 handlesboth tasksLying in interrelated auctionsProp. [Sandholm ICMAS-96]. If agents with deterministic valuations treat Vickrey auctions of interdependent goods with full lookahead regarding later auctions, their dominant strategy bids can differ from the truthful ones of the corresponding isolated auctionsIn the second auction (of t2)Agent 1 bids c1({t1, t2}) - c1({t1}) = 0 if it has t1, and c1({t2}) = 1 if not.Agent 2 bids c2({t1, t2}) - c2({t1}) = 1 if it has t1, and c2({t2}) = 1.5 if not.So, t1 is worth 1.5 to Agent 1 in the second auction (worth 0 to Agent 2)So, in the first auction (of t1)Agent 1 bids c1({t1}) - 1.5 and winst2t1Agent 1Agent 20.50.51.0Lookahead requires counterspeculationPowerful contracts, decommitting, recontractingMechanism design for multi-item auctions•Sequential auctions–How should rational agents bid (in equilibrium)?•Full vs. partial vs. no lookahead•Would need normative deliberation control methods –Inefficiencies can result from future uncertainties•Parallel auctions–Inefficiencies can still result from future uncertainties–Postponing & minimum participation requirements•Unclear what equilibrium strategies would be•Methods to tackle the inefficiencies–Backtracking via reauctioning (e.g. FCC [McAfee&McMillan96])–Backtracking via leveled commitment contracts [Sandholm&Lesser95,AAAI-96, GEB-01] [Sandholm96] [Andersson&Sandholm98a,b]•Breach before allocation•Breach after allocationMechanism design for multi-item auctions...•Combinatorial auctions [Rassenti,Smith&Bulfin82]...–Bids can be submitted on combinations (bundles) of items–Bidder’s perspective•Avoids the need for lookahead•(Potentially 2#items valuation calculations)–Auctioneer’s perspective: •Automated optimal bundling of items•Winner determination problem: –Label bids as winning or losing so as to maximize sum of bid prices (= revenue  social welfare)–Each item can be allocated to at most one bid•Exhaustive enumeration is 2#bidsSpace of allocations#partitions is (#items#items/2), O(#items#items) [Sandholm et al. AAAI-98, AIJ-99, Sandholm AIJ-02]Another issue: auctioneer could keep items{1}{2}{3}{4} {1},{2},{3,4} {3},{4},{1,2} {1},{3},{2,4} {2},{4},{1,3} {1},{4},{2,3} {2},{3},{1,4} {1},{2,3,4} {1,2},{3,4} {2},{1,3,4} {1,3},{2,4} {3},{1,2,4} {1,4},{2,3} {4},{1,2,3} {1,2,3,4}Level(4)(3)(2)(1)Dynamic programming for winner determination•Uses (2#items), O(3#items) operations independent of #bids–(Can trivially exclude items that are not in any bid)–Does not scale beyond 20-30 items1231,21,32,31,2,3[Rothkopf et al. Mgmt Sci 98]NP-completeness•NP-complete [Rothkopf et al Mgmt Sci 98]–Weighted set packing [Karp 72]•[For an overview of worst-case complexity results of the winner determination problem, see review article by Lehmann, Mueller, and Sandholm in the textbook Combinatorial Auctions, MIT Press 2006–available at www.cs.cmu.edu/~sandholm]Polynomial time approximation algorithms with worst case guaranteesGeneral case•Cannot be approximated to k = #bids1-  (unless probabilistic polytime = NP)–Proven in [Sandholm IJCAI-99, AIJ-02]–Reduction from MAXCLIQUE, which is inapproximable [Håstad96]•Best known approximation gives k = O(#bids / (log #bids)2 ) [Haldorsson98] value of optimal allocationk = value of best allocation foundPolynomial time approximation algorithms with worst case guaranteesSpecial cases•Let  be the max #items in a bid: k= 2 / 3 [Haldorsson SODA-98]•Bid can overlap with at most  other bids: k= min( (+1) / 3 , (+2) / 3,  / 2 ) [Haldorsson&Lau97;Hochbaum83]•k= sqrt(#items) [Haldorsson99]•k= chromatic number / 2 [Hochbaum83]–k=[1 + maxHG minvH degree(v) ] / 2 [Hochbaum83]–Planar: k=2 [Hochbaum83]•So far from optimum that irrelevant for auctions•Probabilistic algorithms?•New special cases, e.g. based on prices [Lehmann et al. 01]Restricting the allowable combinations that can be bid on to get polytime winner determination [Rothkopf et al. Mgmt Sci 98]1234561 2 3 4 5 6 7|set|  2 or |set| > #items / cO(#items2) or O(#items3)O(nlargec-1 #items3)NP-complete already if 3 items per bid are allowedGives rise to the same economic inefficiencies that prevail in


View Full Document

CMU CS 15892 - Multi-item auctions and exchanges

Documents in this Course
Lecture

Lecture

35 pages

Load more
Download Multi-item auctions and exchanges
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 Multi-item auctions and exchanges 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 Multi-item auctions and exchanges 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?