- 3 6 7 Vi 04 7 2 7 3 5 9 9 8 6 6 5 5 3 4 6 02 1 9 8 8 4 6 4 5 8 4 8 4 03 16 2 A 4 3 4 Figure 1 An Atomic Network Con 1 (67.47 KiB) Viewed 22 times
3,6,7 Vi 04 7, 2,7 3,5,9 9,8,6 6,5,5 3,4,6 02 1,9,8 8,4,6 4,5,8 4,8,4 03 16 2. (a) 4,3,4 Figure 1: An atomic network congestion game 7 Consider the atomic network congestion game, with three players, described by the directed graph in Figure 1. In this game, every player i (for i =1,2,3) needs to choose a directed path from the source s to the target t. Thus, every player i's set of possible actions (i.e., its set of pure strategies) is the set of all possible directed paths from sto t. Each edge e is labeled with a sequence of three numbers (C1, Q, C3). Given a profile = (1,2,3) of pure strategies (i.e., s-t-paths) for all three players, the cost to player i of each directed edge, e, that is contained in player i's path i, is ck, where k is the total number of players that have chosen edge e in their path. The total cost to player i, in the given profile , is the sum of the costs of all the edges in its path from s to t. Each player wants to minimize its own total cost. Compute a pure strategy Nash Equilibrium in this atomic network conges- tion game. Compute the total cost to each player in that Nash Equilibrium. [7 marks] (b) Consider the following linear programming problem, given as a "feasible dic- tionary”, with "basis" {1,22}: Maximize: Subject to: 3+213 +5r4 11 12 = 4 - 4r3 - 5x4 = 8-6r3 - 364 11 >0, 120, 130, 140 [2 marks] i. What is the "basic feasible solution" (BFS) corresponding to the basis {11, 12} of this feasible dictionary? ii. Apply one "pivot" step (of the simplex algorithm) to this feasible dic- tionary, in order to move the variable rs into the basis and move the variabler out of the basis.
[8 marks) [2 marks] Show the resulting dictionary after this pivot step, including the result- ing new objective function. iii. Is the new dictionary obtained via this pivot step a feasible dictionary? Explain your answer. () Consider the following optimization problem. Suppose that you are given an (m x n) integer matrix, A, and an integer m-vector, b, and you wish to find a real-valued n-vector r, such that Ar = b (if one exists), such that the objective Diari| is minimized. Here |:| denotes the absolute value of ti. Show how to re-phrase this as a linear programming problem, and explain briefly why your formulation as a linear program is correct. [6 marks]