Computer Sciences and Information Technology
Title : | Complexity of Manipulative Attacks on Resource Allocation |
Area of research : | Computer Sciences and Information Technology |
Focus area : | Game Theory and Operations Research |
Principal Investigator : | Dr. Pallavi Jain, Indian Institute of Technology (IIT) Jodhpur, Rajasthan (342030) |
Timeline Start Year : | 2023 |
Timeline End Year : | 2025 |
Contact info : | pallavi@iitj.ac.in |
Details
Executive Summary : | The problem of allocating resources to agents is a universal one, involving matching resources to participants in various aspects of life. Fair allocation is a vast topic in algorithmic game theory, with concepts such as envy-freeness, maximin, and Nash welfare. This project aims to explore the trustfulness of fair allocation rules. In a centralized resource allocation system, internal manipulation, such as strategic behavior of agents casting untruthful preferences, has been extensively studied. However, external manipulative attacks, which are well-studied for other collective decision-making scenarios, have not been studied in the context of resource allocation.
The project aims to explore the computational complexity of manipulative attacks on resource allocation systems. It will focus on finding natural models for manipulative attacks specific for fair resource allocation, identifying which fair allocation rules are computationally hard or easy to manipulate under various manipulative attacks, investigating the influence of parameters on computational complexity, and designing efficient algorithms and polynomial kernels for cases where manipulation can be used in good cause. The authors of the proposal, an Indian and a German group, have complementary expertise in different types of problems, including parameterized complexity and algorithmic game theory. |
Total Budget (INR): | 12,40,000 |
Organizations involved