We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. We viewed the latter in terms of flow network.We consider a graph of n nodes, an n x n symmetric traffic matrix with the cell values for (i,j) being the total requirements between customers of i and customers of j and a capacity ci. A subgraph of this multi commodity flow network with nodes S, corresponding capacities and v(S) as the maximum total flow in this network are in the core of a coalition game v if their corresponding payoffs for the nodes found by summing over all the subtraffic for all the customers of that node from the new traffic matrix is less than that of the original matrix. The payoff increases with the flow to and from the customers of that node. The core is a form of fairness in the splitting of the initial payoffs among n nodes because no coalition has an incentive to secede because it cannot make more by itself. If we determine such a core and a newer flow matrix, then we have defined an Internet equilibria.
The coalitions are not formed by a central governor.  It is decided locally. But if there were a central authority that allocates bandwidths to individual flows in order to maximize global optimum, how much better would it be ? This is also referred to as the price of anarchy. This can also be considered as the ratio between the worst case Nash equilibrium and the optimum sum of payoffs  The price of anarchy is the price of uncoordinated individual utility maximizing decisions. In the context of multi-commodity flow network in which the message delays increase with edge congestion while flow choose paths so as to minimize delay, the price of anarchy is two which means it is no worse than the optimum solution with double the bandwidth.
#codingexercise
Check if a given array can represent Preorder Traversal of Binary Search Tree
bool IsPreOrder(List<int> pre)
{
var stk = new Stack<int>();
int root = INT_MIN;
for (int i = 0; i < pre.Count; i++)
{
   if (pre[i] < root)
       return false;
   while (!stk.empty() && s.top() < pre[i])
   {
      root = stk.top();
      stk.pop();
    }
   stk.push(pre[i]);
}
return true;
}
or possibly more legible as
bool IsPreOrder(List<int> pre, int i, int j)
{
if (i >= j) return true;
var greater =  pre.GetRange(i+1, j-i).first(x => x > pre[i]);
if (greater == null)
    return IsPreOrder(pre, i+1, j);
var k = pre.IndexOf(i, greater);
for (int l = k+1; l <= j; l++)
     if (pre[l] < pre[i])
        return false;
return IsPreOrder(pre, i+1, k-1) && IsPreOrder(pre, k+1, j)
}

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium and then we discussed Internet Equilibria. Nash equilibrium translates to solving linear programming. Unlike Nash Equilibrium, Internet Equilibria  is not achieved by rational contemplation. This game is inherently coalitional. One of the theories suggests to draw the payoffs in such a way that no coalition has an incentive to secede because it cannot make more by itself than what is allocated in the coalition. This splitting of the total payoff forms a "core" but because it is conservative in definition, a game may have an empty core. The Internet equilibria can be described as a flow network with n nodes and a n x n flow matrix where each cell is the total traffic requirements between customers of i and customers of j. The Internet equilibria then translates to a problem of finding an optimum solution in a multicommodity flow problem for the overall network, achieving a flow matrix F' <= F, such that the corresponding payoffs for the nodes xi in terms of the flow matrix cell values summed over all j, are in the core of the coalition game v.
#codingexercise
Yesterday we were discussing spiral matrix traversal. The same algorithm works for anticlockwise direction as well:
#codingexercise
There is a square matrix of order n which is filled from 1 to n^2 in row major. Find the Kth element in spiral traversal of the matrix in anticlockwise direction
Example: Given n=3 and K=5.
Matrix:
1 2 3
4 5 6
7 8 9
Output: 9
By spiral order traversal  we are covering
k  <= n elements in the first column
k <= n+m-1 elements in the last row
k <= n+m-1+n-1 elements in the last column
k <= n+m-1+n-1+m-2 elements in the first row
else element lies in the inner matrix of dimensions m-2 rows and n-2 columns

