レンタルハーモニー

家賃の調和^{[1] [2]}は、分割不可能な項目と固定された金銭的費用を同時に分割しなければならない公平な分割問題の一種である。同居問題^{[3] [4]}や部屋割り家賃分割^{[5] [6]}は、同じ問題の別名である。^{[7] [8] : 305–328}

典型的な状況では、パートナーが一緒に 1 部屋の家を借り、家主が費用を固定します。各ハウスメイトの好みはそれぞれ異なります。1 人は広い部屋を好み、もう 1 人は幹線道路が見える部屋を好むなどです。次の 2 つの問題を同時に解決する必要があります。 ${\displaystyle n}$${\displaystyle n}$

• （a）各パートナーに部屋を割り当て、
• （b）支払額の合計が固定費と等しくなるように、各パートナーが支払うべき金額を決定します。

割り当てで満たしたいプロパティがいくつかあります。

• 非負性 (NN) : すべての価格は 0 以上である必要があります。部屋を取得するためにパートナーに支払いが行われるべきではありません。
• 羨望のなさ(EF) : 価格設定方式 (部屋への家賃の割り当て) が与えられた場合、部屋 + 家賃の区画が他のすべての区画よりもわずかに優れているとパートナーが考える場合、パートナーは特定の部屋を好むと言います。EF は、すべてのパートナーが割り当てられた部屋を好むことを意味します。つまり、どのパートナーも、その部屋に割り当てられた家賃で別の部屋を借りたいとは思わないということです。
• パレート効率(PE) : 他のどのパートナーの部屋への割り当ても、すべてのパートナーにとって弱く優れており、少なくとも 1 人のパートナーにとって厳密に優れていることはありません (価格ベクトルが与えられている場合)。

嫉妬がないということは、パレート効率を意味します。証明:矛盾により、同じ価格ベクトルを持つ、少なくとも 1 人のパートナーにとって確実により良い代替割り当てが存在すると仮定します。この場合、現在の割り当てでは、そのパートナーは嫉妬しています。

賃貸調和問題は、パートナーの好みに関する 2 つの異なる仮定の下で研究されてきました。

• 順序効用バージョンでは、各パートナーはバンドル [部屋、価格] に関する優先関係を持ちます。価格ベクトルが与えられると、パートナーは、その価格でどの部屋 (または複数の部屋) を借りたいかのみを言うことができます。
• 基数効用バージョンでは、各パートナーは金銭的評価のベクトルを持ちます。パートナーは、各部屋について、その部屋にいくら支払ってもよいかを正確に言う必要があります。パートナーは準線型効用を持つと想定されます。つまり、部屋を と評価してを支払う場合、純効用は です。${\displaystyle v}$${\displaystyle p}$${\displaystyle vp}$

基数仮定は順序仮定を暗示します。評価ベクトルが与えられれば、常に選好関係を構築できるからです。順序仮定はより一般的であり、パートナーにかかる精神的負担が少なくなります。

フランシス・スー^[1]によるプロトコルでは、パートナーの好みについて次のような仮定が立てられています。

1. 良い家: 家賃のどの区分でも、各人が少なくとも 1 つの部屋 + 家賃区画を受け入れられると感じます。
2. 外部性なし: 各パートナーの選好関係は部屋と家賃に依存しますが、他の人の選択には依存しません。
3. けちな入居者: すべての入居者は、他のどの部屋よりも、空いている部屋 (家賃が 0 の部屋) を弱く好みます。
4. 位相的に閉じた優先セット: 収束する価格のシーケンスの部屋を好むパートナーは、制限価格の部屋を好みます。

家賃総額を 1 に正規化すると、各料金体系は、に頂点を持つ 次元単体内の点になります。Su のプロトコルは、ケーキカットのSimmons–Su プロトコルと同様に、この単体の双対バージョンで動作します。つまり、特定の料金体系に対応する双対単体の三角形分割の各頂点に対して、所有者パートナーに「その料金体系でどの部屋を希望しますか?」と尋ねます。これにより、双対単体の Sperner 色付けが行われ、したがって、部屋と家賃のおおよその羨望のない割り当てに対応する小さなサブ単体が存在します。 ${\displaystyle (n-1)}$${\displaystyle n}$${\displaystyle \mathbb {R} ^{n}}$

