Detailed Solution: CE322 Algorithmic Game Theory Assignment 2018/19

This document presents a comprehensive solution to an algorithmic game theory assignment, addressing four key questions. The solution begins with finding correlated equilibrium using Linear Programming in MATLAB, explicitly mentioning the equilibrium conditions satisfied. It then explores a zero-sum game, reducing it by removing dominated strategies, determining if a pure Nash equilibrium exists, and computing a mixed equilibrium using indifference conditions. Finally, the solution focuses on computing an instance that admits a Nash equilibrium with as high a Price of Anarchy as possible, using MATLAB to specify click-through rates, player values, and equilibrium strategies, providing social welfare analysis. The assignment is designed to test the students understanding of game theory concepts and their ability to apply them using computational tools like MATLAB.

Question 2 [25%] Consider the following normal form game G:
A B C
X 10,5 0,6 0,0
Y 7,7 0,0 6,0
Z 0,0 7,7
Your task is to find the correlated equilibrium that maximizes the sum of players utilities,
using Linear Programming in MATLAB. Explicitly mention the equilibrium conditions that
are satisfied.
Find the correlated equilibrium that maximizes the sum of players utilities, using Linear
Programming:
Answer:
Consider the game G:
A B C
X 10,5 0,6 0,0
Y 7,7 0,0 6,0
Z 0,0 7,7 5,10
Let us split the table into two matrix
M1: M2:
A B C
X 10 0 0
Y 7 0 6
Z 0 7 5
In the above matrix M1 & M2,
Find the minimum value row wise and maximum
value column wise.
The row wise minimum value is 0 and column wise maximum value is 6 for matrix M1.
The row wise minimum value is 0 and column wise maximum value is 7 for matrix M2.
A B C
X 5 6 0
Y 7 0 0
Z 0 7 10

A B C Row
Min
value
X 10 0 0 0
Y 7 0 6 0
Z 0 7 5 0
Col
max
valu
e
10 7 6
Find the minimum(max value) of M1 and M2,
which is given as [6 7]
In the above two matrices row wise minimum value is not equal to column wise maximum
value.
Hence find the total of row wise of M1.
A B C
X 10 0 0
Y 7 0 6
Z 0 7 5
Total 17 7 11
The maximum total value is 17. Hence the corresponding row and column is deleted.
Thus we have, M1 as
B C
X 0 0
Y 0 6
Solve the above matrix using linear equations.
The solutions are 0 and 0.1717
A B C Row
Min
value
X 5 6 0 0
Y 7 0 0 0
Z 0 7 10 0
Col
max
valu
e
7 7 10

Matlab code:
clear all;
close all;
f=[6 7];
disp(f);
M1=[0 0 ; 0 6];
M2=[0 6];
M1eq=[];
M2eq=[];
lb=[3 1];
ub=[];
[X,Z]=linprog(f,M1,M2,M1eq,M2eq,lb,ub);
disp(X);
disp(Z);
Output:

The point at which the constraints satisfy depends upon the pure strategy. So the values
chosen according to the example for lower bound are [3 1].
Hence the output obtained is Z = 25 and X = 1
Question 4
Your task is to compute an instance I = (ctr, v) that admits a Nash equilibrium (on pure
strategies) b, with as high Price of Anarchy as possible, using MATLAB. You need to specify
the click-through rates, the players’ values, and the equilibrium strategies that you computed.
You can assume that 0 ≤ ctrj ≤ 1 for all slots j, and 0 ≤ vi ≤ 1 for all advertisers i (you can
choose the level of precision by selecting the appropriate number of decimal digits you
allow). Either prove in paper that the strategies that you provide indeed satisfy the
equilibrium conditions, or make it clear where in your code you guarantee that they do.
Explicitly mention the social welfare of the your equilibrium, the best possible social welfare
of your instance, and the Price of Anarchy bound that they imply
Nash Equillibrium (in Pure Starategy)
Consider
Player2
Player1
q 1-q
p 3,3 0,2
1-p 2,0 1,1
Player1 plays strategy1 with probability p and strategy2 with probability (1-p)
Player2 plays strategy1 with probability q and strategy2 with probability (1-q)
To check for pure strategy
Consider Player1
3 q+ 0 (1−q )=2 q+1 ( 1−q )
3 q=2 q+1−q
3 q=q+ 1
2 q=1
q=1/2
Consider Player2
3 p+0 ( 1− p ) =2 p+1 ( 1− p )

3 p=2 p+1− p
2 p= p+1
p=1 /2
Therefore p=q=1/2
Hence there are two pure strategies.
clc;
clear workspace
a=[-2 0 0 5 3; 3 2 1 2 2; -4 -3 0 -2 6; 5 3 -4 2 6];
maxi=max(a);
disp('a=');
disp(a);
maximin=min(maxi);
disp('maxi=');
disp(maxi);
b=transpose(a);
mini=min(b);
disp('b=');
disp(b);
minimax=max(mini);
disp('Mini=');
disp(mini);
if(minimax==maximin)
row=find(mini==minimax);
col=find(maxi==maximin);
disp('row:');
disp(row);
disp('col=');
disp(col);
disp('minima=');
disp(minimax);
end

Output:
Social welfare of the your equilibrium, the best possible social welfare of your instance, and
the Price of Anarchy bound that they imply
Consider an instance below:
Player2
Player1
Q 1-q
P 3,3 0,2
1-p 2,0 1,1
In the above example two players plays with equal strategies of (3,3). That is, equilibrium
condition of both players are (3,3).

Therefore out of 3 choices one of the choice of two players is (3,3) and (1,1) which are called
as equilibrium condition of player1 and player2.
The other strategies of player1 are, i,e 3, 0 , 2 and 1
That is, Out of three possibility,player1 wins all three probability, out of three choices
player1 either lose the game (0), only two times wins out of 3 probability condition, and win
only once out of three possibility.
Similarly Player2 plays with strategies as 3, 2, 0 and 1
That is out of 3, player2 wins all the three possibility (3), only two times wins the game (2),
lose the game and only once win the game out of three possibilities.
The Price of Anarchy bound that they imply
For the above instance, there are two strategies which are classified as pure strategy and
mixed strategy of two players.
The price of anarchy that bound the game is mixed strategy which are given as (0,2) and (2,0)
and pure strategy (3,3) and (1,1).
The efficiency of the game is either one of the player wins the game or at least wins once out
of three possibilities. But not loses the game. The efficiency of the players implies the price
of anarchy.