Participants and resource-people at the ACM summer school on 'An Invitation to Algorithmic Game Theory'.
A two-week ACM (Association for Computing Machinery) school on ‘An Invitation to Algorithmic Game Theory’ was organized at The Institute of Mathematical Sciences (IMSc), Chennai from 1st to 14th July 2024. With support from ACM India, IMSc and Google, the summer school introduced students to algorithms in game theory.
The summer school was attended by over 40 participants from across the country, with about three-quarters of them represented by Bachelors and Integrated Masters students. The goal was to have students from diverse educational backgrounds including state universities and private engineering colleges, says Sushmita Gupta, a faculty at IMSc, who coordinated the event.
Algorithmic game theory emerged with the dawn of the Internet marketplace, when the need to execute millions of auctions every second required a marriage of game theory and efficient algorithm design, says Sushmita. It deals with games between players who make strategic choices about their moves based on available information to achieve some objective. Algorithmic game theory allows us to frame problems using game design and analyze the costs and benefits of strategies across various players to efficiently identify an optimal solution. These problems can fall within competitive or cooperative contexts where the objective is to maximize value measured as financial gain or social welfare. Equilibrium concepts help us assess outcomes and their persistence under various game plays.
At the summer school, instructors walked participants through a wide array of problems peppered with real-world applications. “The goal was to give an intentionally scattered sampling of canonical and widely studied questions that are the bread and butter of game theory,” says Sushmita.
Swaprava Nath from IIT Bombay introduced the problem of auctions to allocate resources while optimizing for profit and the value held by bidders. Sushmita illustrated this using the landmark AdWords algorithm, which helps search engines maximize revenue by matching advertisers to search words. Shweta Jain from IIT Ropar continued with the example of internet advertising to describe the multi-armed bandit problem. Here, a naive player makes a choice by sampling multiple options and learns about rewards through exploration. Chandrashekar Lakshminarayanan from IIT Madras provided an overview of Artificial Intelligence and its applications in two-player strategy games such as chess and Go.
Aparna Taneja’s team at Google’s AI for Social Good applied the multi-armed bandit problem to decide which recipients received an intervention to improve the engagement in a maternal health program. Arun Sai Suggala and Dheeraj M Nagaraj from Google Research spoke about real-word applications of the multi-armed bandit problem across multiple users in a collaborative framework. Palash Dey from IIT Kharagpur discussed algorithms for stable matching of partners based on their preference, which has a rich body of theory and human applications. Pallavi Jain from IIT Jodhpur spoke about ways of dividing items between people under various notions of fairness. Sushmita returned to discuss congestion games, where the goal is to find ways of routing traffic through a road network to minimize overall travel time.
C Ramya from IMSc spoke about computational complexity, which is an important constraint in algorithmic game theory. This is because one cannot take an infinite amount of time to solve a problem, leading to considerations about finding a solution in reasonable time. B Srivathsan from Chennai Mathematical Institute spoke about games on graphs, which is a powerful mathematical framework to study questions in logic, verification and automata theory.
“The summer school was more of an invitation to higher studies. Our ardent hope is that it expanded the horizons of students and informed them about a fascinating topic. We wanted them to feel that higher studies can be interesting and worth exploring, be it in algorithmic game theory or something entirely different,” says Sushmita about the motivation behind the event. “It is like eating something delicious and remembering the feeling that you enjoyed it.”
“Each day was a new flavour of game theory that I never thought existed,” says Bhavik Dodda, a third year Integrated Masters student from Sardar Vallabhbhai National Institute of Technology, Surat. “I am part of the ACM student chapter at my college where I got to know about the summer school,” he says. Back from the summer school, he was inspired to use a matching algorithm to resolve mismatches between roommates in their recent hostel room allotments. “It did work and that was fun!” he says.
“Through the summer school, I came to know that algorithmic game theory is a very practical area where I can use my knowledge about algorithms and complexity,” says Harsh Sharma, a second year Bachelors student from the Chennai Mathematical Institute. “The lectures didn’t require many prerequisites and we were exposed to many open problems to give us an idea about how it feels to do research in this field,” he adds.
“I have been interested in algorithmic game theory for a while now, but haven’t done a proper course in it and wanted to learn more,” says Krishnashree JB, who is about to finish her Masters degree from PSG College of Technology, Coimbatore. “I am currently working on stable matching and wanted to know about other work in the field, which would help in my career,” Krishnashree says.
“I am from a biology background and I’ve mostly done biology courses,” says Authisha Thirumani Selvam, a fourth year undergraduate student from Indian Institute of Science Education and Research, Pune. “I was also very interested in math but everyone studying it seemed much smarter and I avoided math courses,” she adds. A recent interest in computational social choice drew her to applying to the school. “The summer school was very inviting and didn’t scare me off. It was very intuitive and I really liked that,” she says.
“These programs are much needed, especially for people who are not from well-known institutions,” Sushmita says. They can help undergraduate students who are really bright and have great potential but fall through the cracks due to a lack of guidance. “This program is, honestly, a form of outreach to catch students early. Every student can and should aspire to such opportunities no matter what their current circumstances,” she says earnestly. “IMSc is reaching out to a lot of people through such events and everybody is welcome to participate in them.”
At the summer school, instructors walked participants through a wide array of problems peppered with real-world applications. “The goal was to give an intentionally scattered sampling of canonical and widely studied questions that are the bread and butter of game theory,” says Sushmita.
C Ramya from IMSc spoke about computational complexity, which is an important constraint in algorithmic game theory. This is because one cannot take an infinite amount of time to solve a problem, leading to considerations about finding a solution in reasonable time. B Srivathsan from Chennai Mathematical Institute spoke about games on graphs, which is a powerful mathematical framework to study questions in logic, verification and automata theory.