Su のプロトコルは、羨望のない割り当てに収束する割り当てのシーケンスを返します。価格は常に非負です。したがって、結果は NN および EF の要件を満たします。

Suのレンタルハーモニープロトコルは、いくつかのニュース記事で普及しており、^{[9] [10]}、いくつかのオンライン実装があります。^{[11] [12]}

アズリーリーとシュマヤ^[2]は、各部屋の収容人数が1人より多い場合（つまり、複数のパートナーが同じ部屋に住むことができる場合）にスーの解決策を一般化している。

彼らは、以下の条件で羨望のない割り当てが存在することを証明します。

1. 良い家: 各パートナーは、各価格ベクトルが与えられた部屋の少なくとも 1 つを気に入っています。
2. 外部性なし: すべてのパートナーは無料の部屋を好みます。
3. けちなパートナー: 価格の好みは連続的です。

証明に使用される主なツールは次のとおりです。

• KKMS 定理 - Kkm 定理の一般化。
• ホールの結婚定理。

彼らの解は、Su の解と同じ意味で構成的です。つまり、解を任意の精度に近似する手順が存在します。

A. Su のソリューションと Azrieli&Shmaya のソリューションの両方で、各パートナーの好みの関係は、価格ベクトル全体に依存することが許可されています (ただし、必須ではありません)。つまり、パートナーは「部屋 A の料金が 1000 の場合、部屋 C よりも部屋 B を好みますが、部屋 A の料金が 700 だけの場合、部屋 B よりも部屋 C を好みます」と言うことができます。

このような一般性が有用である理由はいくつかある。^[2]

1. 将来の計画。パートナーが部屋 A が一番良いと考え、次に B、そして C の順だとします。A が高ければ、パートナーは B に落ち着きます。しかし、A の方が安ければ、パートナーは C (最も安い) を購入し、お金を節約して A に切り替えるかもしれません。
2. 情報が不完全です。価格ベクトルはパートナーに部屋の質に関する何らかの指標を与える可能性があります。
3. 隣人。価格ベクトルにより、パートナーは、近隣の部屋にどのような人が住むのかをある程度予測できる場合があります。
4. 非合理性効果、例えばフレーミング効果。部屋 B と部屋 C が同じ品質で同じ価格の場合、パートナーは部屋 A を購入する可能性があります。しかし、部屋 B の方が高価になった場合、パートナーは「部屋 B と同じだが、お買い得価格だ」と考えて、部屋 C に切り替える可能性があります。

B. Su のソリューションと Azrieli&Shmaya のソリューションはどちらも「けちな入居者」の仮定をしています。つまり、入居者は常に無料の部屋を無料ではない部屋よりも好むと仮定しています。この仮定は強力で、必ずしも現実的ではありません。部屋の 1 つが非常に悪い場合、一部の入居者は無料であってもその部屋に住みたくない可能性があります。これは、カーディナル バージョンで簡単に確認できます。部屋 A の価値が 0、部屋 B の価値が 100 で、部屋 A が無料で部屋 B の費用が 50 であると信じている場合、間違いなく部屋 B を好みます。

Su ^{[1] は、}この仮定を次のように弱めることを提案している。空き部屋がある場合、各パートナーは最も高価な部屋を選択することはない。これは、空いている部屋を選択することを要求しているわけではない。特に、人が常に空いている部屋を最低でも家賃総額の部屋よりも好む場合に、この仮定は成立する。しかし、上記の例のように、この弱められた仮定でさえ非現実的である可能性がある。^{[8] : 320–321}${\displaystyle 1/(n-1)}$

Segal-Halevi ^{[13] は、}この仮定をさらに弱めることができることを示している。ある部屋の料金がTで、他の部屋が空いている場合、どの部屋も T の部屋を好まないとすれば、あるエージェントにとって料金 T は高すぎるとしよう。すべてのエージェントにとって料金が高すぎる場合は常に、賃貸の調和が存在する。この仮定は、けちな借家人の仮定よりも弱く、準線形性よりも弱い。賃貸の調和の存在を保証するさらに弱い仮定があるかどうかは未解決の問題である。

