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 multi commodity flow network where the maximum total flow in a subgraph is in the core of a coalition game. we saw the definition of core to hint at optimal set. Next we looked at markets.  Markets are known for price equilibrium. and then we discussed mechanism design problems.

A mechanism is said to implement a social choice function if there is an equilibrium of the game induced by the mechanism that yields the same outcomes as the social choice function for each possible profile of types.  A social welfare mechanism implements a social choice function.  A direct revelation mechanism is a mechanism in which the strategies are truthful as per the type and all the functions are utility functions and the outcome  is directly the social choice function.  Enumerating all the social choice functions that are implementable is not easy. The revelation principle also tells us that  we can further restrict our attention to direct revelation mechanisms in which truth telling is an optimal strategy for each agent. A social choice function is truthfully implementable if the direct revelation mechanism has an equilibrium if the strategies are the types and the truth telling by each agent constitutes an equilibrium. As an example, a first price sealed bid auction is a truthful implementation of the social choice function

We can apply game theories to networking as well. In particular, we can view it as a coalition game with the total flow as the outcome. When we add an IP header over the original IP header payload and secure the communications between networks with IP tunneling, we are establishing a coalition and a different network.
           tunnel = IP (header) + IP (payload)
That is why we can overlay this game over any networking even if its for the cloud as mentioned here : https://1drv.ms/w/s!Ashlm-Nw-wnWqXUqaKP1HX09wuwo 


#codingexercise

Print the bottom view of a binary tree
void PrintBottomView(Node root)
{
if (root == null) return;
int hd = 0;
var d =  new SortedDictionary<int, int>();
var q = new Queue<Node>();
root.hd = 0;
q.enqueue(root);
while (q.empty() == false)
{
var first = q.front();
q.dequeue();
hd = first.hd;
d[hd] = root.data;
if (first.left != null)
{
first.left.hd = hd - 1;
q.enqueue(first.left);
}
if (first.right != null)
{
first.right.hd = hd + 1;
q.enqueue(first.right);
}
}
foreach (var kvp in d)
  Console.Write("{0} ", kvp.value);
}

Find the number of rectangles contained in a matrix of size m x n.
int GetCountRectangles(int m, int n)
{
int count = 0;
for( int i = 0; i < m; i++)
   for( int j = 0; j < n; j++)
{
     count += getWithTopLeft(i,j, 0, 0, m-1, n-1);
}
return count;
}
rectangles that start with top left as i,j span columns incrementally or span rows incrementally or both.
for( int i = 0; i < m; i++)

   for( int j = 0; j < n; j++)
{
var bottomright = new Tuple<int, int>(i,j);
}