本文へジャンプ

  • HOME
  • 講演会情報

講演会情報

グラフにおける公平分担問題 (Division of a Graph)
講演者:五十嵐歩美(九州大学システム情報学府)
平成31年2月15日(金)15時〜16時30分 理学部7号館2階214講義室
公平分担問題とは,異なる選好を持つ人々にどのように複数の財を公平に分担するかを考える資源配分問題のことである. 1948年にHugo Steinhausがケーキ分担問題の数学的なモデルを提案して以来, 経済学, 計算機科学, 数学の多岐にわたる学問領域で高い関心を集めた. 古典的なモデルでは, ケーキや土地のように分割可能な財に対する公平分担問題に対して研究が主であったが, 近年分割が可能でない複数の財を公平に分担するにはどうすればよいか, 広く研究が行われるようになった. 分割財の分担と異なり, 非分割財の分担では, 他人の持分を羨むことがない無羨望分担の存在が保証されない. そのため, 近似的な公平性の概念またそれらを満たす解の存在を保証できるかどうか, 議論が盛んに行われるようになった. 本発表では, 主に人工知能分野における最新の研究について紹介した後, グラフの連結制約条件付きの公平分担問題に関する発表者らの成果について紹介する.

English Abstract:
A famous literature considers the problem of cake-cutting. There, a divisible heterogeneous resource (usually formalized as the interval [0,1]) needs to be divided among n agents. Each agent has a valuation function over subsets of the cake. The aim is to partition the cake into n pieces, and allocate each piece to one agent, in a ``fair'' way. By fair, we will mean that the allocation is envy-free: no agent thinks that another agent's piece is more valuable than her own. In many applications, the resources to be allocated are not infinitely divisible, and we face the problem of allocating indivisible goods.
In this talk, I would like to present some recent works on fair division of indivisible goods under connectivity constraints. Agents have some preferences over the bundles and they are only interested in receiving a connected bundle of items. This model is particularly relevant when the items have a spatial or temporal structure, for example, if we wish to allocate land, rooms, or time slots to agents. Time slots, for instance, are naturally ordered in a sequence, and agents will often only value being allocated a contiguous chunk of time, particularly when restart costs are prohibitive. We show that when the graph is a path, envy-freeness up to one good (EF1) allocations are guaranteed to exist for arbitrary monotonic utility functions over bundles, provided that either there are at most four agents, or there are any number of agents but they all have identical utility functions. Our existence proofs are based on classical arguments from the divisible cake-cutting setting, and involve discrete analogues of cut-and-choose, of Stromquist's moving-knife protocol, and of the Su-Simmons argument based on Sperner's lemma. For the case of two agents, we completely characterize the class of graphs G that guarantee the existence of EF1 allocations as the class of graphs whose biconnected components are arranged in a path. This class is strictly larger than the class of traceable graphs; one can be check in linear time whether a graph belongs to this class, and if so return an EF1 allocation.