ラウンドロビンアイテム割り当て

ラウンドロビンは、公平なアイテム割り当ての手順です。複数の分割不可能なアイテムを複数の人に割り当てるために使用できます。割り当ては「ほぼ」嫉妬のない状態になります。各エージェントは、他のバンドルから最大で 1 つのアイテムが削除された場合、自分が受け取ったバンドルが他のエージェントのバンドルと少なくとも同等に優れていると信じます。スポーツでは、ラウンドロビン手順はドラフトと呼ばれます。

割り当てるオブジェクトがm個あり、これらのオブジェクトに対して同等の権利を持つ人 (「エージェント」) がn人います。各人はオブジェクトに対して異なる好みを持っています。エージェントの好みは、値のベクトル (各オブジェクトの値) によって与えられます。エージェントにとってのバンドルの値は、バンドル内のオブジェクトの値の合計であると想定されます (言い換えると、エージェントの評価は、オブジェクトのセットに対する加法的なセット関数です)。

プロトコルは次のように進行します。

1. 人々に 1 から までの任意の番号を付けます 。${\displaystyle n}$
2. 割り当てられていないオブジェクトがある場合:
   • 1 人ずつ、割り当てられていないオブジェクトを 1 つ選択してもらいます。${\displaystyle n}$

各人が順番に、残りのオブジェクトの中から最も価値の高い未割り当てのオブジェクトを選択するものと想定します。

ラウンドロビン プロトコルでは、各エージェントが他のアイテムを取得することを知らなくても「最適なアイテム」を選択する必要があるため、加法性が求められます。評価の加法性により、常に「最適なアイテム」(最も高い価値を持つアイテム) が存在することが保証されます。言い換えると、アイテムは独立した商品であると想定されます。加法性の要件は、弱い加法性に緩和できます。

ラウンドロビン プロトコルは実行が非常に簡単で、必要なのはmステップだけです。各エージェントは、事前にオブジェクトの降順を値の順に並べ替え (エージェントごとに時間がかかります)、時間内にオブジェクトを選択できます。 ${\displaystyle O(m{\text{log}}m)}$${\displaystyle O(1)}$

最終的な割り当てはEF1です。つまり、 と のすべてのペアについて、のバンドルから最大 1 つのオブジェクトが削除された場合、 はを羨まないということです。 ${\displaystyle i}$${\displaystyle j}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$

証明: ^[1]すべてのエージェント について、エージェントによる選択をサブシーケンスに分割します。最初のサブシーケンスはエージェント 1 で始まり、エージェント で終わります。後者のサブシーケンスは で始まり、 で終わります。後者のサブシーケンスでは、エージェント が最初に選択するため、エージェントは最適なアイテムを選択でき、他のエージェントを羨むことはありません。エージェントはエージェント のうちの 1 人のみを羨むことができ、その羨望は最初のサブシーケンスで選択したアイテムからのみ生じます。このアイテムが削除された場合、エージェントは羨ましがりません。${\displaystyle i}$${\displaystyle i-1}$${\displaystyle i}$${\displaystyle i-1}$${\displaystyle i}$${\displaystyle i}$${\displaystyle 1,...,i-1}$${\displaystyle i}$

さらに、ラウンドロビンは、各エージェントが同じ数のアイテム ( mがnで割り切れる場合はm / n )、またはほぼ同じ数のアイテム ( mがnで割り切れない場合は) を受け取ることを保証します。したがって、各学生が同じ数のコースを受講する必要がある学生にコースの座席を割り当てる場合など、単純なカーディナリティ制約がある状況で役立ちます。

ラウンドロビンはおおよその公平性を保証しますが、結果は非効率的になる可能性があります。簡単な例として、評価が次のとおりであるとします。

ラウンドロビンでは、アリスが最初に選択すると、効用(24,23)と社会福祉47の割り当てが得られます。これは、効用(25,25)の 割り当てによって支配されているため、パレート効率的ではありません。${\displaystyle (zxv,ywu)}$${\displaystyle (yxw,zvu)}$

より高い社会的福祉を達成できる可能性のある代替アルゴリズムは、反復最大重みマッチングアルゴリズムです。^[2]各反復で、ノードがエージェントとアイテム、エッジの重みがエージェントのアイテムに対する価値である二部グラフで最大重みマッチングを見つけます。上記の例では、最初のマッチングは、2番目は、3番目は です。合計割り当ては効用（18,32）で、社会的福祉（- 効用の合計）は 50 で、ラウンドロビン割り当てよりも高くなります。 ${\displaystyle (y,z)}$${\displaystyle (w,x)}$${\displaystyle (u,v)}$${\displaystyle (ywu,zxv)}$

上記の割り当ては効用値(19,36)を持つ(xwv, zyu)によって支配されているため、最大重みマッチングを繰り返してもパレート効率は保証されないことに注意してください。

