プレゼントを公平に配る最適なくじ引きを作ろう！🎁

本記事は CyberAgent AI Lab Advent Calendar 2024 16日目の記事として執筆しております！🎄

はじめに

メリークリスマス！サイバーエージェント AI Lab 経済学社会実装チームの冨田／みーとみ（@miiitomi）です。

もうすぐクリスマスということで、イベントで子どもたちにプレゼントを配ったり、パーティでプレゼント交換をする機会のある方もいらっしゃるかもしれません。人によって有利不利があると不公平なので参加者間で公平にプレゼントを配りたい一方で、プレゼントが数種類ある場合には人によって欲しいプレゼントが異なることもあるでしょう。そのような状況では、どのようなルールでプレゼントを配ると良いのでしょうか？

本記事では、プレゼントを配るときに使える最適なくじ引きを作成するアルゴリズムと、それを簡単に実行できる自作ウェブアプリをご紹介したいと思います。

説明はいいから早くそのアプリを触ってみたいという方はこちらをどうぞ！アルゴリズムが気になる方はぜひ本記事をご覧ください。

目次

プレゼント割り当て問題

よくある方法

プレゼントごとのくじ引き

受け取り手優先順序のくじ引き

最適くじ引き：PSルール

最適くじ引きアプリ

プレゼント配り以外の応用例

まとめ

プレゼント割り当て問題

ここで私たちが考えたい問題は、以下のようなものになります。

プレゼント割り当て問題

プレゼントは $P$ 種類あり、$j$ 種類目のプレゼントは $q_j$ 個ある。

プレゼントの受け取り手は $R$ 人いる。

各受け取り手には、欲しいプレゼントの希望順序がある。

希望の例：「第 $1$ 希望：プレゼント $3$、第 $2$ 希望：プレゼント $1$、それ以外は希望しない」など。

各受け取り手に 1 人最大 1 つずつ、プレゼントを配りたい。

全員が納得するようにプレゼントを公平に配るには、どのようなルールで配ると良いでしょうか？

よくある方法

プレゼントが全て十分な数あるか、受け取り手が皆違うプレゼントを希望しているなら、それぞれに好きなものを配れば良いでしょう。そうでない場合に、受け取り手全員を公平に扱ってプレゼントを配るには、くじ引きなど何らかの方法でランダムに配る必要があります。このような状況でよく使われている方法がいくつかあるので、まずそれらを検討してみましょう。

プレゼントごとのくじ引き

よくある方法一つ目の「プレゼントごとのくじ引き」では、以下のようなルールでプレゼントを割り当てます。

ルール 1：プレゼントごとのくじ引き

$1$ 種類目のプレゼントから $P$ 種類目のプレゼントまで順に、以下を行う。

今配ろうとしているプレゼントは $j$ 種類目で、$q_j$ 個あるとする。

まだプレゼントを貰っていない人のうち $q_j$ 人までの人をくじ引きで選び、プレゼント $j$ を渡す。

プレゼントを貰っていない人がいなくなったら終了する。そうでなければ次のプレゼントに進む。

このようなくじ引きによるプレゼント配りは広く使われていますし、またイベントにおいてはくじ引きのワクワク感により盛り上がるでしょう。しかし、参加者の希望を一切考慮せずに割り当てを行なっているため、以下のような不納得感が残ってしまう可能性があります。

例 1：プレゼントごとのくじ引きの非効率性

プレゼントは A, B, C, D の$4$種類で、それぞれ $1$ つずつります。参加者は 1, 2, 3, 4 の $4$ 人で、希望は以下の通りです。

第1希望第2希望第3希望第4希望

1 さん A B C D

2 さん A B C D

3 さん B A D C

4 さん B A D C

いま、くじ引きによってプレゼントが割り当てられ、結果は以下のようになったとします。

プレゼントA：3 さん

プレゼントB：1 さん

プレゼントC：4 さん

プレゼントD：2 さん

このとき、以下のように受け取り手に不納得感が残ってしまいます。

