グループ間の公平な分割

グループ間の公平な分割^[1] (または家族間の公平な分割^[2] ) は、公平な分割問題の一種であり、リソースが個々のエージェント間ではなく、エージェントのグループ間に割り当てられます。分割後、各グループのすべてのメンバーは同じシェアを消費しますが、好みが異なる可能性があります。そのため、同じグループ内の異なるメンバーは、割り当てが公平であるかどうかについて意見が一致しない可能性があります。グループ公平な分割設定の例をいくつか示します。

• 兄弟姉妹が両親からいくつかの家を相続し、それを分割しなければなりません。兄弟姉妹はそれぞれ家族を持っており、どの家がより良いかについて、家族のメンバー間で意見が異なる可能性があります。
• パートナーシップが解消され、その資産はパートナー間で分割される必要があります。パートナーは企業であり、各企業には複数の株主がおり、どの資産がより重要であるかについて意見が一致しない場合があります。
• 大学経営陣は、学部間でいくつかの会議室を割り当てたいと考えています。各学部には数名の教員がおり、どの部屋がより良いかについて意見が分かれています。
• 隣り合う 2 つの国が紛争地域を分割しようとしています。両国の国民は、地域のどの部分がより重要であるかについて意見が異なります。これが国際紛争を解決する上での共通の障害となっています。
• 「エージェントのグループ」は、一人の人間の相反する異なる好みを表すこともあります。行動経済学で観察されるように、人々はしばしば異なる心構えや気分に応じて好みを変えます。 ^[3]このような人々は、それぞれが異なる好みを持つエージェントのグループとして表すことができます。

上記の例はすべて、グループが事前に固定されています。設定によっては、グループをアドホックに決定することもできます。つまり、人々は好みに基づいてグループ化されます。そのような設定の例は次のとおりです。^[4]

• 地元のバスケットボール コートを利用希望者が約 30 人います。各ゲームには 10 人のプレーヤーが参加しますが、どの時間帯がよいかという好みはそれぞれ異なります。時間帯を 3 つに分け、プレーヤーを 3 つのグループに分け、各時間帯にグループを割り当てる必要があります。

比例性や嫉妬のなさなどの一般的な公平性の基準は、単一の選好関係を持つ単一のエージェントの観点から分割を判断します。これらの基準をグループ間の公平な分割に拡張する方法はいくつかあります。

全員一致の公平性には、すべてのグループのすべてのエージェントの目から見て割り当てが公平であるとみなされることが必要です。例:

• 各グループの各エージェントが自分のグループの取り分を合計値の少なくとも 1/ kと評価する場合、その分割は全員一致で比例していると呼ばれます。ここで、 kはグループの数です。
• 各グループのすべてのエージェントが自分のグループのシェアを他のグループのシェアと少なくとも同じくらい評価している場合、その部門は全員一致で嫉妬がない部門と呼ばれます。

全員一致の公平性は強い要件であり、満たされないことがよくあります。

集計の公平性では、各グループに合計、積、算術平均、幾何平均などの特定の集計関数を割り当てます。この集計関数に従って割り当てが公平であるとみなされる必要があります。例:

• 各グループについて、エージェントの値のグループシェアに対する算術平均が合計値の少なくとも 1/ kである場合、その分割は平均比例と呼ばれます。
• 各グループについて、エージェントのグループシェアの価値の積が、他のグループのシェアの価値の積以上である場合、その部門は製品羨望がないと呼ばれます。

民主的な公平性には、各グループにおいて、一定の割合のエージェントが分割が公平であると同意することが必要であり、この割合は少なくとも 1/2 であることが望ましい。このような要件が役立つ可能性がある実際の状況としては、2 つの民主主義国が特定の紛争地域を分割することに合意し、その合意が両国で 国民投票によって承認される必要がある場合が挙げられる。

全会一致の公平性は、総合的公平性と民主的公平性の両方を意味します。総合的公平性と民主的公平性は独立しており、どちらかが他方を意味することはありません。^[2]

パレート効率は、公平性に加えて必要なもう 1 つの重要な基準です。これは通常の方法で定義されます。つまり、少なくとも 1 人のエージェントにとってどの割り当てもより良いものではなく、すべてのエージェントにとって少なくとも同等に良い割り当てもないということです。

