ISE professor receives award to study market algorithms

The notion of market equilibrium is central to the field of economics, but recently it has also been applied to resource allocation problems. The allocation of indivisible goods — which include cars, laptops, or any other product that cannot be split into smaller units  —  presents challenges in defining and computing its market equilibrium.  Yet that is the plan of ISE professor Jugal Garg, who recently received a grant from the National Science Foundation to design fast algorithms that calculate market equilibria.

Garg received the prestigious CRII award in early 2018, which will fund his research and support two PhD students and an undergraduate student for two years. Working at the intersection of operations research, economics, and computer science, he hopes to develop new algorithms that can find the equilibrium allocation in a variety of scenarios.

“Market equilibria tend to be inherently fair and efficient, and that’s why they are best suited for a fair allocation of goods,” Garg says. In his work, he defines “fairness” to mean “envy-free,” where the best solution is where every individual is happiest with what they have in relation to everyone else.

As an example, Garg describes a hypothetical where five people have to choose a bedroom in an apartment. The five rooms are different, and each person has their own preference. The fair solution determines who lives in which room and how much they pay in a way in which no one wants a room other than their own.

But known problems in operations research make the search for fair solutions challenging. Garg wants to create the tools needed to solve those problems.

“We want to come up with fast algorithms, and we want to solve the fair allocation problems using market equilibria, many of them are unsolved,” he says. “To do that, we need to develop new algorithmic tools and techniques, and we need new structural insights on these problems.”

Garg says that his research received its funding so it can make impactful progress in equilibrium computation, fair division, and other long-standing open problems in network flow and optimization. His work could form the basis of a society that runs more smoothly and sees less bickering over a split check.

 

Related Links