int GetKthAntiClockWise(int[,] A, int m, int n, int k)
{
if (n <1 || m < 1) return -1;
if (k <= n)
    return A[k-1, 0]; 
if (k <= n+m-1)
   return A[n-1, k-n]; 
if (k <= n+m-1+n-1)
   return A[(n-1-(k-(n+m-1))), m-1];
if (k <= n+m-1+n-1+m-2)
   return A[0, m-1-(k-(n+m-1+n-1))]; 
return GetKthAntiClockWise(A.SubArray(1,1,m-2,n-2), m-2, n-2, k-(2*n+2*m-4)));
}

We continue discussing the paper by Papadimitriou  - Algorithms, Games and Internet. We started with Nash equilibrium  which essentially says that we cannot predict if we consider the decisions by the participants in isolation and instead that decision making must be studied by taking into account the decision-makings of others.  The decision making is expressed in terms of a probability distribution over possible actions by each player. As long as the set of strategies form a convex set, there is a Nash equilibrium and finding Nash equilibrium translates to solving linear programming.
The next game we are going to look into is the Internet Equilibria.  Internet bandwidth is scarce and its allocation to individual end to end flows is achieved via the TCP/IP congestion control protocol. The congestion is handled this way : If the previous batch of packets got through, then increase the batch size by one. If not, decrease it by half. This has been working very well due to its simplicity but it is not clear of which game the Internet TCP/IP congestion control is a Nash equilibrium. There are a few ways in which this equilibria differs from the previous game. First, the equilibrium is not achieved by rational contemplation. It is achieved by interaction and adaptation in an environment where conditions and player populations change rapidly. Third, changes to strategies incur costs. Fourth, players cannot compensate each other by exclusive negotiations. There have been several theories advanced in this regard. The conditional game theory considers a game of n players as a set of possible 2^n-1 coalitions each of which can achieve a particular value which is the best possible sum of payoffs among players among the coalitions, against worst case behavior of players in the rest. However the game needs to be initialized with a certain value for the total payoff among the n players and this is difficult to do in the Internet Equilibria.  Another technique called the "core" was proposed to study these games. A vector in the real space is considered part of the core if the summation of payoffs over each coalition is greater than a particular value for all such coalitions. It draws the payoffs in such a way that no coalition has an incentive to secede because it cannot make more by itself than what is allocated in the coalition. This splitting of the total payoff is intuitive to the notion of equilibria but also very conservative due to which many games may have empty cores. Although the payoffs may not always be split in such a manner, this game is inherently coalitional is undisputed because the game can be seen as a flow network and flow happens due to coalitions.

#codingexercise
There is a square matrix of order n which is filled from 1 to n^2 in row major. Find the Kth element in spiral traversal of the matrix.
Example: Given n=3 and K=5.
Matrix:
1 2 3
4 5 6
7 8 9
Output: 9
By spiral order traversal  we are covering
k  <= m elements in the first row
k <= m+n-1 elements in the last column
k <= m+n-1+m-1 elements in the last row
k <= m+n-1+m-1+n-2 elements in the first column
else element lies in the inner matrix of dimensions m-2 rows and n-2 columns

int GetKth(int[,] A, int m, int n, int k)
{
if (n <1 || m < 1) return -1;
if (k <= m)
    return A[0, k-1];
if (k <= m+n-1)
   return A[k-m, m-1];
if (k <= m+n-1+m-1)
   return A[n-1, (m-1-(k-(m+n-1)))];
if (k <= m+n-1+m-1+n-2)
   return A[n-1-(k-(m+n-1+m-1)), 0];
return GetKth(A.SubArray(1,1,m-2,n-2), m-2, n-2, k-(2*n+2*m-4)));
}

