报告题目: A Discrete and Bounded Locally Envy-Free Cake Cutting Protocol on Trees

报告人：黄昕博士

报告时间：2023年11月28日（周二）上午 10点-12点

报告地点：科技园阳光楼南815

邀请单位：bat365在线登录入口、离散数学及其应用省部共建教育部重点实验室

参加对象：欢迎感兴趣的老师和学生参加

摘要: We study the classic problem of fairly dividing a heterogeneous and divisible resource -- modeled as a line segment [0,1] and typically called as a cake -- among n agents. This work considers an interesting variant of the problem where agents are embedded on a graph. The graphical constraint entails that each agent evaluates her allocated share only against her neighbors' share. Given a graph, the goal is to efficiently find a locally envy-free allocation where every agent values her share of the cake to be at least as much as that of any of her neighbors' share.The most significant contribution of this work is a bounded protocol that finds a locally envy-free allocation among n agents on a tree graph using O(n^n) queries under the standard Robertson-Webb (RW) query model. The query complexity of our proposed protocol, though exponential, significantly improves the currently best known hyper-exponential query complexity bound of Aziz and Mackenzie [AM16] for complete graphs. In particular, we also show that if the underlying tree graph has a depth of at most two, one can find a locally envy-free allocation with O(n^4 logn) RW queries. This is the first and the only known locally envy-free cake cutting protocol with polynomial query complexity for a non-trivial graph structure.Interestingly, our discrete protocols are simple and easy to understand, as opposed to highly involved protocol of [AM16]. This simplicity can be attributed to their recursive nature and the use of a single agent as a designated cutter. We believe that these results will help us improve our algorithmic understanding of the arguably challenging problem of envy-free cake-cutting by uncovering the bottlenecks in its query complexity and its relation to the underlying graph structures.

报告人简介：黄昕本科毕业于南京大学计算机系，后于2019年获得香港中文大学博士学位，之后在以色列理工进行博士后研究。主要研究方向是公平分配问题，研究成果发表于领域内顶级国际会议EC、WINE、IJCAI、AAAI以及权威期刊ACM Transactions on Economics and Computation、European Journal of Operational Research等。