破産問題

破産問題[ ^1]は債権問題^[2]とも呼ばれ、同質の分割可能な財（お金など）を異なる債権を持つ人々に分配する問題である。焦点は、金額がすべての債権を満たすのに不十分な場合である。

標準的な応用例は、破産して清算される予定の会社です。会社は 債権者ごとに異なる金額の借金を抱えていますが、会社の資産の合計価値は負債の合計よりも小さくなっています。問題は、少ない既存のお金を債権者間でどのように分配するかです。

もう 1 つの応用としては、特に遺産が故人の義務をすべて果たせない場合に、 複数の相続人の間で遺産を分割することが挙げられます。

3番目の応用^[2]は、課税評価です。請求者を納税者、請求額を所得、基金を課税後総所得とみなすことができます。課税後総所得の配分を決定することは、納税額の配分を決定することと同じです。

分割可能な金額は (= 財産または基金) で示されます。請求者はn人います。各請求者i はで示される請求権を持ちます。 ${\displaystyle E}$ ${\displaystyle c_{i}}$

つまり、請求総額は（弱く）財産総額よりも大きい と仮定します。${\displaystyle \sum _{i=1}^{n}c_{i}\geq E}$

分割規則は、すべてのiに対してとなるようなベクトルに問題インスタンスをマッピングする関数です。つまり、各請求者は最大でその請求を受け取り、割り当ての合計は正確に財産Eになります。 ${\displaystyle (c_{1},\ldots ,c_{n},E)}$${\displaystyle (x_{1},\ldots,x_{n})}$${\displaystyle \sum _{i=1}^{n}x_{i}=E}$${\displaystyle 0\leq x_{i}\leq c_{i}}$

請求総額が遺産総額よりも小さくなる可能性がある一般的なバリエーションがあります。これらの一般的なバリエーションでは、は想定されておらず、必要ありません。 ${\displaystyle \sum _{i=1}^{n}c_{i}\geq E}$${\displaystyle 0\leq x_{i}\leq c_{i}}$

現実的な破産問題にヒントを得たもう 1 つの一般化は、請求者間に外生的な優先順位を追加することです。この優先順位は、請求者が同一の請求権を持つ場合でも異なる場合があります。この問題は、優先順位付き請求問題と呼ばれます。別のバリエーションは、重み付き請求問題と呼ばれます。

実際には破産問題を解決するための様々なルールが存在する。^[1]

