Algorithms for Fisher Equilibrium with Various Constrained Market Agents

There has been a recent surge of computational effort for the equilibrium price vector in a market. The problem has started because of theoretical curiosity in understanding the algorithmic complexity for one of the most fundamental problems in mathematical economics. Mathematical properties, algorithm analytic methods, as well as optimization techniques involved with such problems have been merged to apply to the understanding of the computational complexity, as well as algorithmic solvability of such problems. On another frontier, important application problems have risen to challenge determination and computation of equilibrium prices. Sponsored search has been one example where the effective protocol design for a realistic market became important. There is also a possibility to model it as a Fisher market where advertisers come to purchase clicks, as commercial goods, in this special market. At the equilibrium price, all goods should be sold to customers, or they will be wasted, and all the budgets of advertisers, should be spent (subject to their requirements, such as the maximum price per clicks). Such a Fisher market would demand for a computational solution to a market clearance price. It provides a realistic challenge that has not been seen in the tradition of laissez-faire economics. Expectably, other forms of computational problem for market equilibrium price will also find their applications in various new markets created over the Internet, where data, information and computational access will find no difficulties entering into a possibly equilibrium computing engine for a machine-made solution.In this project, the researchers plan to develop algorithmic understandings for various constrained utility functions such as integrality. This study will consider theoretically meaningful models since they may provide a general guideline in possible application fields. In addition, the researchers also plan to look into some realistic settings for their choices in the constrained utility functions, especially with sponsored search auction settings.