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.