2025-11-27T03:43:18.849174

When Contracts Get Complex: Information-Theoretic Barriers

Dütting, Feldman, Gal-Tzur et al.
In the combinatorial-action contract model (Dütting et al., FOCS'21) a principal delegates the execution of a complex project to an agent, who can choose any subset from a given set of actions. Each set of actions incurs a cost to the agent, given by a set function $c$, and induces an expected reward to the principal, given by a set function $f$. To incentivize the agent, the principal designs a contract that specifies the payment upon success, with the optimal contract being the one that maximizes the principal's utility. It is known that with access to value queries no constant-approximation is possible for submodular $f$ and additive $c$. A fundamental open problem is: does the problem become tractable with demand queries? We answer this question to the negative, by establishing that finding an optimal contract for submodular $f$ and additive $c$ requires exponentially many demand queries. We leverage the robustness of our techniques to extend and strengthen this result to different combinations of submodular/supermodular $f$ and $c$; while allowing the principal to access $f$ and $c$ using arbitrary communication protocols. Our results are driven by novel equal-revenue constructions when one of the functions is additive, immediately implying value query hardness. We then identify a new property -- sparse demand -- which allows us to strengthen these results to demand query hardness. Finally, by augmenting a perturbed version of these constructions with one additional action, thereby making both functions combinatorial, we establish exponential communication complexity.
academic

契約が複雑になるとき：情報理論的障壁

基本情報

  • 論文ID: 2403.09794
  • タイトル: When Contracts Get Complex: Information-Theoretic Barriers
  • 著者: Paul Dütting (Google Research)、Michal Feldman (Tel Aviv University)、Yoav Gal-Tzur (Tel Aviv University)、Aviad Rubinstein (Stanford University)
  • 分類: cs.GT (ゲーム理論)
  • 発表時期/会議: SODA 2026 (完全版は2025年11月27日付)
  • 論文リンク: https://arxiv.org/abs/2403.09794

要約

本論文は、組み合わせ行動契約モデルにおける情報理論的障壁を研究している。このモデルでは、委託人が複雑なプロジェクトを代理人に委託し、代理人は任意の行動部分集合を選択できる。各行動集合は代理人に費用(集合関数cで表現)をもたらし、委託人に期待収益(集合関数fで表現)をもたらす。本論文は、需要クエリ(demand queries)を使用しても、劣モジュラーfと加法的cの場合、最適契約を見つけるには指数級のクエリ回数が必要であることを証明し、この分野の基本的な未解決問題に否定的な答えを与えている。研究はさらに、劣モジュラー/優モジュラーfとcの異なる組み合わせに結果を拡張し、通信複雑度モデルの下で指数級の下界を確立している。

研究背景と動機

問題定義

本論文が研究する核心問題は組み合わせ行動契約設計(combinatorial-action contract design)である：

  • 委託人(principal)は代理人(agent)を激励する契約を設計する必要がある
  • 代理人はn個の行動から任意の部分集合Sを選択できる
  • 行動集合Sの選択は費用c(S)と成功確率f(S)をもたらす
  • 契約は成功時の支払いαを規定し、委託人の目標は自身の効用を最大化することである

問題の重要性

  1. 理論的意義: 契約設計は経済理論の柱の一つであり(2016年ノーベル経済学賞はHartとHolmströmに授与)、隠れた行動の委託-代理モデルはその基礎である
  2. 計算複雑性: 組み合わせ関数は通常、指数級のビット数で表現する必要があるため、クエリアクセスを通じた問題解決が必要である
  3. 基本的な未解決問題: FOCS'21でこのモデルが提案された後、核心的な未解決問題は：需要クエリを使用すれば問題は扱いやすくなるか？

既存手法の限界

  • 既知の正の結果:
    • fがgross-substitutesの場合、多項式回の値クエリで解ける
    • fが優モジュラー、cが劣モジュラーの場合、多項式回の値クエリで解ける
  • 既知の負の結果:
    • 値クエリを使用する場合、劣モジュラーfと加法的cは定数近似不可(EFS24)
    • 最適契約の計算はNP困難
  • 重要なギャップ: 需要クエリは値クエリの限界を突破できるか？

研究動機

需要クエリは経済学において自然な解釈を持ち、値クエリより強力である(単一の需要クエリは代理人の効用を最大化する行動集合を返すことができる)。需要クエリの能力の境界を決定することは、組み合わせ契約問題の本質的な複雑性を理解する上で重要である。

核心的貢献

本論文の主な貢献は以下の通りである：

  1. 需要クエリ硬度(主要結果1): 劣モジュラーfと加法的cの場合、最適契約を計算するアルゴリズムは指数級の需要クエリを必要とすることを証明し、FOCS'21で提案された開放問題に否定的な答えを与えている
  2. 供給クエリ硬度: 双対的に、加法的fと優モジュラーcは指数級の供給クエリ(supply queries)を必要とすることを証明している
  3. 通信複雑度下界(主要結果2): fとcが二者に保有される通信モデルでは、多項式回の最適応答クエリを許可しても、最適契約の計算には指数級の通信が必要である：
    • 劣モジュラーfと劣モジュラーc
    • 優モジュラーfと優モジュラーc
    • 劣モジュラーfと優モジュラーc
  4. 新しい技術フレームワーク: 下界を確立するためのブラックボックスツールとして、二つの重要な性質を提案している：
    • 等収益構成(Equal-Revenue): 指数個の異なる契約がすべて最適である
    • 疎な需要(Sparse Demand): 任意の価格ベクトルに対して、近似最適集合の数は多項式である
  5. タイト性: すべての下界結果は、インスタンス表現サイズがpoly(n)のときにタイトであり、既知のFPTASアルゴリズムと一致している

方法の詳細説明

タスク定義

最適契約問題(定義1):

  • 入力: 三つ組⟨n, f, c⟩
    • n: 行動の数
    • f: 2^n → 0,1 (報酬/成功確率関数)
    • c: 2^n → ℝ≥0 (費用関数)
  • 出力: 最適契約α* ∈ 0,1、委託人の効用を最大化
    • 代理人の効用: u_a(α, S) = αf(S) - c(S)
    • 委託人の効用: u_p(α, S) = (1-α)f(S)
    • 代理人の選択: S_α = argmax_S u_a(α, S)
    • 最適契約: α* = argmax_α u_p(α, S_α)

クエリモデル:

  1. 値クエリ(Value Query): 集合Sを入力として、f(S)またはc(S)を返す
  2. 需要クエリ(Demand Query): 価格ベクトルpを入力として、argmax_S(f(S) - Σp_i)を返す
  3. 供給クエリ(Supply Query): 価格ベクトルpを入力として、argmax_S(Σp_i - c(S))を返す
  4. 最適応答クエリ(Best-Response Query): 契約αを入力として、argmax_S(αf(S) - c(S))を返す

核心的技術フレームワーク

論文の証明は三つのレベルの構成に基づいている：

第一層：等収益構成(第3節)

定義(定義5): インスタンス⟨n, f, c⟩が等収益であるとは：

  1. すべての非空集合が激励可能である
  2. 2^n-1個の異なる最適契約{α_t}が存在し、各々が委託人に同じ効用をもたらす

構成方法(定理1 - 劣モジュラーfと加法的c):

  • 費用の設定: c_i = 2^(i-1)、c(S_t) = t (tはSの二進表現)
  • 再帰的に重要な値を定義: α_0 = 0、α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1)
  • 報酬の定義: f_t = f(S_t) = 1/(1-α_t)

