ピッキングシーケンス

ピッキングシーケンスは、公平なアイテム割り当てのためのプロトコルです。m個のアイテムをn 個のエージェントに分割する必要があるとします。アイテムを割り当てる 1 つの方法は、1 人のエージェントに 1 つのアイテムを選択させ、次に別のエージェントに 1 つのアイテムを選択させるというものです。ピッキング シーケンスはm 個のエージェント名のシーケンスであり、各名前によって次にアイテムを選択するエージェントが決まります。

たとえば、4 つのアイテムを Alice と Bob の間で分割する必要があるとします。考えられるピッキング シーケンスは次のとおりです。

• AABB - アリスが 2 つのアイテムを選択し、ボブが残りの 2 つのアイテムを選択します。
• ABAB - アリスがアイテムを 1 つ選び、次にボブがアイテムを 1 つ選び、次にアリスが再び選び、次にボブが再び選びます。これはボブがより良いアイテムを手に入れるチャンスが増えるため、AABB よりも「公平」です。
• ABBA - アリスがアイテムを 1 つ選び、ボブがアイテムを 2 つ選び、アリスが残りのアイテムを受け取ります。これは直感的に ABAB よりもさらに「公平」です。ABAB ではボブは常にアリスより遅れていますが、ABBA はよりバランスが取れています。^[1]

ピッキングシーケンスは公平な分割プロトコルとしていくつかの利点がある: ^{[2] : 307}

• シンプルさ: エージェントはプロトコルがどのように機能し、各ステップで何をすべきかを簡単に理解できます。最適な項目を選択するだけです。
• プライバシー: エージェントは、評価関数全体やランキング全体を公開する必要はありません。各ステップでどのアイテムが自分にとって最適であるかを明らかにするだけで済みます。
• 通信の複雑さが低い: 必要なレポートはm個だけで、各レポートには 1 からmまでの数字が含まれるため、全体の複雑さは になります。${\displaystyle \Theta (m\log {m})}$

ピッキング順序はどのように選択されるべきでしょうか？BouveretとLang ^[3]は、次のような仮定のもとでこの問題を研究しています。

• 各エージェントは加法的効用関数を持ちます（これはアイテムが独立した財であることを意味します）。
• エージェントはアイテムに対して異なるランキングを持つ場合がありますが、ランキングを金銭的価値にマッピングする共通のスコアリング関数があります (たとえば、各エージェントにとって最も優れたアイテムは x ドルの価値があり、2 番目に優れたアイテムは y ドルの価値があるなど)。
• 割り当て者はエージェントのランキングを知りませんが、すべてのランキングは与えられた確率分布からランダムに抽出されたものであることを知っているのです。
• 配分者の目標は、何らかの社会福祉関数の期待値を最大化することです。

これらは、さまざまな設定で期待される功利主義的福祉 (効用の合計) または期待される平等主義的福祉 (最小効用)を最大化する選択シーケンスを示しています。

カリノフスキーら^[4]は、ボルダスコアリング関数を持つ2つのエージェントが存在し、それぞれの順位が等確率である場合、「ラウンドロビン」シーケンス（ABABAB...）が最大の期待効用合計を達成することを示している。^{[2] ：308}

ブラムスとカプラン^[5]は、政党間の閣僚の割り当て問題を研究している。政党連合があり、各政党は議会で異なる数の議席を持っている。大政党にはより多くの省庁やより権威のある省庁が割り当てられるべきである。これは、異なる権利を持つ公平な項目割り当ての特別なケースである。この問題の考えられる解決策は、異なる権利に基づいて選択順序を決定し、各政党が順番に省庁を選択できるようにすることである。このような解決策は、北アイルランド、デンマーク、欧州議会で使用されている。^[6]

Brams は、各エージェントがアイテムに対して厳密な順序付けを持ち、アイテムの束に対して応答的な好みを持っていると仮定しています。これは、選択シーケンスの各時点で、エージェントにとって「最良のアイテム」である 1 つのアイテムが残っていることを意味します。エージェントが各時点で最良のアイテムを選択した場合、そのエージェントは誠実(正直) であると呼ばれます。エージェントが互いの好みに関する完全な情報を持っている場合 (当事者間では一般的です)、正直に選択することは合理的ではない可能性があります。洗練された(戦略的な) 選択を行う方がよい場合があります。したがって、選択シーケンスはシーケンシャル ゲームを誘導し、そのサブゲーム完全な均衡を分析することは興味深いことです。いくつかの結果が証明されています。

• エージェントが 2 人いる場合、誠実な選択と戦略的な選択の両方がパレート効率的な割り当てにつながります。さらに、ゲームは次の意味で単調です。シーケンス内の自分の位置の 1 つ以上が改善されると、エージェントは常に有利になります (たとえば、アリスはシーケンス ABBA の方が BABA よりも有利になります)。3 人以上のエージェントでも、誠実な選択を行う限り、両方の特性が当てはまります。
• 戦略的な選択を行うエージェントが 3 人以上いる場合、選択シーケンスによって非効率的な割り当てが発生する可能性があります (つまり、サブゲーム完全な均衡はパレート効率的ではない可能性があります)。
• 3人以上のエージェントが戦略的選択を行う場合、ゲームは非単調になる可能性があり、つまり、エージェントはシーケンスの早い段階で選択することで結果が悪くなる可能性があります。^{[5] ：210–212}
• 2 人のエージェントの場合、選択シーケンスの単純な変更が存在します。これは真実のメカニズムです。つまり、アイテムを真実に選択することが支配的な戦略です。したがって、パレート最適であるサブゲーム完全な均衡が存在し、ゲームは単調です。

エージェントの異なる権利を考慮すると、公平な選出順序はどのようなものになるだろうか。ブラムス^{[5] :202–206は}、各州の議席配分に使用されるものと同様の除数法を使用することを提案している。最も一般的に使用される2つの方法は、ダニエル・ウェブスターとトーマス・ジェファーソンによって提案されたものである。両方の方法は同じ方法で始まる。

• 除数（権利の合計をアイテムの数で割った値）を計算します（たとえば、すべての権利の合計が 201 で、共有するアイテムが 15 個ある場合、除数は 201/15 になります）。
• 割り当てを計算します。割り当てとは、各エージェントが権利を持つアイテムの数の小数です。これは、権利を除数で割ったものです (たとえば、201 個中 10 個の権利を持つエージェントの場合、割り当ては 10*15/201 ~ 0.75 個のアイテムになります)。

ピッキングシーケンスは、競争均衡と呼ばれる強力な公平性と効率性の条件を満たす割り当てを見つけるために使用できます。^[7]

ラウンドロビン項目割り当てプロトコルは、シーケンスが循環的であるピッキングシーケンスの特殊なケースです: 1、2、...、n、1、2、...、n、...

校庭ゲームでは、多くの場合「チーム」を選択する必要があります。「ABBA」選択を使用する場合、「A」チームは「ファースト ピック」を宣言し、B チームは「セカンド ツー」を宣言します。伝統的な子供のゲームのリスト