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 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 which means he or she is guided by his or her own interest. Hence this is considered a game of incomplete information.A mechanism is a collection of a finite number of strategy sets and an outcome function based on the strategy sets taken together.A mechanism combined with a profile of possible types, the probability density of the possible realization of types, and the utility functions define a game of incomplete information.

We discussed social welfare mechanism which implements a social choice function.  A direct revelation mechanism is a mechanism in which the strategies are truthfully as per the type and all the functions are utility functions and the outcome  is directly the social choice function. 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.

#codingexercise
Find a pair with a given sum in a balanced BST

bool IsPresent(Node root, int val)
{
 if (root == null) return false;
 if (root.data == val) return true;
 if (root.data < val)
     return IsPresent(root.right, val);
else
     return IsPresent(root.left, val);
}

void FindPair(Node root, int sum)
{
if (root == null) return false;
for (int i =0; i <= sum/2; i++)
   if (IsPresent(root, i) && IsPresent(root, sum-i))
       Console.WriteLine("Found pair {0} and {1}", i, sum - i);
}
also we could use a cross join for a cartesian product in pseudo code as follows:
Void FindPair(node root, int sum) 
{ 
Var list = new List<int>(); 
InOrder(root, ref list); 
list.AsQueryable().Join(list, x => x, y=>y, (x,y)=> new {x = x, y = y}). Select( (x,y) => (x+y == sum)).ForEach( (x,y) => Console.WriteLine("Found pair {0} and {1}", x, y)); 

}