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.
Each agent is expected to be a utility maximizer based on the preferences exclusive to the agent. The probability density as well as the sets and the utility functions are assumed to be common knowledge The agents preference depends on the realizations of the set or profile of types so the agents may want the collective decision to depend on the profile of types. So a notion of social choice function  is introduced. This is a function which assigns a collective choice for each possible profile of the agents types.
Moreover this function can be Paretian or Pareto optimal, which is the name given to the most optimal one, if there does not exist a profile where there is a choice from the set of possible alternatives such that the utility  for that choice is greater than or equal to the utility for the collective choice for every type and strictly greater than the utility for the collective choice for some type. Simply put it is the most optimal.
This implies that a social welfare function is Pareto optimal if it selects for every profile of types, an alternative that is Pareto optimal given the agent's utility function. This welfare function only works if each agent is relied upon to disclose his type, however for a given social choice function, an agent may not find it to be in her best interest to reveal this information truthfully.
A mechanism is a collection of a finite number of strategy sets and an outcome function based on the strategy sets taken together. It can be viewed as an institution with rules that determine the procedure for making the collective choice.  The allowed actions of each agent are summarized by the strategy set corresponding to that agent and the rule for how the agents actions get turned into a social choice is given by an outcome function. 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.  This set of rules can be a complex dynamic procedure in which case the elements of the strategy set would consist of contingent plans of actions. A mechanism is said to implement social choice function if there is an equilibrium strategy profile of the game induced by the mechanism such that the outcomes is equal to the utilities for all types belonging to the combinations of possible types when taken together.

Courtesy: Microeconomic theory by Colell, Whinston and Green : Chapter on Incentives and mechanism design

#codingexercise

Find the minimum difference between any two integers in an array.

int GetMinDiff(List<int> A)
{
A.sort();
int diff = int_max;
for( int i =0: i < A.count -1; i++)
    if ( Math.Abs(A[i+1] - A[i] ) < diff )
           diff = Math.Abs(A[i+1] - A[i]);
return diff;
}

In the implementations of testing whether a given integer array is a pre order form or a post order form of a BST, we check for the subarray contained between a root and one of its siblings is strictly a valid subtree of the BST at that level. we dont do the check on both sub trees at that level. This means we can check the values in both sub arrays are strictly less than and strictly greater than the root as the case may be given which sub array is chosen.

Find the maximum difference between any two integers in an array.

int GetMaxDiff(List<int> A)
{
A.sort();
int diff = int_min;
for( int i =0: i < A.count -1; i++)
    if ( Math.Abs(A[i+1] - A[i] ) > diff )
           diff = Math.Abs(A[i+1] - A[i]);
return diff;

}