グループ間の公平な分配

グループ間^{[ 1 ]}（または家族間^{[ 2 ]} ）の公平な分配は、資源を個々のエージェント間ではなく、エージェントのグループ間で分配する公平な分配問題の一種です。分配後、各グループのすべてのメンバーは同じ割合の資源を消費しますが、好みが異なる可能性があります。そのため、同じグループ内の異なるメンバー間で、分配が公平かどうかについて意見が分かれる可能性があります。グループ間の公平な分配設定の例をいくつか挙げます。

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

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

• 約30人が地元のバスケットボールコートを利用したいと考えている。各試合には10人の選手が参加し、それぞれ都合の良い時間帯が異なる。そこで、1日の時間帯を3つの時間帯に分け、選手を3つのグループに分け、各グループにそれぞれの時間帯を割り当てる必要がある。

比例性や羨望のなさといった一般的な公平性の基準は、単一の主体と単一の選好関係の観点から分配を判断する。これらの基準をグループ間の公平な分配に拡張する方法はいくつか存在する。

全会一致の公平性とは、すべてのグループのすべての関係者の目から見て、その配分が公平であるとみなされることを要求する。例えば：

• 分割は、各グループのすべてのエージェントが、自分のグループの取り分を総価値の少なくとも 1/ kと評価する場合、全会一致比例分割と呼ばれます。ここで、 kはグループの数です。
• 分割は、すべてのグループ内のすべての主体が、自分のグループの取り分を他のどのグループの取り分と同等以上と評価する場合に、満場一致で羨望のない分割と呼ばれる。

全員一致の公平性は強い要件であり、多くの場合、満たすことはできない。

集計的公平性とは、各グループに特定の集計関数（例えば、合計、積、算術平均、幾何平均など）を割り当てることです。そして、この集計関数に従って配分が公平であるとみなされることを要求します。例えば、次のようになります。

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

民主的な公平性を実現するには、各グループにおいて、一定の割合の参加者がその分割が公平であると同意する必要があり、この割合は少なくとも1/2以上であることが望ましい。このような要件が実際に役立つ例としては、2つの民主主義国家が係争地の分割に合意し、その合意が両国における国民投票によって承認される場合などが挙げられる。

全会一致の公平性は、集合的公平性と民主的公平性の両方を意味する。集合的公平性と民主的公平性は独立しており、どちらか一方が他方を意味するわけではない。^{[ 2 ]}

パレート効率性は、公平性に加えて求められるもう一つの重要な基準です。これは、一般的な定義に従って、少なくとも1人の個人にとってより良い配分はなく、かつすべての個人にとって少なくとも同等に良い配分がない状態を指します。

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

• 全員一致の公平性：全員一致の比例配分と全員一致の羨望のない配分は常に存在します。ただし、それらは連結していない可能性があり、少なくともn個の連結成分が必要になる場合があります。2 つのグループの場合、n個の成分は常に十分です。k > 2 つのグループの場合、全員一致の比例配分には常に O( n log k ) 個の成分が十分であり、全員一致の羨望のない配分には常に O( nk ) 個の成分が十分です。n 個の成分が常に十分であるかどうかは未解決の問題です。
• 集計的公平性：平均比例配分と平均羨望フリー配分は常に存在し、k個の連結成分のみを必要とする（つまり、各グループが連結された部分を受け取る可能性がある）。しかし、ロバートソン・ウェッブのクエリモデルでは、有限アルゴリズムを使用してこれらを見つけることはできない。
• 民主的公平性：1/2民主的比例配分と1/2民主的羨望フリー配分は常に存在する。2つのグループの場合、連結した配分も存在し、それらは多項式時間で見つけることができる。k > 2のグループの場合、連結した1/2民主的公平配分は存在しない可能性があるが、必要な構成要素の数は全会一致比例配分の場合よりも少ない。
• 公平性と効率性：比例性の3つのバリアントはすべて、任意の数のグループに対してパレート効率性と両立します。全会一致の羨望フリー性は2つのグループに対してはパレート効率性と両立しますが、3つ以上のグループに対しては両立しません。1/2民主主義の羨望フリー性は2つのグループに対してはパレート効率性と両立しますが、5つ以上のグループに対しては両立しません。3つまたは4つのグループに対して両立するかどうかは未解決です。^{[ 3 ]}

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

公平なアイテム配分という観点から、以下の結果が知られています。

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

