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.

Today we discuss privacy, clustering and the web-graph. Privacy is important enough that in Computer Science we have standards to safeguard it. Privacy is endangered when the decisions about the use of personal information are made by the entities other than the person involved. These anomalies are called extranalities and are often considered the root cause of trouble. Personal information is said to be intellectual property that bears negative royalty. Coalition game theory can be used as a modeling tool in this case as well. The outcomes are the fair royalty due to the individual and this model has interesting algorithmic problems.

Clustering is yet another important domain of use for game theory. Although its widely practiced, it does not have the strict foundation as other areas because they are far too many criteria for the goodness of a clustering. There are many ways to come up with clusters and little guidance to choose between them. Economic  The author states that economic considerations are crucial for understanding the issues here as well.  Clustering strives to improve decision making by allowing different segments of space to be treated differently which is a domain of novel optimization problems called segmentation problems.

To take an example of such a study of clustering, the author cites how a monopolist would want to cluster its customers into k segments of a demand curve, with a different price to each segment, in order to maximize revenue. The clustering that maximizes revenue subdivides the customers into segments of consecutive values  of ai/bi. where a and b are customer boundaries and i ranges from 1 to k. The optimum can be computed in O(n^2) by dynamic programming. 

int GetOptimumRevenueFrom(n, a, b, customers)
{
int ratio = a/b
double val = 0;
var clusters = new List<double>()
for (int i = 0; i < n; i++)
{
val += ratio/n;
clusters.Add(val);

}
return GetOptimumRevenue(clusters, n, a, b);
}
double GetOptimumRevenue(clusters,n, a,b, customers)
{
for (int i = 0; i < customers.count; i++;)
      classify(customers[i], clusters);
double revenue = 0;
for (int k =0; k < n; k++)
 {
      revenue += customers.select(x => x.label == clusters[k]).count()*PriceQuantity(clusters[k]);
  }
return revenue;
}
clustering is iterative and we can employ any similarity measure