重要な性質:

  • 補題1: α_tは厳密に増加し、α_t < 1
  • 補題2: 離散導関数f_(t+1) - f_tは減少する(劣モジュラー性を含意)
  • 命題2: fは単調劣モジュラーである

この構成の巧妙さは以下の点にある：

  1. 指数費用と二進符号化により完全な集合インデックスを実現
  2. 再帰関係は各重要な値が等収益条件を満たすことを保証
  3. 離散導関数の単調性は自然に劣モジュラー性を導く

第二層：疎な需要性質(第4.3節)

定義(定義6): 関数fがσ-疎な需要を持つとは、任意の価格ベクトルpに対して、 σ-近似需要集合D_{σ,p} = {S | max_T(f(T) - Σp_i) - (f(S) - Σp_i) ≤ σ}のサイズがpoly(n)である場合をいう。

核心補題(補題3): 曖昧区間l_i, r_iを定義する、ここで：

  • r_i = max{t | S_t ∈ D_{σ,p}、i ∈ S_t}
  • l_i = max{r_i - 2^i, 0}

任意のS_t ∈ D_{σ,p}に対して：

  • t > r_iなら、i ∉ S_t
  • t < l_iなら、i ∈ S_t

証明の思路:

  1. 等収益性質を利用：契約α_{S_t{i}}が存在し、辺際報酬 < 辺際費用
  2. したがってp_i < c_i/α_{S_t{i}} + σ
  3. インデックスがtより遠く小さい集合S_{t'}に対して、i ∉ S_{t'}なら、p_iはS_{t'}∪{i}をより最適にする
  4. これは「強制包含」効果を生じさせる

計数論証(補題4):

  • 各近似最適集合S_tを、t ∈ l_i, r_iを満たす最小の行動iにマッピング
  • 各行動iは最大O(n)個の集合に対応
  • 合計O(n²)個の近似最適集合

命題6: 構成されたfはσ-疎な需要を持つ(適切に小さいσに対して)

第三層：等収益からクエリ硬度へ

値クエリ硬度(命題5):

  • 摂動族I = {⟨n, f_k, c⟩}を構成、ここでf_k(S_k) = f(S_k) + ε
  • 「隠れた特殊集合」論証を使用
  • 任意の決定論的アルゴリズムは摂動された集合を見つけるために2^(n-1)個の集合をクエリする必要がある
  • 期待クエリ回数≥ 2^(n-2)

需要クエリ硬度(定理3): 重要な観察：アルゴリズムが元のfを知っている場合、poly回の値クエリで需要クエリをシミュレートできる

  • 価格ベクトルpに対して、需要クエリが返す集合は近似需要D_{ε,p}内にある必要がある
  • D_{ε,p}はf_kの身元に依存せず、事前に計算可能
  • |D_{ε,p}| ≤ poly(n)回の値クエリで最適集合を見つける
  • したがって需要クエリは値クエリより強くない(最大多項式因子)
  • 値クエリ下界から需要クエリ下界を得る

通信複雑度構成(第5節)

モデル: Aliceはfを保有、Bobはcをもつ、双方は通信でき、最適応答予言機にアクセスできる

構成ステップ:

  1. 費用関数の摂動(cを厳密に劣モジュラーにする):
    • c̃(S) = c(S) - δ|S|²
    • δを選択して2^n-1個の重要な値を保持
    • 命題9: Ĩ = ⟨n, f, c̃⟩は疎な最適応答を持つ
  2. 第(n+1)番目の行動を追加: 辺際報酬と費用をベクトルx_f、x_c ∈ {0,1}^(n choose n/2)でパラメータ化：
    f̂(n+1 | S_t) = z/4  if |S_t|=n/2 ∧ S_t ∈ x_f
               0    otherwise (for |S_t|≥n/2)

ĉ(n+1 | S_t) = αt·z/4  if |S_t|=n/2 ∧ S_t ∈ x_c  
               z/2      otherwise
  3. DISJへの帰約:
    • 観察5: S_t∪{n+1}形式の集合が激励可能 ⟺ |S_t|=n/2 ∧ S_t ∈ x_f∩x_c
    • 命題12: x_f∩x_c ≠ ∅なら、最適契約はS_t∪{n+1}形式の集合を激励
    • 系3: 最適契約を見つけるにはDISJ_{(n choose n/2)}を解く必要がある
    • 事実1(KS92、Raz92)より: DISJ_kはΩ(k)通信が必要
    • Ω(2^n/√n)通信下界を得る

重要な技術的ポイント:

  • z = min{ϕ_c̃、ψ_c̃、ϕ_f、ψ_f、ζ、σ}の選択は劣モジュラー性と疎性を保証
  • 辺際費用の精密な設計により、特殊な集合のみがn+1と一緒に激励可能
  • 命題13: 最適応答予言機があっても、poly通信でシミュレート可能(疎性を利用)

実験設定

本論文は純粋な理論論文であり、実験部分は含まれていない。すべての結果は厳密な数学的証明により確立されている。

理論的検証方法

  1. 構成の検証: 数学的帰納法と不等式証明により等収益構成の性質を検証
  2. 下界証明: 情報理論的論証(Yaoの最小最大原理)と帰約技術を使用
  3. タイト性分析: 既知のアルゴリズム上界(FPTAS)との比較

実験結果

主要な理論的結果

表1の要約:

f \ c劣モジュラー費用加法的費用優モジュラー費用
劣モジュラー報酬CC+BR硬度需要クエリ硬度CC+BR硬度
加法的報酬供給クエリ硬度多項式時間供給クエリ硬度
優モジュラー報酬CC+BR硬度-多項式時間

ここで：

  • 需要/供給クエリ硬度: exp(n)回のクエリが必要
  • CC+BR硬度: Ω(2^n/√n)通信が必要(poly回の最適応答クエリでも)
  • 多項式時間: 効率的なアルゴリズムが存在(DFG24)

重要な定理の陳述

定理2 (需要クエリ硬度): fが劣モジュラー、cが加法的の場合、最適契約を計算するアルゴリズムは指数級の需要クエリを必要とする。

定理4 (通信複雑度 - 劣モジュラーfとc): fとcが両方とも劣モジュラーの場合、poly(n)回の最適応答クエリを許可しても、最適契約の計算にはΩ(2^n/√n)ビットの通信が必要である。

定理8 (供給クエリ硬度): fが加法的、cが優モジュラーの場合、最適契約を計算するアルゴリズムは指数級の供給クエリを必要とする。

定理10、11 (その他の組み合わせの通信複雑度):

  • 劣モジュラーfと優モジュラーc: Ω(2^n/√n)通信
  • 優モジュラーfと優モジュラーc: Ω(2^n/√n)通信

タイト性結果

  1. FPTASとの一致: DEFK21が与えたFPTASは、インスタンス表現がpoly(n)ビットの場合、多項式時間で実行される。本論文の困難なインスタンスもpoly(n)ビットで表現可能(付録H)であるため、下界はタイトである。
  2. 次可加費用の扱いやすさ: 付録Bの観察により、DEFK25のFPTASは次可加cに拡張可能であり、この関数族に対しては、結果は一般化モデルでもタイトである。

技術的ハイライト

  1. 等収益構成の普遍性: 同じ構成技術が以下に適用可能：
    • 劣モジュラーf + 加法的c (第3節)
    • 加法的f + 優モジュラーc (付録D)
  2. 疎な需要の堅牢性:
    • 摂動下で保持される(命題9)
    • 疎な最適応答に拡張可能(定義10)
  3. モジュール化された証明構造:
    • 等収益 → 値クエリ硬度 (ブラックボックス)
    • 等収益 + 疎な需要 → 需要クエリ硬度 (ブラックボックス)
    • 摂動 + 行動追加 → 通信複雑度硬度 (ブラックボックス)

関連研究

組み合わせ契約設計

  1. DEFK21 (FOCS'21):
    • 組み合わせ行動契約モデルを提案
    • gross-substitutes fは値クエリで多項式時間で解ける
    • 劣モジュラーfはNP困難
    • 需要クエリの扱いやすさについて開放問題を提案
  2. EFS24 (ITCS'24):
    • 値クエリでは定数近似不可(P≠NPと仮定)
    • 本論文は需要クエリの情報理論的下界に強化
  3. DFG24 (SODA'24):
    • 優モジュラーf + 劣モジュラーcは値クエリで多項式時間で解ける
    • 本論文は他の組み合わせがすべて困難であることを証明
  4. DEFK25 (SODA'25):
    • 単調f + 加法的cの強多項式FPTAS
    • 次可加cに拡張可能(本論文付録B)

多代理契約

  1. BFN06a、BFNW12: 多代理 + ブール関数
  2. DEFK23: 多代理 + XOS報酬の定数近似
  3. DDPP24: 優モジュラー報酬の近似硬度

クエリと通信複雑度

  1. NS06: メカニズム設計における通信要件
  2. Dob11: 劣モジュラー評価の不可能性
  3. EFN+19: 組み合わせオークションの通信複雑度

本論文は初めて契約文献に通信複雑度結果を確立した研究である。

その他の契約方向

  • 単純 vs 最適契約 (Car15、DRT19)
  • オンライン学習 (HSV14、ZBY+23)
  • 型付き代理人 (GSW21、CMG22)
  • 情報設計 (BTCXZ24)

結論と議論

主要な結論

  1. 開放問題への回答: 需要クエリは劣モジュラーf + 加法的cの契約設計問題を扱いやすくすることができない、本質的な情報理論的障壁が存在する
  2. 全体像の刻画: (優モジュラーf、劣モジュラーc)と(加法的f、加法的c)を除き、すべての劣モジュラー/優モジュラー組み合わせが直面する：
    • クエリ複雑度障壁(一つの関数が加法的の場合)
    • 通信複雑度障壁(両方の関数が組み合わせの場合)
  3. 技術的貢献: 等収益構成と疎な需要性質は、組み合わせ契約の複雑性を研究するための一般的なツールを提供する

限界

  1. 開放問題:
    • 優モジュラーc(fが加法的でも)は近似を許可するか？(表1で開放とマーク)
    • 劣モジュラー/優モジュラーの厳密な部分クラス(XOS、gross-substitutesなど)の通信複雑度？
  2. モデルの仮定:
    • 線形契約(多くの場合で最適であることが既知)
    • 二値結果(成功/失敗)
    • 単一代理人設定
  3. 表現サイズ:
    • 主要結果はO(1)空間表現を仮定
    • 付録HはPoly(n)ビット表現に拡張
    • 無制限表現サイズモデルではいくつかの問題がより容易かもしれない

将来の方向

  1. 厳密な部分クラスの複雑性:
    • gross-substitutes(既知で扱いやすい)と一般的な劣モジュラーの間のギャップ
    • ultra関数(FY25が最近扱いやすさの境界を拡張)
  2. 近似アルゴリズム:
    • 優モジュラーcの近似可能性
    • より良い近似比の刻画
  3. 通信モデルの精密化:
    • 異なる通信プロトコルの能力
    • 最適応答予言機の必要性
  4. 多代理への拡張:
    • 本論文の技術は多代理設定に拡張可能か？
    • DEFK25は既に初期結果を持つ
  5. 実用的なアルゴリズム:
    • 最悪ケースの困難性にもかかわらず、インスタンス依存の効率的なアルゴリズムは存在するか？
    • 平滑分析または平均ケースの複雑性

深い評価

利点

  1. 重大な理論的突破:
    • FOCS'21で提案された核心的な開放問題を解決
    • この分野における初めての通信複雑度結果を確立
    • ほぼ完全な複雑性刻画を提供(表1)
  2. 技術的革新性:
    • 等収益構成は指数費用と再帰関係を巧妙に利用
    • 疎な需要性質の発見と証明は非常に洞察的(補題3の「強制包含」論証)
    • モジュール化フレームワークにより技術をブラックボックス方式で異なる設定に適用可能
  3. 証明の優雅性:
    • 再帰関係α_(t+1) = α_t + (1/2)(√(4α_t² - 8α_t + 5) - 1)はすべての性質を自然に導く
    • 二進符号化は完全なインデックスを実現
    • DISJ帰約の構成は非常に巧妙
  4. 結果の完全性:
    • 劣モジュラー/優モジュラーのすべての組み合わせをカバー
    • クエリと通信の両方のモデルを考慮
    • タイト性分析(FPTASとの一致)
    • poly(n)ビット表現への拡張(付録H)
  5. 執筆品質:
    • 構造が明確で、単純から複雑へと段階的に進む
    • 技術概要(第1.2節)は非常に有用
    • 完全な証明を提供する豊富な付録

不足点

  1. 技術的限界:
    • 優モジュラーcの近似問題は未解決(明確に開放とマーク)
    • 疎な需要の計数論証は正しいが、かなり技術的で直感が不十分
    • poly(n)ビット表現の丸め分析(付録H)は冗長で技術的
  2. 実用性の考慮:
    • 純粋な理論結果で、実際の応用について議論なし
    • 最悪ケース下界で、実際のインスタンスはより容易かもしれない
    • ヒューリスティックアルゴリズムや近似スキームについて未検討
  3. 範囲の制限:
    • 線形契約のみを考慮
    • 単一代理人設定
    • 他の関数クラス(XOS、subadditiveなど)の細粒度分析なし
  4. 表現の詳細:
    • いくつかの証明(補題2など)の代数操作は冗長
    • 通信モデルの動機をより充分に説明可能(fとcが分離される場面の理由)

影響力

  1. 理論的影響:
    • 組み合わせ契約設計の複雑性の境界を確立
    • 等収益と疎な需要は他の契約問題研究の標準ツールになる可能性
    • 契約理論における通信複雑度の応用に新しい方向を開く
  2. 後続研究への示唆:
    • 扱いやすさを得るには新しい構造的性質や制限を探す必要があることを明確化
    • 厳密な部分クラス研究の重要性を指摘
    • 困難なインスタンスを構成する体系的方法を提供
  3. 方法論的貢献:
    • 等収益構成と疎性の結合方法を示す
    • 単一行動追加により半組み合わせから全組み合わせへの技術
    • 情報理論下界と計算複雑度の関連性
  4. 再現可能性:
    • すべての証明は構成的
    • 困難なインスタンスは明示的に構成可能
    • 理論結果は実験検証不要

適用シーン

  1. 理論研究:
    • アルゴリズムゲーム理論における複雑性下界
    • 契約設計の計算可能性の境界
    • クエリ複雑度と通信複雑度研究
  2. アルゴリズム設計の指導:
    • どの場合に近似アルゴリズムを探す必要があるかを明確化
    • ヒューリスティック方法設計の指導
    • 追加構造仮定が必要なシーンの特定
  3. 経済理論:
    • 契約設計における情報の役割の理解
    • 委託-代理問題の計算的視点
    • インセンティブ設計の情報コスト
  4. 実践的示唆:
    • 見かけ上単純な劣モジュラー+加法的ケースでも、最適契約は計算困難かもしれない
    • 最適性と計算可能性の間でバランスを取る必要がある
    • 単純な契約は実践ではより望ましいかもしれない

技術的深度分析

等収益構成の数学的美しさ

再帰関係の導出は深い数学的洞察を示している：

等収益条件 (1-α_t)f_t = 1 と重要な値条件 α_(t+1) = 1/(f_(t+1)-f_t)から、以下を得る：

α_(t+1) = (1-α_(t+1))(1-α_t)/(α_(t+1)-α_t)

この方程式の解は優美な性質を持つ：

  • 厳密に増加する数列を生成
  • 自動的にα_t < 1を満たす
  • 導出されるf_tは自然に劣モジュラーである

疎な需要の組み合わせ論証

補題4の証明は精妙な組み合わせ論証を使用している：

  1. 最小の曖昧行動m(S_t) = min{i | t ∈ l_i, r_i}を定義
  2. 固定iに対してm(S_t) = iを満たす集合は「鎖」を形成することを観察：(S_t1 ∩ i*-1) ⊇ ... ⊇ (S_tk ∩ i*-1)
  3. 鎖の長さ≤ i*、したがって合計≤ Σi* · 4i* = O(n²)個の集合

この「鎖構造」の発見は疎性を証明する鍵である。

通信複雑度帰約の巧妙性

第(n+1)番目の行動を追加する構成は、辺際報酬と費用を精密に設計し、以下を実現している：

  • 大きさn/2の「特殊」集合のみがn+1と一緒に激励可能
  • 最適性はx_f ∩ x_cが非空かどうかに厳密に依存
  • 同時に劣モジュラー性と疎な最適応答を保持

この構成技術は他の通信複雑度下界に示唆を与える可能性がある。

参考文献(精選)

  1. DEFK21 Dütting、Ezra、Feldman、Kesselheim。「Combinatorial Contracts」FOCS 2021。(元のモデル)
  2. EFS24 Ezra、Feldman、Schlesinger。「On the (In)Approximability of Combinatorial Contracts」ITCS 2024。(値クエリ硬度)
  3. DFG24 Dütting、Feldman、Gal-Tzur。「Combinatorial Contracts Beyond Gross Substitutes」SODA 2024。(正の結果)
  4. KS92 Kalyanasundaram、Schintger。「The Probabilistic Communication Complexity of Set Intersection」SIDMA 1992。(DISJ下界)
  5. DRT19 Dütting、Roughgarden、Talgam-Cohen。「Simple versus Optimal Contracts」EC 2019。(単純契約)

総合評価: これは傑出した理論論文である。新しい技術ツール(等収益構成と疎な需要)を導入することで、組み合わせ契約設計分野の核心的な開放問題を解決し、この分野における初めての通信複雑度結果を確立している。論文の技術的深さ、結果の完全性、執筆の明確さはすべてトップレベルに達している。純粋な理論研究であるが、確立された複雑性の境界はこの分野の将来の発展に重要な指導意義を持つ。主な限界は優モジュラー費用の近似問題が未解決であること、および実際の応用についての議論がないことであるが、これらはすべて明確に標記された将来の方向である。