公平なケーキカットの文脈では、以下の結果が知られています（ここでkはグループの数、nはすべてのグループに含まれるエージェントの数です）。^[2]

• 全会一致の公平性: 全会一致の比例割り当てと全会一致の嫉妬のない割り当ては常に存在します。ただし、それらは分離されている可能性があり、少なくともn 個 の接続されたコンポーネントが必要になる場合があります。2 つのグループの場合、n個のコンポーネントは常に十分です。k >2 グループの場合、全会一致の比例割り当てには常に O( n log k ) 個のコンポーネントが十分であり、全会一致の嫉妬のない割り当てには常に O( nk ) 個のコンポーネントが十分です。n個のコンポーネントが常に十分であるかどうかは未解決の問題です。
• 集計公平性: 平均比例割り当てと平均羨望フリー割り当ては常に存在し、k 個の連結コンポーネントのみを必要とします (つまり、各グループは連結された部分を取得できます)。ただし、これらはRobertson–Webb クエリ モデルの有限アルゴリズムを使用して見つけることはできません。
• 民主的公平性: 1/2 民主的比例配分と 1/2 民主的嫉妬のない配分は常に存在します。2 つのグループの場合、連結された配分も存在し、多項式時間で見つけることができます。k >2 グループの場合、連結された 1/2 民主的公平配分は存在しない可能性がありますが、必要なコンポーネントの数は全員一致の比例配分の場合よりも少なくなります。
• 公平性と効率性: 比例性の3つの変種は、グループ数に関係なくパレート効率と互換性があります。全員一致の嫉妬のなさは、2つのグループではパレート効率と互換性がありますが、3つ以上のグループでは互換性がありません。1/2民主主義の嫉妬のなさは、2つのグループではパレート効率と互換性がありますが、5つ以上のグループでは互換性がありません。3つのグループと4つのグループで互換性があるかどうかは不明です。^[3]

エージェントを好みに基づいてアドホックにグループ化できる場合、分割問題はより簡単になります。この場合、任意の数のグループと各グループ内の任意の数のエージェントに対して、全員一致の羨望のない接続された割り当てが存在します。^[4]

正確な分割（コンセンサス分割とも呼ばれる）では、 n人のエージェントがいて、すべてのエージェントがすべてのピースに正確に 1/ k の価値を持つようにケーキをk 個のピース​​に分割することが目標です。n ( k -1)の正確な分割は常に存在することが知られています。ただし、 k =2の場合でも、 n回のカットで正確な分割を見つけることは FIXP 困難であり、 n回のカットで近似正確な分割を見つけることはPPA 完全です（詳細については正確な分割を参照してください）。全員一致の比例は、次の意味でコンセンサス分割と同等であることが証明されています。^[2]

• あらゆるnとkについて、k 個のファミリーにグループ化されたn ( k -1)+1 個のエージェント間の全会一致の比例分割の解は、 k個のピース​​を持つn個のエージェント間のコンセンサス分割の解を意味します。特に、全会一致の比例分割には少なくともn -1 個のカット ( n個のコンポーネント) が必要であり、n -1 個のカットを持つ全会一致の比例分割を見つけることは FIXP 困難であり、 n -1 個のカットを持つ近似全会一致の比例分割を見つけることはPPA 困難であることを意味します。
• あらゆるnとkについて、 nエージェントとkピース間の正確な分割の解は、kファミリーにグループ化された n+1 エージェント間の全会一致の比例分割の解を意味します。特に、正確な全会一致の比例分割は ( n -1)( k -1) カットで実行できること、および近似的な全会一致の比例分割を見つけることは PPA 内にあることを意味します。カットの数はk =2 ファミリーの場合はタイトですが、 k >2 の場合はタイトではありません。^[5]

公平なアイテム割り当ての文脈では、次の結果が知られています。

全員一致の近似最大シェア公平性：^[6]

• 2 つのグループがある場合、グループ内のエージェントの数が (1, n -1) または (2,2) または (2,3) である場合にのみ、MMS 公平性の正の乗法近似が保証されます。正の結果は、多項式時間アルゴリズムによって達成できます。それ以外の場合は、正の MMS を持つ少なくとも 1 つのエージェントがすべての割り当てでゼロ値を取得する場合があります。
• 3 つ以上のグループがある場合、 k -1 グループに 1 つのエージェントが含まれると、MMS 公平性への正の乗法近似が達成されます。対照的に、すべてのグループに 2 つのエージェントが含まれ、1 つのグループに少なくとも 5 つのエージェントが含まれる場合、正の近似は不可能です。

