【IJCAI 2019 | tutorial】不可分项目的公平划分：渐近与图论方法, Fair Division of Indivisible Items: Asymptotics and Graph-Theoretic Approaches (附pdf)

题目主题：

Fair Division of Indivisible Items: Asymptotics and Graph-Theoretic Approaches

简介：

公平划分在过去十年中一直受到博弈论和人工智能界的关注，从公理和计算的角度来看。其目标通常是在感兴趣的代理之间分配资源，以便满足某些公平标准。公平分割的适用范围从解决离婚纠纷、分割遗产到分摊房租、分割家务等。该领域的早期工作主要集中在如何分配土地等可分割资源上。然而，在过去的二十年左右，特别是最近几年，人们对公平分配珠宝和艺术品等不可分割的资源产生了相当大的兴趣。这个设置在某些方面与可分割的设置有本质的不同，因此需要使用新的概念、技术和工具。

在本教程中，我们将首先介绍该地区新来者的公平分工。我们将概述不可分割项目及其属性的主要公平概念。然后，我们将介绍不可分割项目公平划分的两个新框架。首先，我们将给出渐近结果的调查：由于在不可分割的存在下，通常不能满足几个常见的公平概念，一个重要的问题是确定满足每个概念的分配可能在随机实例中存在的条件。我们将介绍概率论和匹配理论中解决这个问题所需的工具。其次，我们将概述最近在网络约束下不可分割项目的公平划分方面所做的工作。在一种情况下，网络描述项之间的物理或时间关系，而代理只对接收连接的项束感兴趣。在另一个场景中，网络描述的是代理之间的关系，而不是项目之间的关系，并要求每个代理都不要嫉妒她的邻居。我们将解释一些存在和复杂性的结果，以及基于可分割的蛋糕切割设置的经典参数的技术。最后，我们将讨论一些源于这些工作的开放性问题。

作者介绍：

Ayumi Igarashi，是JSPS博士后研究员，自2019年4月起由东京大学的Satoru Iwata教授主持。在伊迪丝·埃尔金德教授的指导下，她完成了牛津大学计算机科学系的博士学位。她广泛的研究领域包括博弈论、组合优化和社会选择。她特别关注网络所带来的连接约束问题，特别是在各种情况下的公平和稳定概念的存在和复杂性，例如联盟形成游戏和不可分割项目的公平划分。

Warut Suksompong，是牛津大学计算机科学研究助理（博士后），由Edith Elkind教授主持。他在Tim Rougharden教授的指导下完成了斯坦福大学的博士学位，并在麻省理工学院获得了学士和硕士学位。他的研究兴趣包括算法博弈论、机制设计、公平分工、社会选择理论以及计算机科学与经济学之间的接口问题。他曾在计算机科学、经济学、数学和运筹学领域发表论文。

教程大纲：

• 介绍
  • 公平分工及其应用概述
  • 共同的公平观念（嫉妒自由、相称性、公平性）
• 不可分割商品的公平观念
  • 无妒忌至善（EF1）
  • 无妒忌至善（EFX）
  • 极大极小公平分享（MMS）
• 渐近结果
  • 福利最大化算法
  • 基于匹配的参数
  • 公平分配的不存在
• 图论方法
  • 图的公平分割
  • 近似无嫉妒的联系分配
  • 社交网络上的公平分工
• 总结性和开放性问题