Contention Resolution with a Fast-but-Fickle Channel
说明快慢信道下的争用解决：一个快速但不稳定的信道
简介论文研究多个设备在共享信道上争用传输的问题。作者考虑一条可靠的慢信道和一条可能被随机中断的快信道，并提出随机化算法RACE，在快信道可用时利用它、中断时在慢信道上保持进展。文中给出了延迟与切换开销的竞争比结果，并证明了相应的下界。
本页没有符合条件的条目（筛选只在本页内进行）。
★★★★☆ 值得关注
Computing EF1 Allocations under Budget Constraints in Polynomial Time
说明在预算约束下于多项式时间内计算EF1分配
简介本文研究在预算约束和可加估值下将不可分割物品公平分配给各主体的问题，要求分配满足在移除一件物品后消除嫉妒的EF1条件，并同时针对包含未分配物品的慈善机构。作者给出了异质估值下计算EF1分配的多项式时间算法，并证明检测EF1违反是NP完全问题。此外，还给出了EFX在特定估值情形下的多项式时间算法。
看点解决了预算约束下多项式时间计算EF1分配的公开问题，并给出复杂度结果与近似保证，理论贡献突出。
Learning Global Equilibria in Non-Concave Prospect Theoretic Games
说明非凹前景理论博弈中全局均衡的学习算法
简介本文研究人类行为偏离理性时的非合作博弈，采用前景理论刻画主体在风险下对收益和损失的感知，这使效用函数呈非凹、非凸，求均衡困难。作者提出一种基于极小化-极大化（MM）的学习算法，在势函数满足近端 Polyak-Lojasiewicz 条件下证明其全局收敛到势函数最大化的纳什均衡，并说明如何利用 MM 极小化子结构实现分布式计算。