3 さんと 1 さんについて、プレゼント A を貰った 3 さんはプレゼント B の方が良かったと思っており、プレゼント B を貰った 1 さんはプレゼント A の方が良かったと思っています。したがって、「二人の貰うプレゼントが逆だったなら、二人ともより嬉しかったはず」という意味で、この割り当ては非効率的です。

4 さんと 2 さんについても同様。

	第1希望	第2希望	第3希望	第4希望
1 さん	A	B	C	D
2 さん	A	B	C	D
3 さん	B	A	D	C
4 さん	B	A	D	C

プレゼントごとのくじ引きでは受け取り手の希望を考慮せずに割り当てを行うため、例 1 のように全員の希望をより叶える余地の残る非効率的な割り当てとなってしまう可能性があります。

プレゼント配りが少人数で友人同士の間で行われているのであれば、例のような非効率性が残っても後で交換すればいいかもしれません。しかし、ある程度の参加者人数がいたり、皆が友人同士というわけではない場合には、後から交換によって非効率性を解消することは困難です。したがって、このような非効率性を残さないルールを用いる方が、受け取り手の納得感の観点から考えると望ましいでしょう。

受け取り手優先順序のくじ引き

次は受け取り手の希望を考慮した、次のようなルールを考えてみます。

ルール 2：受け取り手優先順序のくじ引き

$R$ 人の受け取り手それぞれの優先順序を、第 $1$ 優先から第 $R$ 優先までくじ引きによって決める。

第 $1$ 優先の受け取り手から順に、以下を行う。

残っているプレゼントのうち希望するものがあれば、そのうち最も希望するプレゼントを貰う。

このルールは受け取り手の希望を考慮しており、一見良さそうに見えます。全員が受け取れる可能性のあるもののうち最も希望するものを貰っているため、プレゼントの割り当て後に非効率性が残ってしまうこともありません。

しかし、事前の「受け取るプレゼントの確率分布」の割り当ての意味では、これも非効率となってしまう状況があります。以下の例を見てみましょう。

例 2：受け取り手優先順序のくじ引きの事前の非効率性

プレゼントと受け取り手・希望は例 1.と同様とします。例えば受け取り手優先順序が 1, 2, 3, 4 の順に決まったとすると、割り当ては以下のようになります。

優先順序1位：1 さん - プレゼントA

優先順序2位：2 さん - プレゼントB

優先順序3位：3 さん - プレゼントD

優先順序4位：4 さん - プレゼントC

受け取り手の優先順序の決め方は全部で $4! = 24$ 通りあり、それぞれで決まる割り当てを数えると、各受け取り手が各プレゼントを貰う確率を計算することができます。

プレゼントA プレゼントB プレゼントC プレゼントD

1 さん $5 \over 12$ $1 \over 12$ $5 \over 12$ $1 \over 12$

2 さん $5 \over 12$ $1 \over 12$ $5 \over 12$ $1 \over 12$

3 さん $1 \over 12$ $5 \over 12$ $1 \over 12$ $5 \over 12$

4 さん $1 \over 12$ $5 \over 12$ $1 \over 12$ $5 \over 12$

しかし、この「貰うプレゼントの確率分布」の割り当ては、以下のように非効率です。

いま、くじを引く前に、1 さんと 3 さんが「 1 さんがプレゼント B を得るか、もしくは 3 さんがプレゼント A を得た場合、1 さんと 3 さんはプレゼントを交換する」という約束をしたとします。このとき、二人の貰うプレゼントの確率分布は以下のように変わります。

プレゼントA プレゼントB プレゼントC プレゼントD

1 $1 \over 2$ $0$ $5 \over 12$ $1 \over 12$

3 $0$ $1 \over 2$ $1 \over 12$ $5 \over 12$

二人とも第 2 希望のプレゼントを貰う確率が減って、その分第 1 希望のプレゼントを貰う確率が上がっているため、二人ともこの約束によってより希望が叶えられるようになります。

したがって、元の貰うプレゼント確率分布の割り当ては、「誰も損することなく一部の人がより希望を叶えられる余地を残していた」という意味で非効率的です。

	プレゼントA	プレゼントB	プレゼントC	プレゼントD