Yesterday we were discussing the paper by Papadimitriou  - Algorithms, Games and Internet. and we started with Nash equilibrium  which essentially says that we cannot predict if we consider the decisions by the participants in isolation and instead that decision making must be studied by taking into account the decision-makings of others.  The decision making is expressed in terms of a probability distribution over possible actions by each player. A classic example of a game showing Nash equilibrium is prisoner's dilemma. This game is meant to show that two completely rational individuals might not cooperate, even if it appears that it is in their best interest to do so. The equilibrium is a state from where payoffs could be only worse by changing strategies. In the case of prisoner's dilemma, the mutual defection was a state of equilibrium.
It is said that there exists a Nash equilibrium when the set of strategies form a convex set. A convex set is one where we have a distribution of strategies such that their weights or probabilities are all positive and add up to one. In geometry a convex set is as a linear combination of points in real vector space where all the coefficients are non-negative and sum to 1. As an example, a convex combination of two points lies on the line segments between the points. This is exactly what we solve with linear programming. Consequently finding Nash equilibrium translates to solving linear programming. We have seen earlier how a simplex algorithm can be used to solve linear programming. The complexity of the Nash algorithm can therefore be considered similar to solving the linear equations.

#codingexercise
Yesterday we were discussing comparing top left corners of rectangles
A simple compareTo operation can be as follows:
    public int CompareTo(Object obj) {
        if (obj == null) return 1;
        var other = obj as Tuple<int,int>;
        if (other != null)
        {
             if (other.first < this.first && other.second < this.second) return -1;
             if (other.first == this.first && other.second == this.second) return 0;
             return 1;

        }
        else
           throw new ArgumentException("Object is not a Tuple<int,int>");
    }

Today we will start discussing the paper by Papadimitriou  - Algorithms, Games and Internet.
In a game, each of the n players can choose among a set of strategies S, i = 1, .. n and there are functions ui, i = 1 .. n: S1 x S2 ... Sn. These functions result in a payoff for each player for each such combined choice. The fundamental question of Game Theory is what constitutes rational behavior in such a situation ? One such explanation is the Nash equilibrium. A combination of strategies xi belongs to S1, xn belongs to Sn, for which ui (x1, ... xi, ... xn) >= ui (x1, ...xi-dash, ...xn) for all i and xi-dash belong to Si: a behaviour that is from which no player has an incentive to deviate. The Nash equilibrium is attained when each player has chosen a strategy and no player benefits from changing his or her strategy. The set of strategy choices and their corresponding payoffs remain unchanged.
Nash equilibrium has a wide variety of applications because it allows us to formalize what happens if several people or several institutions  are making decisions at the same time, and if the outcome depends on the decisions of the others.  Nash's equilibrium essentially says that we cannot predict if we consider the decisions by the participants in isolation and instead that decision making must be studied by taking into account the decision-makings of others.  The decision making is expressed in terms of a probability distribution over possible actions by each player.  The modern version of Nash equilibrium discussion takes into account this mixed strategy which is shown to exist for any zero sum game involving finite set of actions. Nash's equilibrium is considered to be much more broader than pure strategy method because it makes no judgement about the optimality of the equilibrium being generated. This optimality in terms of payoffs or profit is generally restricting in the definition of the equilibrium.  Furthermore it has applications in non-cooperative games or hostile games. A classic example of such a game is prisoner's dilemma.  This game is meant to show that two completely rational individuals might not cooperate, even if it appears that it is in their best interest to do so.  This example is described so. Two members of a criminal gang are arrested and imprisoned Each prisoner is in a solitary confinement with no means of communicating with one another.  The prosecutors lack sufficient evidence to lock each up so they offer a bargain to each prisoner -betray the other by testifying or cooperate with the other by remaining silent. If A and B both betray each other, each of them serves two years in prison. If A betrays B but B remains silent, A will be set free and B will serve three years in prison and vice versa.  If A and B both remain silent, both of them will serve only one year in prison because there is not enough evidence. If each prisoner pursues the individual reward logically, they will both betray each other with less than optimum outcome. Instead if they show a cooperative behaviour and remain silent, they get a better outcome. Remaining silent is not the only option. The players could also choose to defect. In fact, mutual defection is considered the only strong Nash equilibrium in the game.From this equilibrium, the prisoners could only do worse by unilaterally changing strategy. The dilemma is that mutual cooperation yields a better outcome but it is not the rational outcome because from a self interest perspective, the choice to cooperate at the individual level is irrational.
#codingexercise
Find the maximum number of submatrix contained within a bounding rectangle (represented by a list of tuples where the first item in the list is the top left corner and the last is the bottom right)
int GetCount(List<tuple<int,int>> corners, List<List<Tuple<int,int>>> submatrices)
{
return submatrices.Count( x => corners.first() <= x.first() && corners.last()>= x.last());
}
we can have an extension method on the tuple that compares it to another