全員一致のおおよその嫉妬のなさ：^[7]

• 2つのエージェントグループがあり、2つのグループが2つの加法的な評価を持っている場合、グループサイズが(1,5)または(2,3)であれば全員一致のEF1割り当てが存在するが、グループサイズが(1,6)または(2,4)または(3,3)の場合は存在しない可能性がある。一般に、グループサイズがの場合、EF c割り当ては存在しない可能性がある。2進評価では、EF1はEFXと同等だが、EFX0よりも弱いことに注意する。グループサイズが(1,2)の場合、全員一致のEFX0割り当ては存在しない可能性がある。これは、グループサイズが(1,1)である個々のエージェントの状況とは対照的であり、グループサイズが(1,1)の場合、単調な評価であってもEFX0割り当てが常に存在する。^[8]${\displaystyle ({2c+1 \choose c+1},{2c+1 \choose c+1})}$
  • 特定のインスタンスが満場一致の EF1 割り当てを許可するかどうかを判断するのはNP 困難です。
• 応答的評価（加法的な評価のスーパーセット）を持つエージェントのグループが2つある場合、グループサイズが（1,2）であれば、満場一致のEF1バランスの取れた割り当てが存在します。クネザーグラフに関する特定の推測が正しい場合、グループサイズ（1,4）、（2,3）および任意の単調な評価に対しても、満場一致のEF1バランスの取れた割り当てが存在します。グループサイズが（1,2）の場合、満場一致のEFX割り当ては存在しない可能性があります。
• 任意の単調な評価を持つ任意の数のエージェントを含む2 つのアドホック グループの場合、満場一致の EF1 割り当てが存在します。エージェントのバランスの取れた分割と、満場一致の EF1バランスの取れた商品の割り当ても存在します。加法的な評価を使用しても、EF1 を EFX に強化することはできません。
• 任意の数のエージェントが加法的な評価を行うk 個のアドホック グループの場合、全員一致で PROP*1 の割り当てが存在します。
• n 個のエージェントを任意にk 個のグループに分割した場合、 c 個のアイテムまで嫉妬のない割り当てが常に存在します。 c個のアイテムまでの比例についても同様です。合意分割の場合、境界は です。グループの数が一定の場合、すべての境界は漸近的に厳密です。証明には矛盾理論を使用します。^[9]${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k^{3}}})}$${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k}})}$

全員一致で高い確率で嫉妬心がない：^[10]

• すべてのkグループに同じ数のエージェントが含まれ、その評価がランダムに抽出される場合、財の数が であれば、高い確率で羨望のない割り当てが存在し、効用の合計を最大化する貪欲アルゴリズムによって達成できます。 ${\displaystyle \Omega (n\log n)}$
  • 結果は、サイズの異なる2 つのグループに拡張できます。
  • 高い確率でほぼ嫉妬のない割り当てを達成する真実のメカニズムも存在します。
• 商品の数がn未満の場合、高い確率で、羨望のない割り当ては存在しません。

民主的公平性：^[11]

• 2 つのグループがバイナリ加法的評価(エージェントの数は任意) である場合、常に 1/2 民主的な 1 個以外の羨望のない割り当てが存在します。定数cに対してc個以外の羨望のない割り当てを許可する場合でも、定数 1/2 は厳密です。同じことがc個以外の比例についても当てはまります。各グループのエージェントの 1/2 以上に保証できる別の公平性の概念は、順序最大シェア近似です。すべての整数cに対して、 c 個中 1 個の -民主的なMMS 公平割り当てが存在します。これらの割り当ては、各グループ内で加重承認投票を行うラウンドロビン項目割り当てのバリアントを使用して効率的に見つけることができます。最良のc個の項目のうち 1 個を保証できるエージェントの割合の上限( c 個中 1 個のMMS よりも弱い特性) は です。の場合、1-out-of-best- c割り当ての下限は1/2 から 3/5 に改善できますが、上限の 3/4 が常に達成できるかどうかは未解決の問題です。 ${\displaystyle (1-1/2^{c-1})}$${\displaystyle (1-1/2^{c})}$${\displaystyle c=2}$
  • 特定のインスタンスが各エージェントに正の効用を与える割り当てを許可するかどうかを判断することはNP 困難です。
