単一パラメータユーティリティ

メカニズムデザインにおいて、エージェントが単一パラメータ効用を持つとは、考えられる結果に対するエージェントの評価が単一の数値で表せる場合を言う。例えば、単一の品物のオークションでは、すべてのエージェントの効用は単一パラメータである。なぜなら、効用はその品物に対する金銭的評価で表せるからである。一方、 2つ以上の関連する品物の組み合わせオークションでは、効用は通常単一パラメータではない。なぜなら、効用は通常、すべての可能な品物の束に対する評価で表せるからである。

表記

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

結果ごとに異なる評価を行うエージェント が存在します。${\displaystyle n}$

一般に、各エージェントは、 内のすべての結果に異なる無関係な値を割り当てることができます。 ${\displaystyle X}$

単一パラメータ効用という特殊なケースでは、各エージェントには、エージェントにとっての「勝利結果」である、公開されている結果の適切なサブセットがあります（たとえば、単一アイテムのオークションでは、エージェントがアイテムを獲得した 結果が含まれます）。${\displaystyle i}$ ${\displaystyle W_{i}\subset X}$ ${\displaystyle i}$ ${\displaystyle W_{i}}$ ${\displaystyle i}$

各エージェントには、の「勝利価値」を表す数値が存在する。エージェントによる の結果の評価は、以下の2つの値のいずれかを取る：^{[1] : 228}${\displaystyle v_{i}}$ ${\displaystyle i}$ ${\displaystyle X}$

• ${\displaystyle v_{i}}$ の各結果について;${\displaystyle W_{i}}$
• の各結果に対して 0 です。${\displaystyle X\setminus W_{i}}$

すべてのエージェントの勝利値のベクトルは で表されます。 ${\displaystyle v}$

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

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

単調性

弱単調性は、単一パラメータ領域において特別な形をとる。社会選択関数が弱単調であるとは、すべてのエージェントとすべてのに対して、以下の条件が満たされる場合である。 ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle {\text{Outcome}}(v_{i},v_{-i})\in W_{i}}$ そして

${\displaystyle v'_{i}\geq v_{i}>0}$ それから：

${\displaystyle {\text{Outcome}}(v'_{i},v_{-i})\in W_{i}}$

つまり、エージェントが特定の値を宣言して勝利した場合、より高い値を宣言することによっても勝利することができます (他のエージェントの宣言が同じ場合)。 ${\displaystyle i}$

単調性の性質はランダム化メカニズムに一般化することができ、空間 上の確率分布を返す。^{[1] : 334} WMONの性質は、あらゆるエージェントとあらゆるに対して、関数: ${\displaystyle X}$ ${\displaystyle i}$ ${\displaystyle v_{i},v_{i}',v_{-i}}$

${\displaystyle \Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}$

は の弱増加関数です。 ${\displaystyle v_{i}}$

臨界値

すべての弱単調な社会選択関数、すべてのエージェント、すべてのベクトルには、臨界値が存在し、エージェントの入札額が少なくとも の場合にのみ、エージェントが勝ちます。 ${\displaystyle i}$ ${\displaystyle v_{-i}}$ ${\displaystyle c_{i}(v_{-i})}$ ${\displaystyle i}$ ${\displaystyle c_{i}(v_{-i})}$

たとえば、セカンドプライスオークションでは、エージェントにとっての臨界値は他のエージェントの中での最高入札額になります。 ${\displaystyle i}$

単一パラメータ環境において、決定論的誠実メカニズムは非常に特殊な形式をとる。^{[1] : 334}任意の決定論的誠実メカニズムは関数cの集合によって完全に規定される。エージェントが勝つのは、入札額が 以上のときのみであり、その場合、エージェントは とちょうど同じ額を支払う。 ${\displaystyle i}$ ${\displaystyle c_{i}(v_{-i})}$ ${\displaystyle c_{i}(v_{-i})}$

決定論的な実装

いかなる領域においても、弱単調性は実装可能性の必要条件であることが知られている。すなわち、社会選択関数が真実のメカニズムによって実装可能であるためには、それが弱単調性を持つ必要がある。

単一パラメータ領域においては、弱単調性は実装可能性の十分条件でもある。つまり、あらゆる弱単調な社会選択関数には、それを実装する決定論的かつ真実性の高いメカニズムが存在する。これは、例えば値の二乗和の最大化や最小最大値の最大化といった、様々な非線形社会選択関数を実装できることを意味する。

このメカニズムは次のように動作するはずである：^{[1] : 229}

• エージェントに評価額を明らかにするよう依頼します。${\displaystyle v}$
• 社会的選択関数に基づいて結果を選択します。${\displaystyle x={\text{Outcome}}[v]}$
• すべての勝利エージェント（となるすべてのエージェント）は、臨界値 に等しい価格を支払います。${\displaystyle i}$ ${\displaystyle x\in W_{i}}$ ${\displaystyle {\text{Price}}_{i}(x,v_{-i})=-c_{i}(v_{-i})}$
• すべての負けたエージェント（となるすべてのエージェント）は何も支払いません。${\displaystyle i}$ ${\displaystyle x\notin W_{i}}$ ${\displaystyle {\text{Price}}_{i}(x,v_{-i})=0}$

このメカニズムは真実です。なぜなら、各エージェントの純効用は次のようになるからです。

• ${\displaystyle v_{i}-c_{i}(v_{-i})}$ 彼が勝った場合;
• 負けたら0。

したがって、エージェントは の場合は勝ち、 の場合は負けることを好みます。これはまさに、エージェントが真実を語った場合に起こることです。 ${\displaystyle v_{i}>c_{-i}}$ ${\displaystyle v_{i}<c_{-i}}$

ランダム実装

ランダム化メカニズムとは、決定論的メカニズム上の確率分布です。ランダム化メカニズムは、真実を告げることでエージェントに最大の期待値を与える場合、期待値において真実であると呼ばれます。

ランダム化メカニズムでは、すべてのエージェントに勝利の確率があり、次のように定義されます。 ${\displaystyle i}$

${\displaystyle w_{i}(v_{i},v_{-i}):=\Pr[{\text{Outcome}}(v_{i},v_{-i})\in W_{i}]}$

予想支払額は次のように定義されます。

${\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]}$

単一パラメータ領域において、ランダム化メカニズムが期待値に忠実であるための必要十分条件は次の通りである: ^{[1] : 232}

• 勝つ確率 はの弱増加関数です。${\displaystyle w_{i}(v_{i},v_{-i})}$ ${\displaystyle v_{i}}$
• エージェントの予想支払額は次のとおりです。

${\displaystyle \mathbb {E} [{\text{Payment}}_{i}(v_{i},v_{-i})]=v_{i}\cdot w_{i}(v_{i},v_{-i})-\int _{0}^{v_{i}}w_{i}(t,v_{-i})dt}$

決定論的メカニズムでは、が 0 または 1 のいずれかである場合、最初の条件は結果関数の弱単調性に縮小され、2 番目の条件は各エージェントに臨界値を課すことに縮小されることに注意してください。 ${\displaystyle w_{i}(v_{i},v_{-i})}$

単一パラメータドメインと複数パラメータドメイン

効用が単一パラメータでない場合（例えば、組み合わせオークションなど）、メカニズム設計の問題ははるかに複雑になります。VCGメカニズムは、そのような一般的な評価に機能する数少ないメカニズムの一つです。

参照

• 単峰性の好み

参考文献

1. ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。