Today we continue discussing the problem of finding largest sub matrix of 1 in a boolean matrix using graph based method. we were saying that the depth first search  allows us to explore islands of ones one after the other. we used the islands to find the submatrix. We said we could stretch the submatrix rectangle within each island to cover most of the island. We showed a method to push the extremes in terms of minimum row and column and maximum row and column to determine the boundaries of the submatrix. We could find the top left corner for the submatrix but the same method also finds every other corner of the submatrix. Moreover, submatrix thus founds answers the question of finding the largest submatrix in the original matrix.
However, we are not limited to the largest such sub-matrix. The graph based depth first search allows us to explore the islands one after the other. Therefore we can rank the islands based on size. This helps us find the kth largest submatrix as well with the same ease as we did with the largest matrix. The smallest submatrix is usually of size one. where a single cell occurs as an island. This is also listed with the islands encountered and since we can sort them based on the size, we have the smallest submatrix appearing at the tail of the list.
This method finds the number of submatrices, their locations inside the matrix alongwith their sizes. Consequently we can tell which part of the matrix has the highest number of such submatrices included. None of the submatrices overlap otherwise they wouldn't be islands, consequently we can determine a bounding rectangle that contains more than a threshold number of submatrices we are interested in. This bounding rectangle gives the portion of the original matrix that is heavier in 1s and consequently determines how lop sided the matrix is. The fraction of the contained submatrices within a half of the original matrix to the total number of submatrices encountered gives us a quantitative number for how heavy or lop sided the original matrix is. Finding this bounding rectangle is a matter of arranging the submatrices by their top left corners and progressively increasing the bottom right of the bounding rectangle until a threshold number of rectangles are completely included within the bounding rectangle or half the original square is reached depending on the choice of our selection criteria. 

Today we continue discussing the problem of finding largest sub matrix of 1 in a boolean matrix using graph based method. we were saying that the depth first search  allows us to explore islands of ones one after the other. This way we could count the number of islands. Furthermore we could find the size of each island. we could now tell the largest island. It was however not clear how to find the submatrix contained within an island given that the island could be of irregular shape. In order to find the contained matrix, we merely have to find the corners. we know when we enter an island so we can initialize the minimum and maximum row and columns encountered. Candidates for corners are initialized by the min and max of row,column encountered in that island as the case maybe for that direction. for example, top left will require both row and column value to be minimum. Then the coordinates at these boundary values or adjacent to it such that the area of the sub matrix contained is maximized are used as corners. Therefore we pick the common values for coordinates as close to the corners as possible. for example the sub matrix will have a top row as the higher row value of top left and top right corners. this gives us the submatrix for each island. This method is equally applicable to the largest island as it is applicable to other islands.
#untested but just for explanation.
Tuple<int, int> GetTopLeft(int[,] A, int ROW  int COL, int sr, int sc)
{
assert(A[sr,  sc] == 1); // arbitrary starting point an island
int minr = sr;
int minc = sc;
int maxr = sr:
int maxc = sc;
bool change = True;
while(change)
{
change = False;
for(int k = minr-1; k >= 0 && A[k, minc] && A[k, maxc] ; k--) {minr--; change = True;}
for(int k = maxr+1; k  < ROW  && A[k, minc] && A[k, maxc] ; k++) {maxr++;change = True;}
for(int k = minc-1; k >= 0 && A[minr, k] && A[maxr,k] ; k--) {minc--;change = True;}
for(int k = maxc+1; k < COL  && A[minr, k]  && A[maxr,k]; k++) {maxc++;change = True;}
}
return new Tuple<int, int> (minr, minc);
}