• 比例ルールでは、各代理人の請求額に応じて財産を比例的に分割します。正式には、各請求者i はを受け取ります。ここで、 r はとなるように選択された定数です。比例ルールの結果を と表します。${\displaystyle r\cdot c_{i}}$${\displaystyle \sum _{i=1}^{n}r\cdot c_{i}=E}$${\displaystyle PROP(c_{1},\ldots,c_{n};E)}$
• 切り捨て請求比例ルールと呼ばれる変形があり、 Eより大きい請求はすべてEに切り捨てられ、比例ルールが有効化されます。つまり、 に等しくなります。ここでです。^[2]${\displaystyle PROP(c_{1}',\ldots ,c_{n}',E)}$${\displaystyle c'_{i}:=\min(c_{i},E)}$
• 調整された比例ルール^[3]は、まず各エージェントiに、他のエージェントが請求していない金額である最小限の権利を与えます。正式には、です。は を意味することに注意してください。次に、エージェントiの請求額を に、財産額を に修正します。 であることに注意してください。最後に、切り捨て請求比例ルールをアクティブにします。つまり、 を返します。ここで、です。請求者が 2 人の場合、修正された請求額は常に等しいため、残りは均等に分割されます。請求者が 3 人以上の場合、修正された請求額は異なる場合があります。${\displaystyle m_{i}:=\max(0,E-\sum _{j\neq i}c_{j})}$${\displaystyle \sum _{i=1}^{n}c_{i}\geq E}$${\displaystyle m_{i}\leq c_{i}}$${\displaystyle c'_{i}:=c_{i}-m_{i}}$${\displaystyle E':=E-\sum _{i}m_{i}}$${\displaystyle E'\geq 0}$${\displaystyle TPROP(c_{1},\ldots ,c_{n},E')=PROP(c_{1}'',\ldots ,c_{n}'',E')}$${\displaystyle c''_{i}:=\min(c'_{i},E')}$
• 制約付き平等分配ルールは、財産を代理人間で均等に分配し、誰も請求額以上の金額を受け取れないようにする。正式には、各請求者i はを受け取り、ここでr はとなるように選ばれた定数である。このルールの結果を と表記する。課税の文脈では、これは平準化税として知られている。^[2]${\displaystyle \min(c_{i},r)}$${\displaystyle \sum _{i=1}^{n}\min(c_{i},r)=E}$${\displaystyle CEA(c_{1},\ldots ,c_{n};E)}$
• 制約付き均等損失ルールは、総請求額と遺産の差額を均等に分割し、どの代理人もマイナスの譲渡に陥らないようにします。正式には、各請求者i はを受け取ります。ここで、 r はとなるように選択されます。このルールはマイモニデスによって議論されました。^[4]課税の文脈では、人頭税として知られています。${\displaystyle \max(0,c_{i}-r)}$${\displaystyle \sum _{i=1}^{n}\max(0,c_{i}-r)=E}$
• 争議中の衣服のルール(タルムード ルールとも呼ばれる)では、遺産が請求総額の半分より小さい場合は、請求額の半分に対して CEA ルールを適用します。それ以外の場合は、各請求者に請求額の半分を与え、CEL ルールを適用します。正式には、の場合、 であり、それ以外の場合は、 です 。${\displaystyle 2E<\sum _{i=1}^{n}c_{i}}$${\displaystyle CG(c_{1},\ldots,c_{n};E)=CEA(c_{1}/2,\ldots,c_{n}/2;E)}$${\displaystyle CG(c_{1},\ldots ,c_{n};E)=c/2+CEL(c_{1}/2,\ldots ,c_{n}/2;E-\sum _{j}(c_{j}/2))}$
• 以下の規則はピニレス^[2]に由来するとされている。^{[5]請求額の合計が2} Eより大きい場合、請求額の半分にCEA規則を適用し、 を返す 。それ以外の場合は、各エージェントに請求額の半分を与え、残りにCEAを適用し、 を返す。${\displaystyle CEA(c_{1}/2,\ldots ,c_{n}/2;E)}$${\displaystyle (c_{1}/2,\ldots ,c_{n}/2)+CEA(c_{1}/2,\ldots ,c_{n}/2;E-\sum _{j=1}^{n}c_{j}/2)}$
• 制約付き平等主義ルール^[6]は次のように機能します。請求の合計が2 Eより大きい場合、請求の半分に対してCEAルールを実行し、各請求者にi を与えます。それ以外の場合は、各エージェントに i を与えます。どちらの場合も、r は割り当ての合計がEと等しくなるように選択された定数です。${\displaystyle \min(c_{i}/2,r)}$${\displaystyle \max(c_{i}/2,\min(c_{i},r))}$
• ランダム到着ルールは次のように機能します。請求者が1人ずつ到着するとします。各請求者は、利用可能な金額まで、請求額のすべてを受け取ります。このルールは、到着順序が一様にランダムに選択された場合に結果として得られる割り当てベクトルの平均を返します。^[7]正式には：

${\displaystyle RA(c_{1},\ldots ,c_{n};E)={\frac {1}{n!}}\sum _{\pi \in {\text{順列}}}\min(c_{i},\max(0,E-\sum _{\pi (j)<\pi (i)}c_{j}))}$。

各破産問題を協力交渉問題に関連付け、交渉ルールを使用して破産問題を解決すること が可能となります。その場合、次のようになります。

• ナッシュ交渉解は制約付き平等報酬ルールに対応する。^[8]
• 辞書的平等主義交渉解決法は、制約付き平等報酬ルールにも対応している。^[2]
• 請求額に等しい重みを持つ加重ナッシュ交渉解は比例ルールに対応する。^[8]
• カライ・スモロジンスキーの交渉解決法は、切り捨て請求比例ルールに対応している。^[8]
• 拡張均等損失交渉ソリューションは、切り捨て請求制約均等損失ルールに対応する。^[2]

各破産問題を協力ゲームに関連付けることが可能であり、そのゲームでは各連合の価値は最小限の権利、つまり他のすべての請求者が全額の請求権を獲得した場合にこの連合が確保できる金額（つまり、この連合が裁判所に行かずに獲得できる金額）となる。正式には、請求者の各サブセットSの価値は である。結果として得られるゲームは凸 であるため^[4]、そのコアは空ではない。協力ゲームのソリューション コンセプトを使用して、対応する破産問題を解くことができる。切り捨てられた請求権のみに依存するすべての分割ルールは、協力ゲームのソリューションに対応する。特に、 ${\displaystyle v(S):=\max \left(0,~E-\sum _{j\not \in S}c_{j}\right)}$

• シャプレー値はランダム到着規則に対応する。^[7]
• 前核小体はタルムードの規則に対応する。^[4]
• ダッタ・レイ解は制約付き均等報酬ルールに対応する。^[9]
• タウ値の解は調整された比例則に対応する。^[3]

^{請求権問題を協力ゲーム[10]}と関連付ける別の方法は、その最大権利、つまり他のすべての請求者が請求権を放棄した場合にこの連合が確保できる金額である。 ${\displaystyle v(S):=\min \left(E,\sum _{j\in S}c_{j}\right)}$

ほとんどの場合、除算規則は次のような基本的な性質を満たすことが求められる。^[2]

• 実現可能性: 割り当ての合計は最大で総資産になります。${\displaystyle \sum _{i=1}^{n}x_{i}\leq E}$
• 効率性: 実現可能性よりも強力: 割り当ての合計は総資産に等しくなります。${\displaystyle \sum _{i=1}^{n}x_{i}=E}$
• 非負性: 各請求者は負でない金額を受け取る必要があります。${\displaystyle \forall i:x_{i}\geq 0}$
• 請求の制限性: 各請求者は最大でも自分の請求額を受け取る必要があります。${\displaystyle \forall i:x_{i}\leq c_{i}}$
• 最小限の権利: 非負性よりも強い: 各請求者は少なくとも最小限の権利を得るべきであり、これは他のすべてのエージェントが完全な請求権を得た場合に残る権利です。 ${\displaystyle \forall i:x_{i}\geq m_{i},{\text{ where }}m_{i}:=\max(0,E-\sum _{j\neq i}c_{j})}$
  • 効率性、非負性、および請求の制限性は、最小限の権利を意味することに注意してください。
• 同格者の平等な扱い (ETE) : 同一の請求権を持つ 2 人の請求者は同一の割り当てを受ける必要があります。優先順位を持つ請求権の一般化された問題では、各優先順位クラスのエージェントに対して同格者の平等な扱いが要求されますが、異なる優先順位クラスのエージェントに対しては必要ありません。${\displaystyle c_{i}=c_{j}\implies x_{i}=x_{j}}$
• 同等のグループの平等な扱い: ETE よりも強力: 請求総額が同じ 2 つの請求者サブセットには、同じ合計割り当てが与えられる必要があります。
• 匿名性: ETE よりも強力: 請求のベクトルを並べ替えると、割り当てのベクトルもそれに応じて並べ替えられます。
• 順序保存: ETE よりも強力: 弱く高い請求権を持つエージェントは弱く多くを獲得し、弱く多くを失うはず: 。${\displaystyle c_{i}\geq c_{j}\implies (x_{i}\geq x_{j}{\text{ and }}c_{i}-x_{i}\geq c_{j}-x_{j})}$
• グループ順序保存: グループ ETE と順序保存の両方よりも強力です。エージェントの 2 つのサブセットごとに順序保存が必要です。

• 権利（公平な分配）
• 異なる権利を持つ比例ケーキカット
• 戦略的破産問題

• 破産問題およびその他関連問題における加法ルール
• 破産問題：協力的な交渉アプローチ