上で説明したように、カーディナル バージョンへの入力は入札のマトリックスです。すべてのパートナーは、各部屋に対して、その部屋が自分にとっていくら (ドル単位) の価値があるかを入札する必要があります。通常、エージェントは準線形効用を持つと想定されるため、部屋に対する効用は、部屋の価値から部屋の価格を引いた値になります。

基数解法の重要な概念は、maxsum（別名、功利主義）割り当てです。これは、入札の合計を最大化するパートナーの部屋への割り当てです。maxsum割り当てを見つける問題は割り当て問題として知られており、ハンガリーアルゴリズムによって時間内に解決できます（ここで、はパートナーの数です）。すべてのEF割り当てはmaxsumであり、すべてのmaxsum割り当てはPEです。^[4]${\displaystyle O(n^{3})}$${\displaystyle n}$

嫉妬のなさおよび負でない支払いという 2 つの要件は、必ずしも両立するわけではありません。たとえば、総コストが 100 で、評価が次のとおりであるとします。

ここで、最大の割り当ては、部屋 1 をパートナー 1 に、部屋 2 をパートナー 2 に与えることです。パートナー 2 が嫉妬しないようにするには、パートナー 1 は 115 を支払い、パートナー 2 は -15 を支払う必要があります。

この例では、評価額の合計が総費用よりも大きい。評価額の合計が総費用に等しく、パートナーが2人または3人いる場合は、常にEFとNNの割り当てが存在する。^{[4] ：110–111}しかし、パートナーが4人以上の場合は、次の例のように、EFとNNは再び互換性がない可能性があります（証明については^{[8] ：318–319を}参照）。

この例は、序数バージョンでは発生しないことに注意してください。序数プロトコルは、「けちなパートナー」の仮定、つまりパートナーは常に空き部屋を好むという仮定を立てているからです。この仮定が成り立つ場合、EF+NN 割り当てが常に存在します。しかし、上記の例では、仮定は成り立たず、EF+NN 割り当ては存在しません。したがって、カーディナル バージョンのプロトコルは、EF と NN の間で妥協する必要があります。各プロトコルは、異なる妥協を行います。

ブラムスとキルガー^{[8] :305–328  [14]は}ギャップ手順を提案している:

1. 最大合計割り当てを計算します。
2. 最大合計額が総費用より少ない場合、パートナーは住宅所有者が要求する合計額を支払いたくないため、問題は解決できません。
3. 最大合計額が合計費用と正確に一致する場合、部屋が割り当てられ、パートナーは評価額を支払います。
4. 最大合計額が総コストを上回る場合、これらの価格と次に低い評価額との差に基づいて価格が引き下げられます (詳細については書籍を参照してください)。

最後のステップの背後にある考え方は、次に低い評価額が部屋の「競争」を表すというものです。次に高い入札者が部屋をもっと欲しがっている場合、その部屋の価格はもっと高くなります。これは、ヴィックリー オークションの精神に似ています。ただし、ヴィックリー オークションでは支払いはパートナーの入札とは完全に独立していますが、ギャップ手順では支払いは部分的にしか独立していません。したがって、ギャップ手順は戦略性がありません。

ギャップ手順では、常に非負の価格が割り当てられます。割り当ては最大和であるため、明らかにパレート効率的でもあります。ただし、一部のパートナーはそれをうらやむかもしれません。つまり、ギャップ手順は NN と PE を満たしますが、EF は満たしません。

さらに、ギャップ手順は、たとえ EF 割り当てが存在する場合でも、非羨望フリー割り当てを返す可能性がある。ブラムスはこの問題について次のように述べている。「ギャップ価格は、商品に対する入札の競争力を考慮に入れており、価格設定メカニズムは市場志向になる。羨望フリーは望ましい特性だが、これら 2 つの特性が矛盾する場合は、市場志向のメカニズムの方が好ましい。入札が競争力のある場合は、羨望を引き起こすという犠牲を払ってでも、パートナーはより多く支払うべきである」。 ^{[8] : 321}

Haake、Raith、Su ^[7]は補償手続きを提示している。この手続きが解決する問題は、いくつかの点で賃貸調和問題よりも一般的である。

