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)
}