3/28/2022 William Gillespie
ISE Professor Jugal Garg has been awarded the Dean’s Award for Excellence in Research by The Grainger College of Engineering.
Written by William Gillespie
ISE Professor Jugal Garg has been awarded the Dean’s Award for Excellence in Research by The Grainger College of Engineering.
Jugal Garg joined ISE faculty as an assistant professor in the spring of 2016, with a research background at the intersection of economics and computation.
Garg received the prestigious NSF CRII award in early 2018, followed by the NSF CAREER Award in 2020. He won the James Franklin Sharp Outstanding Teaching Award in Industrial Engineering in 2019, and has frequently appeared in the student-juried list of teachers ranked as excellent.
In the past year, Garg has published more than twenty papers in top-tier venues of Artificial Intelligence, Operations Research, and Theoretical Computer Science. His paper “Multi-Agent UAV Routing: A Game Theory Analysis with Tight Price of Anarchy Bounds” won the INFORMS Koopman prize in 2021.
Garg’s recent work focuses on the age-old problem of fair allocation of goods and chores, and provides state-of-the-art results on some of the most important questions in the area.
Fair division is the problem of allocating a set of desired goods and/or undesired tasks among agents that makes every agent content (i.e., is “fair”) and achieves high welfare (i.e., is “efficient”). The formal study of this problem dates to the seminal work of Steinhaus, a Jewish, Polish mathematician who survived World War II and went on to be considered one of the founders of Game Theory. Though fair division is approached as a mathematical problem, the basic need to share is familiar to most, and ancient at that. An everyday example is known as “Divide and Choose”: in dividing, for example, a cake, one party cuts the cake and the other chooses how the two halves are distributed, providing incentive for the cutter to divide as evenly as possible. Divide and Choose has appeared on Sesame Street and is mentioned in the book of Genesis.
The potential real-world applications for streamlined mathematical solutions to complex fair division problems are many, including, for example, the division of family inheritance, partnership dissolutions, divorce settlements, radio and television spectrum allocation, airport traffic management, office space between co-workers, seats in courses, computing resources in peer-to-peer platforms, and sharing of earth observation satellites. The rise of internet platforms has introduced new opportunities to apply fair division (Uber would like to fairly match drivers and passengers, as one example).
The items to be divided can be divisible or indivisible, and they can be desirable (goods) or undesirable (chores). Professor Garg’s work spans all variants of this problem, producing significant results, empirically fast algorithms, and settling important open questions and conjectures, including a solution for what has been called “fair-division’s biggest open question”, a potentially historic breakthrough.
Many of his results rely on the computation of competitive equilibrium, a central solution concept in economics.
The area of equilibrium computation arose in the mid 90’s to address the questions and challenges posed by the new economic models and the associated computational challenges. Economists use the term equilibrium to describe the balance between supply and demand in the marketplace. Under ideal market conditions, price tends to settle within a stable range when output satisfies customer demand for that good or service. Equilibrium is vulnerable to both internal and external influences. The ability to predict that price is quite useful. The advent of the Internet has unleashed new markets at a gigantic scale and revolutionized commerce, social interaction, entertainment, politics, and many other aspects of human life. To understand and operate these systems better, their equilibrium analysis is crucial. Last year, Jugal has made extensive contributions to the algorithms and complexity of equilibrium computation.
In the words of Department Head Jeff Shamma, “the breadth, depth, and creativity of Jugal’s contributions are exceptional. He is a remarkably versatile thinker and researcher, able to work on fundamental and deep problems in fair division and equilibrium computation, while applying the tools and concepts from game theory and related topics to a host of important applications in OR, economics, AI, and beyond. He has an ambitious agenda to advance the frontiers of the computational complexity of fundamental problems in computational economics and AI theory and apply game-theoretic ideas to several areas that span multiple disciplines.”
Asked how the award would affect his research, Professor Garg says, “The award has fueled my enthusiasm to keep pursuing research on fundamental open questions in computational economics and AI theory.”
Congratulations, Jugal!