• 分割する不可分な項目の数 ( m ) は、パートナーの数 ( n ) と異なる場合があります。
• アイテムのバンドルには、匿名である限り (パートナーを ID に基づいて区別しない)、任意の制約を設定できます。たとえば、制約がまったくない場合や、「各パートナーは少なくとも一定数のアイテムを受け取る必要がある」、または「一部のアイテムはバンドルされている必要がある」(たとえば、接続されたままでなければならない土地区画であるため) などの制約を設定できます。
• 合計「コスト」はプラスになることもあり、これは共有できるお金もあることを意味します。これは相続分割のシナリオの特徴です。同様に、「アイテム」はマイナスの効用を持つこともあります (たとえば、分割できない雑用を表すことができます)。

パートナーには「資格要件」があり、入札額の合計が少なくとも総費用以上である必要があります。

手順は次の手順で行います。

1. 最大合計 (実利的) 割り当てを見つけます。これは、アイテムのバンドルに対する制約を満たす、効用の合計が最も高い割り当てです。制約がない場合、各アイテムを最も高い評価を持つパートナーに提供する割り当てが最大合計です。制約がある場合 (「パートナーごとに少なくとも 1 つのアイテム」など)、最大合計割り当てを見つけるのがより困難になる可能性があります。
2. 各パートナーから、割り当てられたバンドルの価値を請求します。これにより、初期の資金プールが作成されます。
3. 初期プールからコストを支払います。すべてのパートナーが資格要件を満たしている場合は、プール内の資金は十分であり、余剰金が残る可能性があります。
4. 嫉妬深い相手に補償することで嫉妬をなくします。補償は最大でラウンドで行われます。手順は完全に説明されており、どの補償をどのような順序で行うべきかが明確に示されています。さらに、コンピューターのサポートなしで実行できるほど簡単です。${\displaystyle n-1}$
5. すべてのラウンドで行われた補償の合計は、嫉妬をなくすために必要な最小の合計であり、余剰を超えることはありません。余剰が残った場合は、各パートナーに同額を与えるなど、嫉妬を生まない方法で分割できます (この論文では、「より公平」であると考えられる他のオプションについても説明しています)。

項目が多く、制約が複雑な場合、最初のステップである最大合計割り当ての検出は、コンピュータなしでは計算が難しい場合があります。この場合、補償手順は任意の割り当てから開始される可能性があります。この場合、手順は、エンヴィ サイクルを含む割り当てで終了する可能性があります。これらのサイクルは、バンドルをサイクルに沿って移動することで削除できます。これにより、ユーティリティの合計が確実に増加します。したがって、制限された回数の反復の後、最大合計割り当てが見つかり、手順は上記のように続行して、エンヴィのない割り当てを作成できます。

補償手続きでは、一部のパートナーにマイナスの支払いを請求する場合があります (つまり、パートナーにプラスの金額を支払う)。これは、補償手続きが EF (したがって PE でもある) であり、NN ではないことを意味します。著者は次のように述べています。

「我々は、個人が他のメンバーから商品の束を受け取るために報酬を受け取る可能性を排除しません。公平な分配の文脈では、これはまったく問題ではないと考えています。実際、グループがメンバーの誰も排除したくない場合は、グループがメンバーに望まない束を受け取ったことを補助しない理由は何もありません。さらに、資格要件は、補助が、分配されるオブジェクトの完全なセットに対するプレーヤーの評価が不十分であることの結果ではないことを保証します。」^{[7] : 746}

しかし、他の著者は、通常の同居人のシナリオでは次のように主張しています。

「マイナスの家賃の部屋を割り当てられたハウスメイトは、他のハウスメイトの何人かから補助を受ける。このような状況では、一部のハウスメイトは、より大きな割引を受けられる可能性があるため、マイナスの家賃の部屋を使わずに残し、その部屋を割り当てられたハウスメイトを排除することを好むかもしれない。このような状況を避けるために、マイナスの家賃は避けなければならない」^[4]

Abdulkadiroğluら^[5]は市場ベースのアプローチを提案している。これは上昇オークションと下降オークションを組み合わせたものである。連続価格オークションとして説明するのが最も簡単である。

