Today we will start discussing the paper by Papadimitriou  - Algorithms, Games and Internet.
In a game, each of the n players can choose among a set of strategies S, i = 1, .. n and there are functions ui, i = 1 .. n: S1 x S2 ... Sn. These functions result in a payoff for each player for each such combined choice. The fundamental question of Game Theory is what constitutes rational behavior in such a situation ? One such explanation is the Nash equilibrium. A combination of strategies xi belongs to S1, xn belongs to Sn, for which ui (x1, ... xi, ... xn) >= ui (x1, ...xi-dash, ...xn) for all i and xi-dash belong to Si: a behaviour that is from which no player has an incentive to deviate. The Nash equilibrium is attained when each player has chosen a strategy and no player benefits from changing his or her strategy. The set of strategy choices and their corresponding payoffs remain unchanged.
Nash equilibrium has a wide variety of applications because it allows us to formalize what happens if several people or several institutions  are making decisions at the same time, and if the outcome depends on the decisions of the others.  Nash's equilibrium essentially says that we cannot predict if we consider the decisions by the participants in isolation and instead that decision making must be studied by taking into account the decision-makings of others.  The decision making is expressed in terms of a probability distribution over possible actions by each player.  The modern version of Nash equilibrium discussion takes into account this mixed strategy which is shown to exist for any zero sum game involving finite set of actions. Nash's equilibrium is considered to be much more broader than pure strategy method because it makes no judgement about the optimality of the equilibrium being generated. This optimality in terms of payoffs or profit is generally restricting in the definition of the equilibrium.  Furthermore it has applications in non-cooperative games or hostile games. A classic example of such a game is prisoner's dilemma.  This game is meant to show that two completely rational individuals might not cooperate, even if it appears that it is in their best interest to do so.  This example is described so. Two members of a criminal gang are arrested and imprisoned Each prisoner is in a solitary confinement with no means of communicating with one another.  The prosecutors lack sufficient evidence to lock each up so they offer a bargain to each prisoner -betray the other by testifying or cooperate with the other by remaining silent. If A and B both betray each other, each of them serves two years in prison. If A betrays B but B remains silent, A will be set free and B will serve three years in prison and vice versa.  If A and B both remain silent, both of them will serve only one year in prison because there is not enough evidence. If each prisoner pursues the individual reward logically, they will both betray each other with less than optimum outcome. Instead if they show a cooperative behaviour and remain silent, they get a better outcome. Remaining silent is not the only option. The players could also choose to defect. In fact, mutual defection is considered the only strong Nash equilibrium in the game.From this equilibrium, the prisoners could only do worse by unilaterally changing strategy. The dilemma is that mutual cooperation yields a better outcome but it is not the rational outcome because from a self interest perspective, the choice to cooperate at the individual level is irrational.
#codingexercise
Find the maximum number of submatrix contained within a bounding rectangle (represented by a list of tuples where the first item in the list is the top left corner and the last is the bottom right)
int GetCount(List<tuple<int,int>> corners, List<List<Tuple<int,int>>> submatrices)
{
return submatrices.Count( x => corners.first() <= x.first() && corners.last()>= x.last());
}
we can have an extension method on the tuple that compares it to another