Transcript Slide 1
Market Oriented Programming Sai Rahul Reddy P 7/17/2015 Market Oriented Programming 1 What is Market Oriented Programming ? Market-oriented programming (MOP) is a mathematical programming approach to distributed computation using selfish agents, based on market price mechanisms MOP exploits the institution of markets to solve particular problems of distributed resource allocation Comprises of two problems: Allocation and Pricing Inspired in part by economists (market mechanisms) and also by AI (heterogeneous, self interested agents) 7/17/2015 Market Oriented Programming 2 Basics of Micro Economics … Price Simple Supply and Demand curve Quantity 7/17/2015 Market Oriented Programming 3 Basics of Micro Economics … Price p1 Simple Demand curve p2 q1 7/17/2015 Quantity q2 Market Oriented Programming 4 Basics of Micro Economics … Supply Curve Price p2 p1 Quantity 7/17/2015 q1 Market Oriented Programming q2 5 Basics of Micro Economics … Equilibrium Price p1 pe q1 qe q2 Quantity 7/17/2015 Market Oriented Programming 6 Example: Mungi • Price per unit of storage is price(€) = 1 + 4p€2exp(€/(1- €) -1), € (0< €<1) is the storage utilization of the system • Taxation function is t(β) = b[1-exp(-β/b)], 7/17/2015 Market Oriented Programming 7 Example: Load Balancing Problem Cost of the job • The cost of buying μJ/rk CPU seconds at Pk. • The cost to cross the link to get to Pk. • The cost to get from the Pk to the processor at which J entered the system. Job Preferences • Price Preference • Service time preference • Service and price preference Economic Model Auctions 7/17/2015 Market Oriented Programming 8 Other Examples • Spawn Uses the monetary funding units as an abstract form of priority in distributed and heterogeneous systems. The use of price information to control adaptive expansion and contraction of process trees in concurrent applications. • Data Management Economy • Flow Control Economy • Quality of service in computer networks • Multiple Access Protocols 7/17/2015 Market Oriented Programming 9 Mechanism Design 6 Given: System comprising of self-interested, rational agents Set of system wide goals Mechanism Design Does there exist a mechanism that can implement the goals ? 7/17/2015 Market Oriented Programming 10 Example: System “ABC” ABC: A new breed of software agents?? System: One Seller with a single indivisible good N buyers (agents) each with value vi for the good (money value) vi is known only to agent i Value vi: Maximum value agent i is willing to pay for the good (Agent is indifferent between the good and the money value vi) Goals: G1: Sell the good to agent (buyer) with highest vi G2: The buying agent pays vi to the seller for the good 7/17/2015 Market Oriented Programming 11 First Price Sealed Bid Auction Mechanism Each agent submits a sealed bid to the seller Good is sold to the agent with the highest bid The winning agent pays the quoted bid value to the seller Does this mechanism implements G1 and G2? 7/17/2015 Market Oriented Programming 12 First Price Sealed Bid Auction: Agent Strategy Overbid If the agent wins, it has to pay more than it is worth Bid True Value vi If the agent wins, it has to pay its original value and the agent gains nothing Underbid Reduces the chance of winning Less the agent pays than vi more it gains Strategy: Bid slightly more than the expected second highest price 7/17/2015 Market Oriented Programming 13 Vickrey Auction Mechanism Each agent submits a sealed bid to the seller Good is sold to the agent with the highest bid The winning agent pays the second highest bid value to the seller Does this mechanism implements G1 and G2? 7/17/2015 Market Oriented Programming 14 Vickrey Auction : Agent Strategy Overbid X If the agent is the real winner and wins, it gains nothing If the agent is not the real winner and wins by overbidding, it may pay more than its value Underbid X If the agent is the real winner and wins, it gains nothing The agent may lose by underbidding Bid True Value vi Best Strategy Tell the truth independent of what agents do (Dominant Strategy) 7/17/2015 Market Oriented Programming 15 English Auction Mechanism Open out-cry ascending price auction Starts with a minimum bid value quoted by the seller Agent can revise the bid amount upward by a minimum increment Auction ends when bidding stops Highest bidder gets the object and pays the amount quoted Does this mechanism implements G1 and G2? 7/17/2015 Market Oriented Programming 16 Evaluation of Auctions ? • Allocation Efficiency • Revenues 7/17/2015 Market Oriented Programming 17 References 1. Ferguson, D., et al, Microeconomic algorithms for load balancing in distriuted computer systems, Proc. 8th Int'l Conf. Distributed Computing Systems. 2. Ferguson, D et al, Economic models for allocating resources in computer systems,Book: Market-based control: a paradigm for distributed resource allocation. 3. G. Heiser, F. Lam, and S. Russell, Resource Management in the Mungi SingleAddress-Space Operating System, Proceedings of Australasian Computer Science Conference. 4. http://en.wikipedia.org/en/Supply 5. Wellman, MP, Market-Oriented Programming: Some Early lessons, Book: Market-based control: a paradigm for distributed resource allocation 6. http://purana.csa.iisc.ernet.in/~mbk/jammin/kamesh.html (Slides Taken) 7/17/2015 Market Oriented Programming 18 7/17/2015 Market Oriented Programming 19 Load Balancing In Clusters Jobs Assignment For each machine in a cluster of n machines, with resources r1, r2, . . . rk. The machine’s cost is defined as k ∑f( n, utilization of ri ). i=1 Where f is some function. Jobs are assigned to resources in such a way to minimizes this marginal cost. Jobs Re-assignment When a job terminates we will check the stability condition for each job j and each machine M. If stability condition fails the job is reassigned in such a way that minimizes the marginal cost. 7/17/2015 Market Oriented Programming 20