1. 各部屋の価格を家全体のコストに初期化します。${\displaystyle 1/n}$
2. 各パートナーの需要セット（現在の価格でパートナーが最も気に入っている部屋または部屋セット）を計算します。
3. 過剰需要の部屋（部屋数よりも多くのパートナーによって要求されている部屋。正確な定義については論文を参照してください）のセットを計算します。
4. 需要が過剰な客室の料金を同じレートで引き上げます。
5. 同時に、他のすべての部屋の料金を同じ料金で下げて、すべての部屋の料金の合計が常に合計料金と等しくなるようにします。
6. 各瞬間に、各パートナーの需要と、需要が過剰になっている部屋のセットを更新します。
7. 需要が過剰な部屋のセットが空になったら、停止してホールの結婚定理を適用し、各パートナーに需要セット内の部屋を割り当てます。

実際には、価格を連続的に変更する必要はない。なぜなら、関心のある価格は、1人以上のパートナーの需要集合が変化する価格だけであるからである。関心のある価格の集合を事前​​に計算し、連続価格オークションを離散価格オークションに変換することは可能である。この離散価格オークションは、有限数のステップの後に停止する。^{[5] : 525–528}

返される割り当ては常に羨望の影響を受けません。価格は、Haake らの手順と同様に負になる場合があります。ただし、その手順とは対照的に、負でない価格の EF 割り当てが存在する場合、価格は負ではありません。

SungとVlach ^[4]は、割り当ての一般的な性質を次のように証明している。

1. 嫉妬がないということは最大和を意味します。割り当てxが与えられた場合、 xが嫉妬のない価格ベクトル p が存在する場合、xは最大和です。
2. 最大和は羨望のなさを意味します。価格ベクトルpが与えられた場合、 pが羨望のない割り当て x があれば、任意の最大和割り当てに対してpは羨望がありません。

これらの特性に基づいて、彼らは次のアルゴリズムを提案しています。

1. 最大合計割り当てを見つけます。
2. 嫉妬のない制約の下で、最小和価格ベクトル（価格の合計が最小になるベクトル）を見つけます。このような価格ベクトルは線形計画問題の解であり、ベルマン・フォードアルゴリズムによって見つけることができます。
3. 最小合計が合計コストと等しい場合は、最小価格で最大合計の割り当てを実装して終了します。
4. 最小合計が合計コストより小さい場合は、合計が合計コストと等しくなるまですべての価格を一定の割合で増加させます (つまり、各価格に を追加します)。すべての価格を同じ量だけ変更すると、割り当てが嫉妬のない状態を維持できます。${\displaystyle (cost-minsum)/n}$
5. 最小合計が総コストより大きい場合、NN と EF の両方を満たすソリューションは存在しません。続行するにはいくつかの方法があります。
   • すべての価格を一定の割合で減らし、合計が総コストと等しくなるまで続けます (つまり、各価格から を減算します)。Haake Raith と Su の解のように、一部の価格は必然的に負になります。${\displaystyle (minsum-cost)/n}$
   • プラスの価格のみを一定の割合で減らし、合計が総費用と等しくなるまで続けます。ここでは、価格が同じ額だけ変わるわけではないので、Brams と Kilgour の解決法のように、必然的に一部のパートナーは嫉妬することになります。ただし、この解決法では、嫉妬するパートナーは無料で部屋を手に入れることができます。

最大合計割り当ての検索と最小合計価格の検索の両方の実行時複雑度は です。 ${\displaystyle O(n^{3})}$

SungとVlachの解決策は、PE、EF、NN（可能な場合）、多項式実行時間など、以前のプロトコルの望ましい特性をすべて備えているように見えます。さらに、嫉妬深いパートナー全員が空き部屋を得られることを保証します。^[15]は、線形計画問題を解くことに基づいた同様の解決策の実装を提供していますが、別の論文を引用しています。

アラゴネス^[16]は、すべてのEFソリューションの中でエージェントによる最小の支払いを最大化するEFソリューションを見つけるための多時間アルゴリズムを提示した（これはマネー・ロールズ・ソリューションと呼ばれる）。