ラウンドロビンアルゴリズムは、グループ間でアイテムを公平に割り当てるために使用できます。この設定では、各グループのすべてのメンバーが同じバンドルを消費しますが、各グループ内の異なるメンバーはアイテムに対して異なる好みを持つ可能性があります。これにより、各グループが順番にどのアイテムを選択するかをどのように決定するかという問題が生じます。各グループの目標は、そのメンバーのうち「満足している」、つまり割り当てが公平であると感じるメンバーの割合を最大化することであるとします (個人の好みに応じて)。また、エージェントがバイナリ加法評価を持っているとします。つまり、各エージェントは各アイテムを 1 (「承認」) または 0 (「不承認」) のいずれかで評価します。次に、各グループは、重み付け承認投票を使用してどのアイテムを選択するかを決定できます。^[3]

• 各グループメンバーには重みが割り当てられます。メンバーjの重みは特定の関数w ( r _j , s _j ) です。ここで、
  • r _{j は}j が承認する 残りの商品の数です。
  • s _jは、 jに対して選択された公平性基準が満たされるように、 j のグループがまだ取得する必要がある商品 の数です。
• 残りの各項目には重みが割り当てられます。項目gの重みは、 g を承認するエージェントの重みの合計、つまり、j がg を1 と評価するすべてのjのw ( r _j、s _j )の合計です。
• グループは最も重いアイテムを選択します。

結果として得られるアルゴリズムは、RWAV (重み付け承認投票によるラウンドロビン) と呼ばれます。重み関数w ( r , s ) は、次の再帰関係によって定義される補助関数B ( r , s ) に基づいて決定されます。

• ${\displaystyle B(r,s):=1~~{\text{if}}~~s\leq 0;}$

• ${\displaystyle B(r,s):=0~~{\text{if}}~~0<s~{\text{and}}~r<s;}$
• ${\displaystyle B(r,s):=\min {\bigg [}{\frac {1}{2}}[B(r-1,s)+B(r-1,s-1)],B(r-2,s-1){\bigg ]}~~{\text{それ以外の場合}}}$。

直感的には、エージェントの B( r , s ) は、エージェントが最終的な割り当てに満足する確率を表します。s ≤ 0 の場合、定義によりこの確率は 1 です。つまり、エージェントは満足するためにこれ以上の財を必要としません。 0 < sかつr < sの場合、この確率は 0 です。エージェントは、利用可能な財よりも多くの財を必要とするため、満足することはできません。 それ以外の場合、 B( r , s ) は、他のグループがエージェントが望む財を取る場合の B( r -1, s ) と、エージェントのグループがエージェントが望む財を取る場合の B( r -1 , s-1 )の平均です。 項 B( r -2, s -1) は、両方のグループがエージェントが望む財を取る状況を表します。 B( r , s ) が計算されると、重み関数wは次のように定義されます。

${\displaystyle w(r,s):=B(r,s)-B(r-1,s)}$

この重み関数を使用して RWAV を 2 つのグループで実行すると、グループ 1 の幸せなメンバーの割合は少なくとも B( r , s( r )) になり、グループ 2 の幸せなメンバーの割合は少なくとも B( r -1, s( r )) になります。^{[3] : 補題 3.6}関数s ( r ) は公平性基準によって決定されます。たとえば、1-out-of-3 マキシミンシェア公平性の場合、s ( r ) = floor( r /3) です。次の表は、関数Bのいくつかの値を示しており、 B(r-1, floor(r/3)) の値は太字で示されています。

このことから、RWAV アルゴリズムは、両方のグループで、メンバーの少なくとも 75% が割り当てが 3 分の 1 MMS の公平性であると感じることを保証していると結論付けることができます。

1. ラウンドロビンプロトコルは、アイテムが商品（すべてのエージェントによって正に評価される）の場合と雑用（すべてのエージェントによって負に評価される）の場合にEF1を保証します。ただし、商品と雑用が両方ある場合はEF1は保証されません。ラウンドロビンの適応であるダブルラウンドロビンは、商品と雑用が混在していてもEF1を保証します。^[4]

2. エージェントがより複雑なカーディナリティ制約を持つ場合（つまり、アイテムがカテゴリに分割され、アイテムの各カテゴリごとに、各エージェントがこのカテゴリから取得できるアイテムの数に上限がある場合）、ラウンドロビンは失敗する可能性があります。ただし、ラウンドロビンとenvy-graph手順を組み合わせると、EF1であり、カーディナリティ制約を満たす割り当てを見つけるアルゴリズムが得られます。^[5]

3. エージェントが異なる重みを持っている場合（つまり、エージェントが合計アイテムに対して異なる権利を持っている場合）、重み付きラウンドロビンと呼ばれる一般化されたラウンドロビンプロトコルは、アイテムが商品である場合（すべてのエージェントによって正に評価されている）にEF1を保証します^[6] 。また、逆の重み付きラウンドロビンは、アイテムが雑用である場合（すべてのエージェントによって負に評価されている）にEF1を保証します。 ^[7]

ラウンドロビンは、ピッキングシーケンスの特殊なケースです。

ラウンドロビン プロトコルは、公平なアイテム割り当て以外にもさまざまな分野で使用されます。たとえば、 ラウンドロビン スケジューリングやラウンドロビン トーナメントを参照してください。