 users want to push a certain amount of flow. Then, a flow is at Nash equilibrium (or is a Nash flow) if no agent can improve its latency by changing its path Theorem ( Beckmann et al., 1956): If edge latency functions are continuous and non-decreasing, and users control an infinitesimal amount of flow, then the Nash flow exists and is unique.
31
Flows and Price of Anarchy Theorem 1: In a network with linear latency functions, the cost of a Nash flow is at most 4/3 times that of the minimum-latency flow. Theorem 2: In a network with general latency functions, the cost of a Nash flow is at most n/2 times that of the minimum-latency flow. (Roughgarden & Tardos, JACM02)
32
A bad example for non-linear latencies Assume i>>1 st xixi 1 0 1 1 - A Nash flow (of cost 1) is arbitrarily more expensive than the optimal flow (of cost close to 0)
33
Convergence towards a NE (in pure strategies games) Ok, we know that selfish routing is not so bad at its NE, but are we really sure this point of equilibrium will be eventually reached? Convergence Time: number of moves made by the players to reach a NE from an initial arbitrary state Question: Is the convergence time (polynomially) bounded in the number of players?
34
The potential function method Roughly speaking, a potential function for a game is a real-valued function, defined on the set of possible outcomes of the game, such that the equilibria of the game are precisely the local optima of the potential function Potential games: broad class of games admitting a potential function Theorem: In any finite potential game, best response dynamics always converge to a NE of pure strategies.
35
Potential function and congestion games How many steps are needed to reach a NE? It depends on the combinatorial structure of the players' strategy space Definition (Matroid Congestion Games): A congestion game G is called MCG if: The strategy space of every player is the basis of a matroid over the set of congested resources (recall that the size of this strategy space corresponds to the rank of the player's matroid); The rank of the game, r( G ), is defined to be the maximum matroid rank over all players.
36
Convergence in congestion games Theorem (Achermann et al., FOCS'06): In a MCG G with n players and m resources, all best response improvement sequences have length O(n 2 m r( G )). Example of a MCG: Load balancing Instead, in general, a network congestion game is not a MCG Moreover, it is possible to show that there exist instances for which the convergence time is exponential (unless finding a local optimum in any Polynomial Local Search (PLS class) problem can be done in polynomial time, against the common belief) Still, Internet works quite fine!
38
SECOND PART: Algorithmic Mechanism Design (or, the art of convincing a capitalist to behave like a socialist )
39
Mechanism Design: the goal 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? Implementation of the goals depends on the individual behavior of the agents
40
Mechanism Design: a picture Agent 1 Agent n Mechanism p1p1 pnpn tntn t 1t 1 r 1r 1 r nr n Private types Reported types Payments Output Each agent reports strategically to maximize its well-being… …in response to a payment which is a function of the output!
41
Overview of the results Algorithms Mechanisms Centralized Decentralized (Non- cooperative) Network design problems
42
Mechanism Design Games induced by mechanisms are different from games in standard form: Players hold independent private values The payoff matrix is a function of these types each player doesnt really know about the other players payoffs, but only about its one! Games of Incomplete information Dominant Strategy Equilibrium is used
43
Mechanism Design Problem: Type of an Agent N agents, and each agent has some private information called the type, t i T i, and performs a strategic action We restrict ourself to direct revelation mechanisms, in which the action is reporting a type r i T i (with possibly r i t i ) Example: Auction Game Each agent knows its cost for doing a job, but not the others one; the type of the agent is its cost T i = [0, + ]: The agents cost may be any positive amount of money t i = 80: Minimum amount of money the agent i is willing to be paid r i = 85: Exact amount of money the agent i bids to the system for doing the job (not known to other agents)
44
Mechanism Design Problem: Output Specification F is the set of feasible outputs Output Specification: For a given reported-type configuration r=(r 1, r 2, …, r N ), it specifies a valid outcome x(r) F which should optimize an objective function f(t) (the so-called social choice function) Example: Auction Game F : Different winners of the auction f(t): min i (t 1, t 2, …, t N ) (the lowest true cost) x(r): allocate to the bidder with lowest reported cost
45
Mechanism Design Problem: Valuation and Utility If x is the outcome, then the valuation that agent i makes of x is given by a real valued function: v i (t i,x) Auction Game: If agent i wins the auction then its valuation is equal to its actual cost for doing the job, otherwise it is 0 If p i is the payment given to the agent, then the utility of the outcome x is: u i (t i,x) = p i - v i (t i,x) Auction Game: If agents cost for the job is 90, and it gets the contract for 100 (i.e., it is paid 100), then its utility is 10
46
The Mechanism A mechanism is a pair M= specifying: An algorithm g(r) which computes the outcome x as a function of the reported types r A payment scheme p as a function of the output x
47
Strategy-Proof Mechanisms If truth telling is the dominant strategy in a mechanism then it is called Strategy-Proof Agents report their true types instead of strategically manipulating it Utilitarian Problems: A problem is utilitarian if its objective function is such that f(t) = i v i (t i,x) The Auction game is utilitarian
48
Vickrey-Clarke-Groves (VCG) Mechanisms A VCG-mechanism is (the only) strategy-proof mechanism for utilitarian problems: Algorithm: g(r)= arg max x F i v i (r i,x) Payment function: p i (x)= h i (r -i ) - ji v j (r j,x) where h i (r -i ) is an arbitrary function of the types of other players What about non-utilitarian problems? We will see…
49
VCG-Mechanisms are Strategy-Proof Proof (Intuitive sketch): Payment given to agent i p i (x)= h i (r - i )- ji v j (r j,x) and both the terms above are independent of the type, strategy and valuation of agent i So it is best for agent i to report its true value. Strategic behavior does not lead to a beneficial outcome.
50
Clarke Mechanisms This is a special VCG-mechanism (known as Clarke mechanism) in which h i (r - i )= ji v j (r j,x(r - i )) p i = ji v j (r j,x(r - i )) - ji v j (r j,x) In Clarke mechanisms, agents utility are always non-negative
51
Clarke mechanism for the Vickrey auction The winner is paid p i = ji v j (r j,x(r - i )) - ji v j (r j,x) = = ji v j (r j,x(r - i )) second lowest offer Let us convince ourself it is strategy-proof by case analysis. For a player i, let T=min ji {r j }: t i t i, he may still win (again being paid T), but he may also lose (if r i >T), by getting a null utility; t i >T: then, if r i >t i, he keeps on not to win, while if r i
52
VCG (Clarke)-Mechanisms: Pros and Cons The goal, i.e., the optimization of the social-choice function, is achieved with certainty The payments may be sub-optimal
53
VCG-mechanisms: algorithmic issues System has to calculate N+1 functions: once with all agents (for g(r)) and once for every agent (for the associated payments) What is the time complexity of the mechanism? What happens if the problem is non- utilitarian? What happens if computing the optimal solution is NP-hard?
54
VCG-mechanisms and graph problems Following the Internet model, we assume that each agent owns a single edge of a graph G=(V,E), and establishes the cost for using it The agents type is the true weight of the edge Classic optimization problems on G become mechanism design optimization problems! Many basic network design problems have been faced: minimum spanning tree, shortest paths,