Distributed Scheduling Mechanisms

0621416-Hajek分布式调度机制项目的主要目标是探索基于市场的分布式调度算法的设计和分析，使代理能够在线预订资源。在面对困难的组合问题时，将研究获得计算可行性的方法，包括：(1)以受控的方式权衡最优性，同时保留重要的性质，(2)专注于平均情况或最坏情况的性能，以及(3)利用未来的不确定性往往使在线算法比离线算法更简单的事实。这项研究的一个有趣的副业是确定分布式智能代理可以像集中式算法一样有效地进行在线选择的机制。智力优势：该项目将汇集最近研究的不同领域的工具，包括来自拍卖理论和微观经济学机制设计的工具，在线算法的竞争分析，确定性和随机优化方法，以及局部和全局稳定性分析。更广泛的影响：这项工作可能在许多社会和经济环境中有广泛的应用。例如，这些方法可能被用于各种不同的应用，如向大型组织中的个人分配任务，或向灾难恢复任务中的应急小组分配搜索和救援资源。工程应用将包括在无线网络中预留传输带宽。

0621416 - HajekDistributed Scheduling MechanismsThe 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.