Engineering systems vs Engineering agents Preferences and Utility Rationality and protocol design Example: Clarke tax Clarke tax Example Example Solution concepts Solution concepts Stability Nash equilibrium Nash equilibrium Nash equilibrium Nash equilibrium Nash equilibrium Selecting between equilibria Bilateral and multilateral negotiation Auctions Auctions English auctions First-price sealed-bid auction Dutch auction Vickrey auction Example Proof Proof Vickrey Auctions in real life Advantages and disadvantages Common and correlated-value auctions Winner's curse Winner's curse Combinatorial auctions Combinatorial auctions Winner-determination problem Winner-determination problem Winner-determination problem Winner-determination problem Current research issues SummaryDistributed Software DevelopmentSelf-interested MASChris BrooksDepartment of Computer ScienceUniversity of San FranciscoDepartment of Computer Science — University of San Francisco – p. 1/??Engineering systems vs Engineeringagents•Recall that at the end of Thursday’s class, we weretalking about ant algorithms.•By specifying a simple set of rules, we can achieveinteresting large-scale behavior.•Ant-type approaches lead us to think about how wecan build systems that produce the effects we want.•“Given that agents will act in a particular way, howcan we constrain the environment to achieve adesirable outcome?”•This method of problem solving is best applied toproblems involving self-interested agents.Department of Computer Science — University of San Francisco – p. 2/??Preferences and Utility•Agents will typically have preferences over outcomes•This is declarative knowledge about the relativevalue of different states of the world.•“I prefer ice cream to spinach”•Often, the value of an outcome can be quantified(perhaps in monetary terms.)•This allows the agent to compare the utility (orexpected utility) of different actions.•A rational agent is one that maximizes expected utility.•Self-interested agents each have their own utilityfunction.Department of Computer Science — University of San FranciscoRationality and protocol design•By treating participants as rational agents, we canexploit techniques from game theory and economics.•Assume everyone will act to maximize their ownpayoff•How do we structure the rules of the game so thatthis behavior leads to a desired outcome?•This approach is called mechanism design.Department of Computer Science — University of San Francisco – p. 4/??Example: Clarke tax•Assume that we want to find the shortest paththrough a graph.•Each edge is associated with an agent.•Each edge has a privately known transmission cost.•Agents might choose to lie about theirtransmission cost.•How can we find the shortest path?Department of Computer Science — University of San Francisco – p. 5/??Clarke•Rule:•Accept each agent’s bid.•If they are not on the shortest path, they get 0.•If they are on the shortest path, they get:•Cost of next shortest path - (cost of shortest pathwithout their contribution).Department of Computer Science — University of San FranciscoExamplestartfinish5(f)3(g)4(d)4(e)7(h)2(a)2(b)2(c)•Assume each agent bids truthfully.•Agents A, B, and C are each paid 8 - (6 - 2) = 4•This is their contribution to the ’best solution’•Other agents are paid nothing.Department of Computer Science — University of San Francisco – p. 7/??Example•Why is truth-telling a dominant strategy?•What if a underbids?•A bids 1: paid 8 - (5 - 1) = 4. No benefit.•What if A overbids?•A bids 3: paid 8 - (7 - 3) = 4. No benefit.•A bids 5. No longer on the shortest path, so Agets 0.•What if d underbids?•D bids 3: no change.•D bids 1: paid 6 - (5 - 1) = 2. But his cost is 4.•D overbids: no change.Department of Computer Science — University of San Francisco – p. 8/??Solution concepts•So how do we evaluate an algorithm or protocolinvolving self-interested agents?•Some solutions may be better for some agents andworse for others.•Example: cake-cutting problem•We know that each agent will try to maximize its ownwelfare•What about the system as a whole?Department of Computer Science — University of San FranciscoSolution concepts•There are a number of potential solution concepts wecan use:•Social welfare - sum of all agent utility.•Pareto efficiency•Is there a solution that makes one agent betteroff without making anyone worse off?•Individual rationality•An agent who participates in the solution shouldbe better off than if it hadn’t participated.•Stability•The mechanism should not be able to bemanipulated by one or more agents.•It’s not usually possible to optimize all of these at thesame time.Department of Computer Science — University of San Francisco – p. 10/??Stability•Ideally, we can design mechanisms with dominantstrategies•A dominant strategy is the best thing to do nomatter what any other agent does.•In the previous example, truth-telling was adominant strategy.•We would say that the mechanism isnon-manipulable. (lying can’t break it.)•Unfortunately, many problems don’t have a dominantstrategy.•Instead, the best thing for agent 1 to do depends onwhat agents 2,3,4,... do.Department of Computer Science — University of San Francisco – p. 11/??Nash equilibrium•This leads to the concept of a Nash equilibrium•A set of actions is a Nash equilibrium if, for everyagent, given that the other agents are playing thoseactions, it has no incentive to change.•Example: big monkey and little monkey•Monkeys usually eat ground-level fruit•Occasionally they climb a tree to get a coconut (1per tree)•A Coconut yields 10 Calories•Big Monkey expends 2 Calories climbing thetree.(net 8 calories)•Little Monkey expends 0 Calories climbing the tree.(net 10 calories)Department of Computer Science — University of San FranciscoNash equilibrium•If BM climbs the tree•BM gets 6 C, LM gets 4 C•LM eats some before BM gets down•If LM climbs the tree•BM gets 9 C, LM gets 1 C•BM eats almost all before LM gets down•If both climb the tree•BM gets 7 C, LM gets 3 C•BM hogs coconut•How should the monkeys each act so as to maximizetheir own calorie gain?Department of Computer Science — University of San Francisco – p. 13/??Nash equilibrium•Assume BM decides first•Two choices: wait or climb•LM has four choices:•Always wait, always climb,
View Full Document
Unlocking...