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.  Next we looked at markets.  Markets are known for price equilibrium. 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. That is why all design problems become mechanism design problems.
A mechanism design problem is one which has N agents. These agents must make a collective choice from some set X of possible alternatives. However each agent before making a choice privately observes his preferences over the alternatives in X also referred to as his type.
Each agent is expected to be a utility maximizer
#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 lesser 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

codingexercise
Check if a given array can represent Postorder Traversal of Binary Search Tree
bool IsPostOrder(List<int> post, int i, int j)
{
if (i >= j) return true;
var lesser =  post.GetRange(0, j-1, j-i).ReversedFirst(x => x < post[i]);
if (lesser == null)
    return IsPostOrder(post, i+1, j);
var k = post.IndexOfReverse(j, lesser);
for (int l = k+1; l <j; l++)
     if (post[l] < post[j])
        return false;
return IsPostOrder(post, i, k) && IsPostOrder(post, k+1, j-1);
}

The only thing to change in the code above is the occurrence of root as the last element instead of the first element The same code above can be simplified with the use of a stack similar to the method IsPreOrder