Gal、Mash、Procaccia、Zick ^[17]は、Splidditウェブサイトの家賃分配アプリケーションの経験に基づいて、嫉妬のなさだけでは参加者の満足度を保証するのに不十分であると指摘しています。そのため、彼らは線形計画法に基づいて、嫉妬のない、かつある基準を最適化する配分を計算するアルゴリズムフレームワークを構築しました。理論的および実験的テストに基づいて、彼らは平等主義ルール（嫉妬のないエージェントの最小効用を最大化すること）が最適な結果を達成すると結論付けています。

これらのソリューションは常に EF であるため、負の価格が返される可能性があることに注意してください。

maximin ソリューションは、spliddit.org Web サイトと pref.tools Web サイトに実装されています。

ピーターズ、プロカッチャ、チュー^[18]は、 エージェントが自分の評価に自信を持てない可能性がある実践的な状況を研究した。

カーディナル モデルのほとんどの論文では、エージェントが準線形の効用関数 (効用は部屋の価値から価格を引いたもの) を持っていると想定しています。しかし、現実には、エージェントには予算の制約があり、部屋の価格が予算を上回る場合、効用は線形よりもはるかに急速に低下します。実際、エージェントは常に、予算より高い価格の部屋よりも、予算以下の価格の部屋を好みます。

この場合、EFかつ手頃な価格である価格ベクトルは存在しない可能性がある。例えば^[19]では、家賃総額が1000で、部屋が2つあり、評価額が800と200で予算が600のエージェントが2人いると仮定する。両方のエージェントが同じ準線形効用を持つ単一の価格ベクトル（800,200）が存在するが、部屋1のエージェントには支払う十分な予算がない。対照的に、手頃な価格のベクトル（例：600,400）は存在するが、羨望の的にならないわけではない。

この場合も「価格が高すぎる」という条件^[13]は成立しますが、選好は連続的ではありません（エージェントはp1>600の場合には部屋2のみを好み、p1<=600の場合には部屋1のみを好みます）。

Procaccia、Velez、Yu ^[19]は、 EFかつ手頃な価格の割り当てが存在するかどうかを調べる効率的なアルゴリズムを提示している。存在する場合、すべてのEF手頃な価格の割り当ての中で、最小の効用（平等主義的なアイテム割り当てのように）を最大化する割り当てを見つける。

Airiau、Gilbert、Grandi、Lang、Wilczynski ^[20]は、予算制約による非存在問題を克服するための2つの解決策を提案している。

• EF を予算に優しい EFに緩和します。つまり、エージェント j がiの予算よりも多く支払った場合、エージェントiはエージェントjを羨むことができます。BF-EF 割り当ては EF 割り当てよりも存在する可能性が高いですが、それでも存在することが保証されているわけではありません。彼らは、BF-EF 割り当てが存在する場合にそれを計算するためのMILP を示しています。また、固定価格ベクトルの多時間アルゴリズムと、固定部屋割り当ての疑似多時間アルゴリズムも示しています。
• 部分的な割り当て、つまり、(1,2) を価格でエージェント (1,2) に半年間割り当て、残りの半分については割り当てを逆にして、各エージェントに 500 を請求する、を許可する。彼らは、存在する場合に部分的な EF 割り当てを見つけるための線形計画法を示している。彼らは、スイッチの合計数が最小の EF 割り当てを見つけることは NP 困難である (パーティション問題またはハミングセールスマン問題からの還元により) が、動的計画法によって O*(2 ^k ) の時間で解決できることを示している。ここで、k はバーコフ分解のサイズ^{[曖昧さ回避が必要]} ( k ≤ n ² ) である。彼らは、エージェントあたりのスイッチの最大数を最小化することも NP 困難であると推測している。

これら両方の緩和により、EF 割り当てのセットが大幅に拡大されます。ただし、これらの緩和のそれぞれを適用しても、EF 割り当てが存在しない可能性があります。

Velez ^[21]は、ソフトな予算制約の下でのEF家賃分割を研究している。各エージェントは、部屋の価値、予算、予算を超えて支払わなければならないことによる限界不効用（例えば金利）を報告する。彼は、さらに平等主義（最大最小効用）または貨幣ロールズ主義（最小最大家賃）である、あるいは他の同様の条件の1つを満たすEF家賃分割を見つけるアルゴリズムを提示する。実行時間はO( n ^{k + c} )で、nはエージェントの数、kは異なる不効用値（例えば異なる金利）の数、c >2は定数である。

