RationalityasaParadigmforInternetComputing

, , , , , ,Slide,27,of 27,Noam Nisan,Rationality as a Paradigm forInternet Computing,Noam Nisan,Hebrew University, Jerusalem,Contents,The Internet and the new face of computing,Analyzing computing systems in equilibrium,Designing computational mechanisms,A defining problem: Combinatorial auctions,What is Computing?,20,th Century,(second half),21,st century,(first decade),von Neumann Machine,The Internet,The Internet,Huge dynamic heterogeneous distributed system “normal distributed CS”,Not centrally owned, different parts owned by different people, firms, or organizations with,differing goals, “CS+economics+game-theory”,TCP Retransmission Rule,Transmission Control Protocol,Used for most Internet communication,Breaks messages into packets, and,assembles the packets back into messages,Handles packet delay/loss,TCP Retransmission Rule,When a packet is lost, decrease transmission rate (by a factor of 2),Rational:,Network is congested fix it by reducing demand down to capacity,“Improved” Rule,When a packet is lost, start sending each packet twice,Rational:,Packets are lost fix it by increasing the probability that at least one copy of each packet arrives,Why not?,Internet Resource Sharing,The vision,everyone connected to the Internet should have access to all resources that are connected to the Internet,Examples:,CPU-time,Files,I/O devices,Data,Knowledge,Humans,Why share?,Electronic Commerce,How will computers talk business?,Using communication, security software, agents, ,Using standards: XML, .NET, J2EE, and other,TLAs,What will they say to each other?,“Book X costs Y”,“Bid X for Y units of stock Z”,“Heres a complicated offer to you guys: #$% ”,Internet Computing Protocols,Should take into account,Computational issues:,CPU time, communication, robustness, memory, languages, ,Incentive issues:,Selfishness, strategies, payments, coalitions, risk, ,Should combine the points of view of Computer Science and of economics,Should apply game theory in a computational context,Rational behavior is more easily assumed from computers than from humans,The strategy is in the software,At All Protocol Levels ,eCommerce,: eStores, auctions, exchanges, supply chains,Online Services:,games, web-hosting, ASPs,Information Resources,: music, databases,Computational resources:,CPU, disk space, proxies, caching,Network Infrastructure,: routing, admission control, QoS,Low level,(traditional CS domain),High level,(traditional business domain),The Price of Anarchy,Papadimitriou,Take a “normal” CS protocol that works well if everyone does what they should.,Say “Oh my god the participating computers may do whatever they want”,Analyze what happens when “they do whatever they want”,Radical departure from CS: “want”, utility rationality game-theory equilibrium,Aim to prove that things are still not too bad,Or else: argue against using on the Internet,Minimizing Packet Delay,Braesss Paradox,1,1,x,x,0,delay proportional,to load,constant,delay,Many “small”packets total quantity = 1,Each knows the delay situation,Each chooses how to get to destination,Minimizing Packet Delay,Braesss Paradox,1,1,x,x,0,Many “small”packets total quantity = 1,Each knows the delay situation,Each chooses how to get to destination,Optimal routing (delay = 1.5),1/2,0.5,0.5,1,1,1,1,0,Selfish routing (delay = 2.0),The Price of Anarchy is Low,Roughgarden&Tardos,Theorem:,for all network topologies, for all sets of routing requests, for all delay functions on the links:,If all delays are linear functions, then the previous example is as bad as it gets the price of anarchy is at most a factor of 4/3 in delay,For general delay functions, doubling the edge capacities compensates for selfishness the price of anarchy is at most a factor of 2 in infrastructure,Algorithmic Mechanism Design,Nisan&Ronen,Design the protocols so that they will work well under selfish behavior of participants,“work well” the usual computational optimization goals,“under selfish behavior” the usual game-theoretic concepts of equilibrium,Use notions and techniques from the economic field of Mechanism Design,“Inverse game-theory”,Concentrate on “incentive compatibility” (truthfulness),Equilibrium is reached when all players report their private information truthfully,The revelation principle shows that this is without loss of generality,VCG-Mechanism in CS,Vickrey-Clarke-Groves,Basic positive result in mechanism design,Allow monetary transfers to/from participants,Basic idea: internalize externalities,Each player pays/gets the total loss/benefit in utility he causes to all others,All players see the same goal: optimizing the total sum of players utilities,Shared,Cache,Caching XXX will save me 100$,Caching XXX will save me 10$,Caching XXX will cost me 80$,Pay 70 (=80-10),Clarke tax,Beyond Classical Mechanism Design,New domain of problems,Parameter-complexity: e.g. structure of network,Brave-new-world: disregard human conventions and biases,New optimization goals,Not just sum-of-utilities: e.g. make-span in scheduling,New limitations,Computational complexity,Distributed implementation,Interaction with usual mechanism design often problematic,New biases regarding solution concepts,Computer scientists dont like Bayesian analysis: real-world distributions are too different from those in our analysis worst-case will happen,Computer scientists are happy with approximations: optimality is often too hard,A Sampling of Some Recent Results,Selling “digital goods” (unlimited supply),Goldberg&Hartline&Wright,A randomized mechanism can approximate monopoly price revenue,Scheduling jobs on “unrelated machines”,Nisan&Ronen,No better than 2-approximation for the make-span is possible, but randomized mechanisms can do better,Scheduling jobs on “related machines”,Archer&Tardos,A polynomial time 3-approximation mechanism for the make-span,Cost-sharing for multicast transmissions,FPS,VCG mechanism can be implemented in linear communication,Auctions using a few bits,Blumrosen&Nisan,An auction with 1-bit from each player can achieve 98% efficiency,Combinatorial Auctions,Most mechanism design problems involve resource allocation,The central problem in classical mechanism design is an,auction,: how to allocate a single indivisible good?,Abstracts many resource allocation problems,English auction, Dutch auction, first price sealed-bid auction, ,Gold standard: Vickreys 2nd price auction,The emerging central problem in algorithmic mechanism design is a,combinatorial auction,: how to allocate a collection of goods, with complex dependencies between them?,Abstracts many complex resource allocation problems,Involves a wide spectrum of computational and game-theoretic issues,Combinatorial Auction Problem Definition,N,indivisible non-identical items are sold concurrently,k,bidders compete for subsets of these items,Each bidder,j,has a valuation for each set of items:,v,j,(S),= value that,j,assigns to acquiring the set,S,v,j,is monotonic non-decreasing (“free disposal”),Objective:,Find a partition,(S,1,S,k,),of,1.N,that maximizes the social welfare:,j,v,j,(S,j,).,Means:,protocol between bidders and auctioneer,Difficulties:,communication, computation, incentives,Complements and Substitutes,v,j,(),may have,complements,:,v,j,(S,T,),v,j,(S),+,v,j,(T),for some,S,and,T,.,Extreme case: “single-minded bid” - will only pay for a complete package - pay,p,for the set,S,but pay nothing for anything else,v,j,(),may have,substitutes,:,v,j,(S,T,),v,j,(S),+,v,j,(T),for some disjoint,S,and,T,.,Extreme case: “unit demand bid” - will pay for at most a single item the price may depend on the item,Routing as a Combinatorial Auction,Bidder A,Bidder B,Bidder C,Each bidder wants to buy some path to the destination,Each link is an item,Destination,The FCC Spectrum Auctions,The FCC auctions spectrum licenses for many geographic regions and various frequency bands,These auctions have raised billions of dollars,The value of a license to a bidder depends on the other licenses it holds,Currently licenses are,sold in a simultaneous,auction,USA Congress mandated,that the next spectrum,auction be made,combinatorial.,3.1-3.2,GHz,3.2-3.3,GHz,3.3-3.4,GHz,3.1-3.2,GHz,3.2-3.3,GHz,3.1-3.2,GHz,3.2-3.3,GHz,3.1-3.2,GHz,3.2-3.3,GHz,3.1-3.2,GHz,3.2-3.3,GHz,3.3-3.4,GHz,Basic Mechanism Design Approach,Basic Solution,Each bidder sends,v,j,(),to auctioneer.,Auctioneer finds the partition that maximizes,j,v,j,(S,j,).,Auctioneer allocates,S,j,to each bidder,j,Auctioneer charges VCG payments ensures incentive compatibility,Computational difficulties,Bidding,: How to send,v,j,()?,Requires communication of,numbers impractical,Allocation,: How can the auctioneer find an optimal allocation? The problem is computationally intractable (even to approximate well),Bidding Languages,The auction must fix a “language” for representing valuations. All bidders will use that language to express their valuations,Language must be,expressive,: express all reasonable valuations succinctly,Language must be,simple,: computationally easy to manage valuations (represent, determine allocation,),Proposed languages use: package bids, OR, XOR,(left-sock & right-sock : 5$),OR,( (Red-shirt : 10$) XOR (blue-shirt : 9$),Different bidding languages have different power,What should the FCC allow?,Iterative Auctions,Definition:,The demand of valuation,v,at item prices,p,1, p,n,is the set S that maximizes the benefit:,v(S)-,i,S,p,i,A Walrasian equilibrium is an allocation,S,1,S,m,and item prices,p,1, p,n,such that each,S,j,is the demand of,v,j,at these prices,Fact:,Any Walrasian equilibrium gives an optimal allocation,Algorithm:,Demange&Gale&Sotomayor,initialize prices of all items to 0,repeat: if an item is demanded by more than one bidder, increase the price a little; until a Walrasian equilibrium is reached,Theorem:,This works if valuations are “gross substitutes”,Kelso&Crawford,Theorem:,In general, exponential communication (equivalently, an exponential number of prices) is needed,Nisan&Segal,Allocation Algorithms,The allocation problem is computationally intractable,Approaches for overcoming computational difficulty,Solve (or approximate) special tractable cases,Gross substitutes,Kelso&Crawford,Sub-modular (2-approximation),Lehmann&Lehmann&Nisan,Linear order on items,Rothkopf&Pekec&Harstad,Heuristics that obtain optimal allocations and run “reasonable fast”,Practical for 100s of items,CABOB -,Sandholm et al.,Heuristics that run quickly and find “reasonably good” solutions,A few % loss for 1000s of items,Zurel&Nisan,Use the usual tools of combinatorial optimization,LP relaxation,Branch-and-bound, cutting-planes,Local search,Dynamic programming,Incentives vs. Allocation,Challenge:,find a mechanism that obtains “reasonably good” allocations and is computationally efficient.,Key problem:,Algorithms that find sub-optimal allocations do not yield incentive compatible mechanisms,Attaching VCG payments to sub-optimal algorithms essentially never yields incentive compatibility,Nisan&Ronen,The only known incentive compatible mechanisms are VCG; for “complete spaces” with at least 3 possible outcomes only VCG mechanisms exist.,Roberts, Green&Laffont,Special case,: single minded bidders have a single valuation parameter and desire a single package,A Computationally efficient incentive compatible mechanism exists,Lehmann&Ocallaghan&Shoham,Open problem,: Find any non-VCG mechanism for any multi-dimensional valuation space,