1 さん	$5 \over 12$	$1 \over 12$	$5 \over 12$	$1 \over 12$
2 さん	$5 \over 12$	$1 \over 12$	$5 \over 12$	$1 \over 12$
3 さん	$1 \over 12$	$5 \over 12$	$1 \over 12$	$5 \over 12$
4 さん	$1 \over 12$	$5 \over 12$	$1 \over 12$	$5 \over 12$

	プレゼントA	プレゼントB	プレゼントC	プレゼントD
1	$1 \over 2$	$0$	$5 \over 12$	$1 \over 12$
3	$0$	$1 \over 2$	$1 \over 12$	$5 \over 12$

よって、受け取り手優先順序のくじ引きによる事前の「貰うプレゼントの事前の確率分布の割り当て」は、皆の希望をより叶える余地を残していた非効率な割り当てとなる可能性があります。この事前の非効率性は、当事者同士の約束によって割り当て前に事前に解消することは、少人数であっても困難でしょう。皆の希望を最大限叶える公平で最適なプレゼント配りルールを作るためには、この事前の非効率性も生じない方が望ましいと考えられます。

最適くじ引き：PSルール

では、事前の非効率性も生まない公平で最適なくじ引きを作るには、どのようにしたら良いでしょうか？

それは Bogomolnaia and Moulin (2001) によって提案されたPSルール（Probabilistic Serial rule）によって実現することができます。 PSルールは、受け取り手が希望するプレゼントを貰う割合を少しづつ「食べていく（eating）」という表現を使って、以下のように説明されます。

ルール 3：PSルール

最初、各プレゼント $j$ の量は $q_j$ ある。

$t = 0$ 秒から $t = 1$ 秒までの $1$ 秒間、各参加者 $i$ は以下を行う。

今の $t \in [0, 1]$ 秒時点において、残っている量が $0$ より大きいプレゼントのうち最も希望するプレゼントを、秒速 $1$ で食べていく。

あるプレゼントを複数の人で食べている時は、それぞれが同時に秒速 $1$ でそれを食べる。

今食べているプレゼントの量が $0$ になった瞬間に、残っているプレゼントのうち次に希望するプレゼントを食べ始める。

$1$ 秒間に $i$ さんがプレゼント $j$ を食べた量を $e_{i,j}$ とし、それを $i$ さんがプレゼント $j$ を貰う確率とする。

上の説明ではやや分かりにくいと思うので、例を見てみましょう。

例 3：PSルールの適用

プレゼントと受け取り手・希望は例 1 と同様とします。この例に対しPSルールを適用すると、以下のようになります。

$t = 0$ 秒目、1 さんと 2 さんは A を、3 さんと 4 さんは B を食べ始める。

$t = {1 \over 2}$ 秒後、1 さんと 2 さんはそれぞれ A を $1 \over 2$ ずつ食べて A は無くなり、同時に 3 さんと 4 さんも B を $1\over 2$ ずつ食べて B も無くなる。

1 さんと 2 さんは C を食べ始め、3 さんと 4 さんは D を食べ始める。

$t = 1$ 時点で、1 さんと 2 さんはそれぞれ C を $1 \over 2$ ずつ食べて C は無くなり、同時に 3 さんと 4 さんも D を $1 \over 2$ ずつ食べて D も無くなる。

よって、各受け取り手が貰うプレゼントの確率分布は、以下のようになる。

プレゼントA プレゼントB プレゼントC プレゼントD

1 $1 \over 2$ $0$ $1 \over 2$ $0$

2 $1 \over 2$ $0$ $1 \over 2$ $0$

3 $0$ $1 \over 2$ $0$ $1 \over 2$

4 $0$ $1 \over 2$ $0$ $1 \over 2$

	プレゼントA	プレゼントB	プレゼントC	プレゼントD
1	$1 \over 2$	$0$	$1 \over 2$	$0$
2	$1 \over 2$	$0$	$1 \over 2$	$0$
3	$0$	$1 \over 2$	$0$	$1 \over 2$
4	$0$	$1 \over 2$	$0$	$1 \over 2$

