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

メカニズム設計において、エージェントが持つ効用は、起こりうる結果に対する評価を単一の数値で表せる場合、単一パラメータであると言われます。例えば、単一のアイテムのオークションでは、すべてのエージェントの効用はアイテムの金銭的評価で表せるため、単一パラメータです。一方、 2つ以上の関連アイテムの組み合わせオークションでは、効用は通常、アイテムのあらゆる組み合わせに対する評価で表されるため、単一パラメータではありません。

セットがあります${\displaystyle X}$起こりうる結果の。

がある${\displaystyle n}$各結果に対して異なる評価を行うエージェント。

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

単一パラメータ効用の特殊なケースでは、各エージェントは${\displaystyle i}$結果が公に知られている真の部分集合を持つ${\displaystyle W_{i}\subset X}$これらはエージェントにとっての「勝利の結果」である。${\displaystyle i}$（例：単一アイテムのオークションでは、${\displaystyle W_{i}}$エージェントの結果が含まれています${\displaystyle i}$（アイテムを獲得する）

エージェントごとに、${\displaystyle v_{i}}$これは「勝利の価値」を表します${\displaystyle i}$エージェントによる結果の評価${\displaystyle X}$以下の2つの値のいずれかを取ることができます：^{[ 1 ]： 228}

• ${\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}$。それは次のように表されます。$結果(v)$または$\displaystyle {\text{結果}}(v_{i},v_{-i})}$。

弱単調性の性質は、単一パラメータ領域では特別な形式をとる。社会的選択関数は、すべてのエージェントに対して、弱単調である。${\displaystyle i}$そしてすべての${\displaystyle v_{i},v_{i}',v_{-i}}$、 もし：

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

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

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

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

単調性特性は、空間上の確率分布を返すランダム化メカニズムに一般化できます。${\displaystyle X}$^{[ 1 ] : 334} WMONプロパティは、すべてのエージェントについて次のことを意味します。${\displaystyle i}$そしてすべての${\displaystyle v_{i},v_{i}',v_{-i}}$関数:

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

は、弱増加関数である。${\displaystyle v_{i}}$。

あらゆる領域において、弱単調性は実装可能性の必要条件であることが知られている。つまり、社会的選択関数は、弱単調である場合に限り、真実性を備えたメカニズムによって実装できる。

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

このメカニズムは次のように機能するはずです。^{[ 1 ]： 229}

• エージェントに査定額を開示するように依頼し、${\displaystyle v}$。
• 社会的選択関数に基づいて結果を選択してください。${\displaystyle x={\text{結果}}[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}$

決定論的メカニズムでは、${\displaystyle w_{i}(v_{i},v_{-i})}$が0または1の場合、最初の条件は結果関数の弱単調性に帰着し、2番目の条件は各エージェントに臨界値を割り当てることに帰着します。

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

• 単峰性の嗜好