単調性（機構設計）

メカニズム設計において、単調性は社会的選択関数の特性である。これは、戦略的証明メカニズムを使用してそのような関数を実装するために必要な条件である。その言葉による説明は次の通りである: ^[1]

あるエージェントのタイプを変更すると（他のエージェントのタイプは固定したまま）、社会的選択関数による結果が変わる場合、このエージェントの新しいタイプで評価された新しい結果と元の結果の効用の差は、このエージェントの元のタイプで評価された効用の差と少なくとも同じである必要があります。

言い換えれば：^{[2] : 227}

一人のプレイヤーが評価を変えたときに社会的選択が変わる場合、それはそのプレイヤーが古い選択の価値に比べて新しい選択の価値を高めたからに違いありません。

考えられる結果はいくつかあります。 ${\displaystyle X}$

エージェントには、結果ごとに異なる評価を持つものがあります。エージェントの評価は、各選択肢に割り当てる値を表す 関数として表されます。${\displaystyle n}$${\displaystyle i}$$${\displaystyle v_{i}:X\longrightarrow R_{+}}$$

すべての価値関数のベクトルは で表されます。 ${\displaystyle v}$

すべてのエージェント について、他のエージェントのすべての価値関数のベクトルは で表されます。つまり です。 ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v\equiv (v_{i},v_{-i})}$

社会的選択関数は、値ベクトルを入力として受け取り、結果を返す関数です。これはまたはで表されます。 ${\displaystyle v}$${\displaystyle x\in X}$${\displaystyle {\text{結果}}(v)}$${\displaystyle {\text{結果}}(v_{i},v_{-i})}$

社会選択関数が強単調性特性 (SMON) を満たすのは、すべてのエージェントおよびすべてのに対して、次の条件が満たされる場合です。(初期の好みにより、エージェントは初期の結果を好みます)。(最終的な好みにより、エージェントは最終的な結果を好みます)。 または同等です。${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$$${\displaystyle x={\text{結果}}(v_{i},v_{-i})}$$$${\displaystyle x'={\text{結果}}(v'_{i},v_{-i})}$$$${\displaystyle x\succeq _{i}x'}$$$${\displaystyle x\preceq _{i'}x'}$$$${\displaystyle v_{i}(x)-v_{i}(x')\geq 0}$$$${\displaystyle v_{i}'(x)-v_{i}'(x')\leq 0}$$

お金がなくても結果関数を持つ戦略証明メカニズムが存在する場合、この関数は SMON である必要があります。 ${\displaystyle 結果}$

証明: あるエージェントとある評価ベクトルを固定します。戦略不可能性とは、実評価を持つエージェントが、嘘をついて宣言するよりも、宣言することを弱く好むことを意味します。したがって、次のようになります。 同様に、実評価を持つエージェントは、嘘をついて宣言するよりも、宣言することを弱く好むことになります。したがって、次のようになります。${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$$${\displaystyle v_{i}(x)\geq v_{i}(x')}$$${\displaystyle v_{i}'}$${\displaystyle v_{i}'}$${\displaystyle v_{i}}$$${\displaystyle v_{i}'(x')\geq v_{i}'(x)}$$

メカニズムがお金の使用を許可されている場合、メカニズムはエージェントにとってあまり好ましくない代替手段に切り替えて、そのエージェントにお金で補償できるため、SMON プロパティは実装に必要ではなくなります。

社会選択関数は、あらゆるエージェントおよびあらゆるに対して、次の条件が満たされる場合、弱単調性特性 (WMON) を満たします。${\displaystyle i}$${\displaystyle v_{i},v_{i}',v_{-i}}$$${\displaystyle x={\text{結果}}(v_{i},v_{-i})}$$$${\displaystyle x'={\text{結果}}(v'_{i},v_{-i})}$$$${\displaystyle v_{i}(x)-v_{i}(x')\geq v_{i}'(x)-v_{i}'(x')}$$

結果関数を持つ戦略証明メカニズムが存在する場合、この関数は WMON である必要があります。 ${\displaystyle {\text{結果}}}$

証明: ^{[2] : 227}あるエージェントとある評価ベクトルを固定します。戦略不可能なメカニズムには価格関数 があり、これはメカニズムの結果が のときにエージェントが受け取る支払い額を決定します。この価格は結果に依存しますが、 に直接依存してはいけません。戦略不可能性とは、評価を持つプレイヤーがを宣言するよりも を宣言することを弱く好むことを意味します。したがって、次のようになります。同様に、評価を持つプレイヤーはを宣言するよりも を宣言することを弱く好むことを意味します。したがって、次のようになります。最初の不等式から 2 番目の不等式を引くと、WMON プロパティが得られます。 ${\displaystyle i}$${\displaystyle v_{-i}}$${\displaystyle 価格_{i}(x,v_{-i})}$${\displaystyle i}$${\displaystyle x}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{i}'}$$${\displaystyle v_{i}(x)+{\text{価格}}_{i}(x,v_{-i})\geq v_{i}(x')+{\text{価格}}_{i}(x',v_{-i})}$$${\displaystyle v_{i}'}$${\displaystyle v_{i}'}$${\displaystyle v_{i}}$$${\displaystyle v_{i}'(x)+{\text{Price}}_{i}(x,v_{-i})\leq v_{i}'(x')+{\text{Price}}_{i}(x',v_{-i})}$$

単調性は必ずしも実装可能性の十分な条件ではありませんが、十分な条件となる重要なケースがいくつかあります (つまり、すべての WMON 社会的選択関数を実装できます)。

• エージェントが単一パラメータのユーティリティ関数を持つ場合。
• 多くの凸領域では、特に各値関数の値域が のときに顕著になります。^[1]${\displaystyle \mathbb {R} ^{+}}$
• 各値関数の値域が、つまり立方体の場合 (Gui、Müller、Vohra (2004))。${\displaystyle \mathbb {R} }$
• 任意の凸領域において（Saks and Yu (2005)）。
• 凸閉包を持つ任意の領域において。^[3]
• あらゆる「単調性領域」において。^[3]

1. エージェントが単一のピークを持つ選好を持つ場合、中央値の社会的選択関数（エージェントにとって最良の結果の中から中央値を選択する）は強く単調です。実際、中央値の投票を選択するメカニズムは、お金を使用しない誠実なメカニズムです。中央値投票ルールを参照してください。
2. エージェントが基数効用関数によって表される一般的な好みを持っている場合、功利主義的な社会的選択関数（エージェントの評価の合計を最大化する結果を選択する）は強単調ではなく、弱単調です。実際、これはお金を使った真実のメカニズムであるVCG メカニズムによって実装できます。
3. ジョブ スケジューリングでは、メイクスパン最小化の社会的選択関数は、強単調でも弱単調でもありません。実際、これは真実のメカニズムでは実装できません。真実のジョブ スケジューリングを参照してください。

• 投票システムにおける単調性基準。
• マスキンの単調性
• さまざまな分野における単調性のその他の意味。