PSルールによって作られる貰う確率分布の割り当ては、事前の非効率性のない、皆の希望を最大限叶える効率的なものとなります（詳細は元論文、または日本語では小島・河田 (2024) の 7 章を参照）。

また、PSルールが行うのは上記のような貰うプレゼント確率分布の表を作るところまでですが、Birkhoff-von-Neumannの定理を用いることで実際にくじを引いてプレゼントの割り当てを決定することができます。¹

最適くじ引きアプリ

PSルールによる公平な最適なくじ引きは理論的にとても良い性質を持っていますが、手作業で実際にこの最適くじ引きを実行するのは簡単ではありません。

そこで私は、このPSルールによる最適くじ引きを簡単に実行できるこちらのウェブアプリを作成してみました！直感的に簡単に使えるように作ったので、興味を持った人はぜひこちらを使ってみてください！

プレゼント配り以外の応用例

これまでプレゼント配りの状況を例に説明してきましたが、日常生活において類似の問題は数多くあります。

4 人家族でケーキを 4 種類買ってきた。それぞれの希望をもとに、食べるケーキをくじで決めたい。
学校のクラスの委員決めで、生徒の希望と各委員の定員をもとに、一人一つの委員に決定したい。
会社のある部署で、メンバーが毎週持ち回りで一人半年に一回、プロジェクトの進捗状況を発表している。半年間の候補日の中で各メンバーの担当日時を、それぞれの希望をもとに決定したい。

このような状況でも、PSルールによって割り当てを決定することができます。ちなみに 3 点目については、私たちサイバーエージェント AI Labの「進捗共有会」という会で、実際にPSルールを用いてメンバーの担当日決めを行っています。

まとめ

経済学とコンピュータサイエンスの知見を用いて、人と人やものをマッチさせる良い方法を理論的に考える分野にマッチング理論という分野があり、それらの理論的考察から実際の市場・制度設計を行う実践的な分野にマーケットデザインと呼ばれる分野があります。マッチング理論・マーケットデザインの学術的知見は、近年国内外の多くの分野で広く応用されるようになりました。本記事で紹介した確率的割り当て問題（Random Assignment Problem）とPSルールも、これらの分野で研究されてきた問題です。

サイバーエージェント AI Lab 経済学社会実装チームでもマッチング理論・マーケットデザインの研究・社会実装プロジェクトを行なっています。一例として、東京大学マーケットデザインセンター（UTMD）と自治体と取り組んでいる保育所利用調整の社会実装プロジェクトについては、今回のCyberAgent AI Lab Advent Calendar 10日目の竹浪さんの記事「社会実装されたらいいなと思っていたら、自分も一緒に実現していた話」で紹介されています。ちなみに、マッチング理論の分野でより一般に広く知られている、DAアルゴリズムによって男性と女性のマッチングができるこちらのアプリも作ってるので、こちらもよかったらご覧ください。

本記事やアプリを通して、マッチング理論・マーケットデザインや私たちの取り組みに興味を持っていただける方がいましたら大変嬉しいです。

今年の冬はぜひ最適くじ引きアプリでプレゼント交換をして、素敵なクリスマスをお過ごしください！🤶

では常にPSルールを用いるのがベストかというと、必ずしもそうではない状況もあるかもしれません。PSルールは満たさないが受け取り手優先順序のくじ引きは満たす良い性質として、「受け取り手が自身の希望を偽って申告することによって得することが絶対にない」という耐戦略性と呼ばれる性質があります。参加者が少なく互いの希望がある程度予想されるため、希望申告の戦略的駆け引きが深刻になりうる状況や、主催者にとって正しい希望情報データを引き出すこと自体に価値がある状況では、事前の効率性を犠牲にして耐戦略性を満たすルールを使う方が良い場合も考えられます。今回は、受け取り手優先順序のくじ引きは実施が比較的容易であることを考えて、手作業で実施するのがより困難なPSルールをアプリとして実装してみることにしました。 ↩︎