The main goal of the project is to explore the design and analysis of distributed market based scheduling algorithms, which enable agents to reserve resources online. Methods for gaining computational feasibility in the face of the difficult combinatorial problems will be investigated, including: (1) trading off optimality in a controlled way, while retaining important properties, (2) focusing on average case, or worst case, performance, and (3) leveraging the fact that future uncertainty often makes online algorithms simpler than their offline counterparts. An intriguing sideline of the study is to identify mechanisms under which distributed intelligent agents can make online choices as effectively as a centralized algorithm.
Intellectual Merit: The project will bring together tools from disparate areas of recent research, including those from the theory of auctions and mechanism design from microeconomics, competitive analysis of online algorithms, deterministic and stochastic optimization methods, and both local and global stability analysis.
Broader Impact: The work could have broad applications in many social and economic settings. For example, the methods could potentially be used for such diverse applications as the assignment of tasks to individuals in a large organization, or assignment of search and rescue resources to emergency response teams in a disaster recovery mission. Engineering applications would include the reservation of transmission bandwidth in wireless networks.