• 一般的な単調な評価を持つ 2 つのグループの場合、1/2 民主的な羨望のない例外 1 の割り当てが常に存在し、効率的なアルゴリズムによって見つけることができます。
• 2 項加法評価を持つ 3 つ以上のグループの場合、1/ k民主的な羨望のない (1 を除く) 割り当てが常に存在します。一般的な単調評価では、1/ k民主的な羨望のない (2 を除く) 割り当てが常に存在します。係数 1/ k は、任意の定数cに対して、羨望のない ( cを除く) 割り当てに対して厳密です。羨望のない状態が比例または最大シェアに緩和されると、多項式時間アルゴリズムを使用して同様の保証を実現できます。加法評価を持つグループの場合、ラウンドロビン項目割り当てのバリアントを使用して、1/3 民主的な 1 から最良k の割り当てを見つけることができます。

家賃の調和（羨望のない部屋と家賃の分配）の文脈では、次のような結果が知られています。 ^[12]

• 全員一致の嫉妬のなさ（論文では強い嫉妬のなさと呼ぶ）は、費用分担ポリシーが均等または比例の場合には存在しないかもしれないが、費用分担が自由なポリシーでは必ず存在する。さらに、費用分担が自由な場合に、総家賃を最大化する全員一致の嫉妬のなさの割り当ては、多項式時間で見つけることができる。
  • アドホックグループでは、費用を平等に分担するポリシーがあっても、全員一致で嫉妬がない状態が存在します。
• 平均的羨望のなさ（論文では総計的羨望のなさと呼ぶ）は、費用分担ポリシーが平等、比例、または無料である場合に常に存在します。

グループ間での公平な分割の実際的な応用は、定員が限られている公園やその他の体験のチケットを分割することです。多くの場合、チケットはランダムに分割されます。人々が単独で来場する場合、すべての候補者の間で単純な均一ランダム抽選を行うのが公平な解決策です。しかし、人々は家族や友人グループで来場し、一緒に入場したいと考えることがよくあります。これにより、抽選を正確にどのように設計するかについてさまざまな考慮事項が生じます。次の結果がわかっています。

• グループのメンバー全員が事前に特定されている設定では、グループ抽選メカニズムはグループを均一にランダムに順序付けし、空き容量がある限り順番に処理します。この自然なメカニズムは不公平で非効率的である可能性があり、より優れた代替手段がいくつかあります。^[13]
• エージェントがグループのメンバーを特定せずに複数のチケットをリクエストできる場合、個別抽選メカニズムはエージェントを一様にランダムに順序付けし、空き容量がある限り各エージェントのリクエストに付与します。この一般的なメカニズムは、不公平で非効率的な結果をもたらす可能性があります。加重個別抽選は、処理順序がリクエストの少ないエージェントに有利になるように偏向される代替メカニズムです。これはほぼ公平でほぼ効率的です。^[13]
• 反復確率最大化アルゴリズムは、最小の効用を最大化する宝くじを見つけます（平等主義ルールとレキシミン順序に基づく）。これはグループ戦略不可能であり、最大利用率の1/2係数近似を達成します。また、パレート効率的で、嫉妬がなく、匿名です。その特性は、1つの特性を損なうことなく別の特性を改善することは不可能であるという意味で最大です。^[14]

• 集団の嫉妬のなさは、個々のエージェント間の公平な分配に関する公平性の基準です。個々のエージェントがそれぞれ自分の私的取り分を得た後、どのエージェント連合も同じ規模の別の連合を嫉妬しないことを意味します。
• クラブ財は、単一のグループ (「クラブ」) のすべてのメンバーによって同時に消費されるが、他のグループのメンバーからは除外されるリソースです。グループ公平分割問題では、割り当てられたすべての財は、割り当てられたグループ内のクラブ財です。
• 同意できるサブセットとは、特定のグループ内のすべての人々によって、その補完項目と同等以上であると見なされる項目のサブセットです。