ベレス^[22]はこれらのアルゴリズムの戦略的特性を研究している。彼は、各アルゴリズムの完全情報非協力的結果は、許容される不効用の数が制限されている場合に限り、真の選好に関するEF配分とまったく同じであることを示している。

Arunachaleswaran、Barman、Rathi ^[23]は、準線形よりもかなり一般的な設定を研究しており、この設定では、各部屋の各エージェントの効用は、家賃の任意の区分線形関数になり得る。この設定は、ソフト予算制約を一般化する。高すぎる価格があるため、EF 割り当てが常に存在する。彼らは、FPTAS を示している。これは、1/ εおよびn ^{k + c}の時間多項式で、最大 (1+ ε ) の EF である割り当てを見つけるアルゴリズムである。ここで、n はエージェントの数、k は異なる不効用値 (異なる金利など) の数、c >2 は定数である。彼らはまた、問題が複雑性クラスPPADとPLS の交差点にあることも示している。

これまでに調査されたすべてのプロトコルは、パートナーが真の評価を明らかにすることを前提としています。それらは戦略不可能ではありません。パートナーは、偽の評価を報告することで利益を得ることができます。実際、戦略不可能性と嫉妬のなさは両立しません。常に嫉妬のない割り当てを返す決定論的な戦略不可能なプロトコルは存在しません。これは、パートナーが 2 人しかいない場合や、価格が負になることが許されている場合にも当てはまります。証明: 総コストが 100 で、パートナーの評価が以下のとおりであると仮定します (ここで、はパラメーター、)。 ${\displaystyle x,y}$${\displaystyle 0<x<y<100}$

唯一の最大和割り当ては、部屋 1 をパートナー 1 に、部屋 2 をパートナー 2 に与えることです。を部屋 2 の価格とします (部屋 1 の価格は になります)。 パートナー 1 が羨ましがらないようにするには、 が必要です。 パートナー 2 が羨ましがらないようにするには、 が必要です。 ${\displaystyle p_{2}}$${\displaystyle 100-p_{2}}$${\displaystyle p_{2}\geq x/2}$${\displaystyle p_{2}\leq y/2}$

決定論的プロトコルが価格を内のある値に設定するとします。価格が より大きい場合、パートナー 2 には、支払いを に近づけるために、 のより低い値（それでも より上）を報告するインセンティブがあります。同様に、価格が より小さい場合、パートナー 1 には、パートナー 2 の支払いを に近づけるために（したがって、自分の支払いを に近づけるために）、のより高い値（それでも より下）を報告するインセンティブがあります。したがって、このメカニズムは戦略的証明にはなり得ません。 ${\displaystyle p_{2}}$${\displaystyle [x/2,y/2]}$${\displaystyle x/2}$${\displaystyle y}$${\displaystyle x}$${\displaystyle x/2}$${\displaystyle y/2}$${\displaystyle x}$${\displaystyle y}$${\displaystyle y/2}$

研究者たちはこの不可能性に2つの方法で対処してきました。

この問題には、家全体のコストが固定されていると仮定する代わりに、各部屋に最大コストがあると仮定するバリエーションがあります。このバリエーションでは、戦略不可能なメカニズムが存在します。つまり、最小合計コストを選択する決定論的な割り当てルールは戦略不可能です。^[24]

この結果は、不可分なオブジェクトに対する柔軟性の向上と、連合戦略耐性の証明のために一般化することができます。^{[25] [26]}

元の賃貸料の調和問題に戻ると、ランダム化メカニズムを検討することができます。ランダム化メカニズムは、部屋の割り当てと家賃の分配に関する確率分布を返します。どのパートナーも部屋に自分の評価を誤って報告することで効用の期待値を増やすことができない場合、ランダム化メカニズムは期待値において真実です。ランダム化メカニズムの公平性は、いくつかの方法で測定できます。^[6]

