Convex-Concave GamesProf. S. Boyd, EE392o, Stanford UniversityExample: Optimal Server Location on Networknetwork with 11 nodes replacements1234567891011Prof. S. Boyd, EE392o, Stanford University 1payoff matrix isP =0 1 1 1 2 1 2 3 2 3 21 0 1 2 3 2 3 2 1 2 21 1 0 1 2 2 3 3 2 2 11 2 1 0 1 2 3 2 3 3 22 3 2 1 0 3 4 1 2 3 31 2 2 2 3 0 1 4 3 4 32 3 3 3 4 1 0 5 4 5 43 2 3 2 1 4 5 0 1 2 32 1 2 3 2 3 4 1 0 1 23 2 2 3 3 4 5 2 1 0 12 2 1 2 3 3 4 3 2 1 0. (1)(P (i, j) is distance between nodes i and j)Prof. S. Boyd, EE392o, Stanford University 2• request deterministic, but unknown: place server at center of graph(nodes 1, 2, 3 or 4); then d elay no greater than 3• request has (known) distribution v0: solve LPminimize (P v0)Tusubject to 1Tu = 1.(2)for example, if v0is uniform: place server at node 1 or 3 (or anycombination); expected delay is 1.636• request has unknown probability distribution: server’s optimaldistribution found as solution to matrix gameProf. S. Boyd, EE392o, Stanford University 31234567891011(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0.5, 0)(0.5, 0)(0, 0.5)(0, 0.326)(0, 0.174)• pair (u⋆i, v⋆i) next to node i specifies probability of ser ver and requestoriginating at node i, where u⋆, v⋆solve the gameProf. S. Boyd, EE392o, Stanford University 4• solution need not be unique: another optimal server distribution is˜u⋆= (0.486, 0.077, 0, 0, 0, 0.104, 0.035, 0.298, 0, 0, 0). (3)Note: Not every solution tominimize (P v⋆)Tusubject to 1Tu = 1(4)solves the game: (bilinear) objective function is not strictly convex-concavein u and v.Prof. S. Boyd, EE392o, Stanford University 5An example of a convex-concave game• m Gaussian c om m un ications channels, signal powers pi≥ 0,noise (or interferenc e) powe r ni≥ 0• power budget: total signal power P , total noise power N• objective for signal power s is to m a ximize total capacity,for noise powers to minimize total capacity:maximizepminimizenPmi=1log(1 +βipiσi+ni)subject to 1Tp = P,1Tn = N,p  0, n  0.(5)objective is convex in n and concave in pProf. S. Boyd, EE392o, Stanford University 6Specific examplespecific instanc e with 10 channels, solved using barrier method• P = 20, N = 10• σ = (2, 6, 5, 8, 3, 9, 5, 6, 7, 3)• βi= 1, i = 1, . . . , moptimal allocation of signal powers isp⋆= (2.734, 2.333, 2.733, 0.334, 2.733, 0.000, 2.733, 2.333, 1.333, 2.733),wor st possible noise distribution isn⋆= (3.6, 0, 0.6, 0, 2.6, 0, 0.6, 0, 0, 2.6).Prof. S. Boyd, EE392o, Stanford University 7value of the game, C⋆= 2.860figure shows that p⋆is wate r filling solution to e ffective noise distribution(σ + n⋆)/β:1 2 3 4 5 6 7 8 9 10012345678910ChannelPowerSignal powerEffective noise powerProf. S. Boyd, EE392o, Stanford University