Computing violated sets in a market equilibrium problem with constant prices

Consider Fisher’s and Arrow-Debreu’s market equilibrium models for a linear utilities case consisting of a set BB of buyers and a set GG of divisible goods. Supposing that a vector of prices P=(p1,…,p|G|)P=(p1,…,p|G|) for goods is given and there are some buyers with surplus money, but, by the politics of the market, prices PP are constant and cannot be changed in order to compute an equilibrium. In this paper, a set of buyers with surplus money is called a violated set. First, we define a kind of violated set called maximum mean, then compute a set of buyers with maximum surplus money corresponding to the definition of a maximum mean violated set. We show a maximum mean set is found in O(mnlog(n2/m))O(mnlog(n2/m)) time, where n=|B|+|G|n=|B|+|G|, and mm is the number of pairs (i,j)(i,j), such that buyer ii has some utility for purchasing goods jj.