• グループが2つある場合、MMS公平性に対する正の乗法近似が保証されるのは、グループ内のエージェント数が(1, n -1)または(2,2)または(2,3)の場合に限られます。正の結果は多項式時間アルゴリズムで達成可能です。それ以外のすべての場合において、MMSが正であるエージェントのうち少なくとも1人が、すべての割り当てでゼロ値を取得するケースが存在します。
• グループが3つ以上ある場合、 k -1個のグループに1つのエージェントが含まれていると、MMS公平性に対する正の乗法近似が得られます。一方、すべてのグループに2つのエージェントが含まれており、かつ1つのグループに少なくとも5つのエージェントが含まれている場合は、正の近似は不可能です。
• マキシミンシェアの順序近似に関する結果はより肯定的である。 ^{[ 7 ]}

ほぼ全員一致の羨望のなさ：^{[ 8 ]}

• 2 つのエージェントグループがバイナリ加算評価を持つ場合、グループサイズが (1,5) または (2,3) であれば、全員一致の EF1 割り当てが存在します。しかし、グループサイズが (1,6) または (2,4) または (3,3) であれば、存在しない可能性があります。一般に、グループサイズが${\displaystyle ({2c+1 \choose c+1},{2c+1 \choose c+1})}$バイナリ評価の場合、EF1 は EFX と同等ですが、EFX0 より弱いことに注意してください。グループサイズが (1,2) の場合、全員一致の EFX0 割り当ては存在しない可能性があります。これは、個々のエージェントの場合、つまりグループサイズが (1,1) の場合とは対照的です。この場合、単調評価であっても、EFX0 割り当ては常に存在します。^{[ 9 ]}
  • 与えられたインスタンスが全員一致の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 個のアイテムまで羨望のない割り当てが常に存在し、${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k^{3}}})}$比例性については、 c項目まで同様です。合意による分割の場合、境界は次のようになります。${\displaystyle O({\sqrt {n}})\geq c\geq \Omega ({\sqrt {n/k}})}$グループの数が一定の場合、すべての境界は漸近的にタイトになります。証明には不一致理論を使用します。^{[ 10 ]}

全員一致で高い確率で羨望がない：^{[ 11 ]}

• すべてのkグループが同じ数のエージェントを含み、それらの評価がランダムに抽出される場合、商品の数が であれば、羨望のない配分が高確率で存在する。${\displaystyle \Omega (n\log n)}$そして、効用の合計を最大化する 貪欲アルゴリズムによって達成することができる。
  • この結果は、規模の異なる2つのグループにも適用できる。
  • また、高い確率でほぼ羨望のない配分を実現する、真実に基づいたメカニズムも存在する。
• 商品の数がn未満の場合、高い確率で羨望のない配分は存在しない。

民主主義の公平性：^{[ 12 ]}

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

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

• 費用分担方針が均等または比例の場合、全員一致の羨望フリー状態（本論文では「強い羨望フリー状態」と呼ぶ）は存在しない可能性があるが、費用分担方針が自由な場合は常に存在する。さらに、費用分担が自由な場合において、総賃料を最大化する全員一致の羨望フリーな配分は、多項式時間で見つけることができる。
  • 臨時のグループでは、費用分担が平等な方針であっても、全員一致で嫉妬心のない状態が保たれる。
• 平均的な羨望のなさ（論文では集計された羨望のなさと呼ばれる）は、費用分担の方針が均等、比例、または無料の場合に必ず存在する。

グループ間での公平な分配の実際的な応用例として、定員制の公園やその他の体験施設のチケットの分配が挙げられます。多くの場合、チケットはランダムに分配されます。個人で来場する場合は、すべての応募者の中から単純な一様ランダム抽選を行うのが公平な解決策となります。しかし、家族や友人グループで来場し、一緒に入場したいと考える人も多くいます。そのため、抽選をどのように設計するかについて、さまざまな検討が必要となります。以下の結果が知られています。

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

• 集団的羨望の排除は、個々の主体間の公平な分配のための公平性基準である。これは、各主体が自身の私的分配分を受け取った後、いかなる主体連合も、同じ規模の他の主体連合を羨まないということを意味する。
• クラブ財とは、単一のグループ（「クラブ」）内のすべてのメンバーが同時に消費する資源であり、他のグループのメンバーは消費しない資源である。グループ間の公平な分配問題では、分配されるすべての財は、分配先のグループにおいてクラブ財となる。
• 好ましい部分集合とは、ある集団に属するすべての人々が、少なくともその補集合と同等に優れていると考える項目の部分集合のことである。

• 共有グループ間でのパイの分配。^{[ 16 ]}