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. 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, then it may be better than the coalition game. This is referred to as the price of anarchy. Next we looked at markets.  Markets are known for price equilibrium. Once an optimum is reached and there is no further reallocation possible to improve, we have a Pareto set of the market. we can improve the efficiency and standardize the transactions with price and currency. All we need is a price per unit of each good. Arrow-Debreu 1953 theorem suggests that there is always a price vector p called the price equilibrium by which the endowments are indeed the best vector of goods.If game theory strives to understand rational behavior in competitive situations, then there is such a thing as inverse game theory. Given desired goals, we can design a game such that players motivated solely by self-interest end up achieving desired goals. In the context of the internet, if an artifact such as a new congestion control protocol, a new caching scheme, a new routing algorithm etc. has a better performance, it does not necessarily mean it will be successful unless there is a path from its introduction to prevalence where it is adopted, implemented and tolerated. That is why all design problems become mechanism design problems.
#codingexercise
Given a tree and a sum, return true if there is a path from the root down to a leaf, such that adding up all the values along the path is greater than the given sum.
bool hasPathSum(Node root, int sum)
{
  if (root == NULL)
  {
     return (sum == 0);
  }else
  {
    int newsum = sum - root.data; 
    if (newsum > sum) throw Exception("underflow")
    if ( newsum < 0 && root.left == null && root.right == null)
      return true;
    if(root.left && hasPathSum(root.left, newsum))
       return true;
    if(root.right && hasPathSum(root.right, newsum))
       return true;
    return false;
  }
}
the check for underflow need not throw an exception but just return value