1.事前の嫉妬のなさは、どのパートナーも他のパートナーのくじを嫉妬しないことを意味します。この条件は、誠実なメカニズムで簡単に達成できます。つまり、すべての可能な割り当てを均等な確率でランダム化し、各パートナーに合計コストを請求します。しかし、この条件は魅力的ではありません。結果として、多くのパートナーが嫉妬する可能性が高いからです。くじが公平だったという事実に、彼らは安心しないかもしれません。 ${\displaystyle 1/n}$

2.保証された嫉妬のない確率 (GPEF)とは、パートナーの評価に関係なく、少なくとも の確率で、結果が嫉妬のないものになるような一定の確率があることを意味します。 の GPEF は、次の方法で達成できます。嫉妬のない割り当てを見つけ、ランダムに整数を選択し、各パートナーを右に部屋ずつ循環的に移動させます。このランダム化されたメカニズムは期待値が真実です。これは、すべてのパートナーが各部屋に着く確率が等しく、パートナーの入札に関係なく、期待される支払額が合計コストの であるためです。EF 割り当ての確率は の確率であり、これは正確に です。これは、パートナーの数が増えると嫉妬のない確率が 0 に収束するため、心強いものではありません。しかし、これより優れた方法は不可能です。期待値が真実であるすべてのメカニズムにおいて、GPEF は最大で です。 ${\displaystyle p}$${\displaystyle p}$${\displaystyle 1/n}$${\displaystyle i\in \{0,\dots ,n-1\}}$${\displaystyle i}$${\displaystyle 1/n}$${\displaystyle i=0}$${\displaystyle 1/n}$${\displaystyle 1/n}$

3.嫉妬のないパートナーの期待数 (ENEF)とは、メカニズムのあらゆる可能な結果において嫉妬しないパートナーの数を平均すると、パートナーの評価に関係なく、期待値が少なくとも となるような特定の整数が存在することを意味します。ENEF 基準は、嫉妬が完全にない確率だけでなく、割り当てが完全に嫉妬なしではないケースの質も測定するため、GPEF 基準よりも適切と思われます。期待に忠実なメカニズムの最大 ENEF は最大で です。 に対して、この境界を達成することが可能です。 に対して、この境界をほぼ達成する期待に忠実なメカニズムが存在します。ENEF は です。一般的な考え方は次のとおりです。VCGメカニズムを使用して、最大合計の割り当てと支払いを計算します。ランダムに 1 人のパートナーを選択します。そのパートナーを無視して、VCG を再度使用します。合計支払額が合計コストと等しくなるように結果を組み合わせます (詳細については論文を参照)。次のことを示すことができます。(a) メカニズムは期待に忠実であること、(b) 無視されたパートナー以外のすべてのパートナーは嫉妬しないこと。したがって、ENEF は です。シミュレーションでは、約 80% のケースで、このメカニズムの GPEF も最大値 になることが示されています。 ${\displaystyle N}$${\displaystyle N}$${\displaystyle n-1+1/n}$${\displaystyle n=2}$${\displaystyle n>2}$${\displaystyle n-1}$${\displaystyle n-1}$${\displaystyle 1/n}$

戦略耐性要件の緩和策としては、「操作可能性の度合い」を最小限に抑えるという方法がある。^[27]これは、各プロファイルについて、ルールを操作できるエージェントの数を数えることによって定義される。この新しい概念によれば、最大限に好まれる公平な配分ルールとは、（個人および連合で）最小限に操作可能な公平で予算均衡のとれた配分ルールである。このようなルールは、公平で予算均衡のとれた配分の中で、効用が最大化されるエージェントの最大数で配分を選択する。

金銭の授受がなく、共有できるのは分割できない項目のみである問題がいくつかあります。

• 公平なランダム割り当て- 各エージェントは単一のオブジェクトを取得します。公平性はランダム化によって実現されます。
• 家の割り当て問題- 各エージェントは単一のオブジェクト (家) を取得する必要があります。ランダム化は許可されません。目標は効率性と公平性です。
• 嫉妬のないマッチング- 各エージェントは最大で 1 つのオブジェクトを取得する必要があります。目標は、嫉妬のない割り当ての数を最大化することです。
• 公平なアイテム割り当て- 各エージェントは任意の数のオブジェクトを取得できます。
• 割り当て問題- 各エージェントは単一のオブジェクトを取得する必要があります。目標は、合計値を最大化するか、合計コストを最小化することです。