当前位置：    新闻动态   2022   戴思佳同学在第三届国际理论计算机联合大会中做了题为”EFX under Budget Constraint ”的报告

 

戴思佳同学在第三届国际理论计算机联合大会中做了题为”EFX under Budget Constraint ”的报告

2022年8月16日

8月16日上午，张涌老师课题组的戴思佳同学在第三届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom，IJTCS-FAW 2022）会议中做了题为”EFX under Budget Constraint ”的报告。主要报告了在公平分配问题中，基于智能体有预算约束的条件下，探索满足最大化纳什社会函数分配能够达到多大的公平性质。并且通过对轮询算法的改进，设计了对于二值估值函数能够在多项式时间内计算出预算可行的达到EFX公平分配的算法。

公平分配（fair division）问题在疫苗分配、政府拍卖和遗产继承等方面有着广泛的应用。在实际生活中，agent 能否被分配某个物品还受到他们自身预算的限制。本报告研究了在预算限制下物品分配的效率和无妒忌（envy-free）性质。在预算限制下，每个物品都对应一个非负的价格，而 agent 的预算要求他们所得物品得总价格不超过其预算。此时 envy-free（BFEF）是指对于任何一个给定的 agent i 和 j，i 不会认为 j  所分配到的任何一个满足 i 自己预算限制的物品子集 S  比自己所分配到的物品更有价值，反之亦然。由于 EF 一般地是无法保证成立的，报告考虑了 EF 的一个松弛版本：将前述定义的  S 修改为 S 去掉任何一个其中的物品 g 的价值，所得限制称为 BFEFX。在每个 agent 对物品的估值是0或者1的情况下，报告给出了一个基于 round robin 和妒忌消除的算法，在多项式时间内可计算出一个满足预算限制的 BFEFX 的分配。同时报告还研究了分配的效率问题，并证明：在同样的条件下，任何一个最大化纳什社会福利的分配都是1/4-近似 BFEFX 的。这里，  a -  近似 BFEFX 是指任何一个 agent 对自己分配到物品的估值都至少是其它 agent 满足预算的物品子集去掉任何一个物品的价值的  a  倍。