※本記事は、Stanford UniversityのSanmi Koyejo准教授による講義「Stanford CS329H: Machine Learning from Human Preferences」の「Mechanism Design」回の内容を基に作成されています。講義の詳細情報は https://web.stanford.edu/class/cs329h/ でご覧いただけます。本記事では、講義の内容を要約しております。なお、本記事の内容は原講義の見解を正確に反映するよう努めていますが、要約や解釈による誤りがある可能性もありますので、正確な情報や文脈については、オリジナルの講義動画（https://www.youtube.com/watch?v=zkHTbb-0Gns ）をご覧いただくことをお勧めいたします。
登壇者紹介 Sanmi Koyejo氏は、Stanford Universityコンピュータサイエンス学部の助教授(Assistant Professor)です。Stanfordのオンライン人工知能プログラムに関する詳細は https://stanford.io/ai で、本コースへの登録に関する情報は https://online.stanford.edu/courses でご確認いただけます。コース全体のプレイリストは、YouTubeの「Stanford CS329H: Machine Learning from Human Preferences」チャンネルでご覧いただけます。
1. メカニズムデザインの概要と基本概念
1.1 メカニズムデザインの定義：ルール作りの科学
講師：今日の目標は、メカニズムデザインをこれまで取り上げてきたアイデアの組み合わせとして扱い、少なくとも私の視点から見て興味深いツールの一つとしてカバーすることです。これは社会選択や投票といった概念と、ゲーム理論のアイデアを組み合わせたものです。ゲーム理論については以前の講義の最後で少し触れましたが、社会選択とゲーム理論の両方に接続しています。これらの接続関係が何であるかを明確にしていきたいと思います。
今日話す内容の一部は、以前に取り組んだことをベースにしています。具体的には、バンディット、選好モデリング、選好最適化に関する質問に関連したものです。今回は似たようなアイデアを扱いますが、戦略的またはゲーム理論的な設定で考えます。つまり、行為者が敵対的であったり、様々な方法で虚偽の情報を提供したりする可能性がある状況を想定します。このフレームワークが今日の講義の終わりまでに明確になることを願っています。
メカニズムデザインを以前に学んだことがない方のために、少しフレームを設定しましょう。この分野が自らをどう定義しているかというと、「ルール作りの科学」という観点からです。参加者が戦略的に行動することを選択した場合でも、望ましい結果を得られるようにルールを設計する方法について考えます。ここで「戦略的」とは、システムへの参加方法が、例えば敵対的であったり、自己の選好を優先したり、あるいは様々な方法で参加を選択したりすることを含むという意味です。
それでも、全体的なエコシステムが正しく機能し、何らかの望ましい結果につながるようにします。これは社会選択と同様の設定です。社会選択と同じく、デザイナーの役割の一部は、望ましい結果が何であるかを決定することです。それを超えて、デザイナーの仕事は、どのような介入が可能か、あるいはゲームのルールをどのように決定できるかを考え出すことです。行為者がその結果において敵対的または戦略的であることを選択した場合でも、望ましい結果を得られるようにするのです。これが、この分野が答えようとしている広範な問いの枠組みです。
1.2 社会選択理論とゲーム理論との関連
講師：これをもう少し明確にしていきたいと思います。進めていく中で、具体例を交えながら説明していきます。メカニズムデザインは、様々な研究分野から借用しています。伝統的には主に経済学で研究されてきた分野です。ゲーム理論のアイデアから多くを借用しています。実際の期間は定かではありませんが、少なくとも最近の記憶では、大手インターネット企業が台頭した時期とほぼ一致していると言えるでしょう。
その結果、メカニズムデザインは実世界の計算タスクに非常に有用であることが判明しました。そのため、計算分野の文献でますます研究されるトピックとなりました。今日はこれらのいくつかに触れていきます。これには、例えばヨアキムの議論、連想選択、計算複雑性の概念などが含まれますが、それだけではありません。機械学習モデルがメカニズムの一部である場合、メカニズム内でのその学習プロセスをどう考えるかという興味深い問題もあります。繰り返しになりますが、これらのいくつかは今日の講義の過程で明確になっていくことを願っています。
1.3 歴史的背景と実社会への応用
講師：いくつかの実際の影響について話していきます。しかし、最も明確な成功例の一つであり、実際に今日最も時間をかけて取り上げるアイデアは、オークションや様々な種類の価格設定、経済的意思決定といったものです。メカニズムの設計、その特性の研究、そして様々な種類の実世界の文脈において、これらは多大な影響を与えてきました。
ここでは、文字通りのオークションの例を示しています。これから数分間議論する内容の雰囲気を感じていただくためです。まず、メカニズムデザインのアイデア、オークションのアイデアが影響を与えてきた既存の例から始めましょう。例えば、電波の周波数帯について入札オークションプロセスが行われた時期があります。規制緩和によって状況が変わった時です。
入札プロセスを設定するためにメカニズムデザインのアイデアを使用した多くの研究がありました。実際、行為者は明らかに自己利益を持っていました。彼らは利益を最大化したいと考えていたのです。それでも、良い結果が得られる可能性が高いようなプロセスを設定したいわけです。これが、メカニズムデザインがやろうとしていることのフレーミングです。歴史に興味がある方は、これらが良い参考文献となるでしょう。
こうしたアイデア、特にオークションや価格設定といったものは、多くのウェブ企業で大量に使用されています。先ほど挙げた例に触れると、Amazonがアイテムの価格設定や順序付けを決定するようなケースがあります。大手ウェブ検索企業の多くは、この文献から借用したアイデアを使用しています。Googleは、検索の背後にある広告購入プロセスを支える要素の一つとしてこれを使用しています。
私はこれらの数字が好きです。最初にこの講演を行った同僚から借用しています。参考文献は最後にあります。2016年、Googleは広告で790億ドルの収益を上げました。総収益は896億ドルでした。間違いなく、収益の圧倒的大部分は広告に結びついています。そして、この技術は、オークションプロセスや入札プロセスなどによって支えられているのです。Facebookも同様です。2016年には、広告収益以外のすべては、広告収益と比較すると四捨五入誤差のようなものだったと思います。広告プロセスを支えているのは、メカニズムデザインから来るオークションのアイデアです。その多くは直接借用されており、一部は小さな調整が加えられています。これについては、今日の講義の過程で触れていきます。
ここで重要なポイントは、この分野が、特に最近において、社会に大きな影響を与えてきた分野であるということです。なぜなら、それがもたらすツールが、現在、多くの価格設定に関する意思決定、オークション、様々な種類の集団的意思決定に使用されているからです。
2. オークションの基本フレームワークと戦略的行動
2.1 経済的選好の推論：コーヒーショップの例
講師：私たちの目的において、より直接的に言うと、これらのツールを使用することにつながる可能性のある重要な質問、あるいは一つの中心的な質問は次のようなものです。真の経済的選好を推論できるだろうか、という問いです。ここで経済的選好とは、異なるステークホルダーが、この場合は買い手が、販売を検討している特定のアイテムに対してどのような実際の価値または価格を持っているかを考えています。
このような設定にいてメカニズムを使用する場合、メカニズムはどの買い手がどのアイテムを受け取るかを決定する必要があります。そして、それぞれのアイテムに対していくら支払うかを決定します。その根底にある目標は、社会的に望ましい結果を定義できるような方法で行うことです。多くの場合、これらの設定では、社会的に望ましい結果とは、支払われる金額が個人にとってのアイテムの実際の価値に見合っているということです。経済的に良い結果とは、アイテムを最も価値あるものと考える人が、その真の価値で入札した場合に、そのアイテムの入札に実際に勝つということかもしれません。
例えば、コーヒーショップの設定では、アイテムはコーヒー、カップケーキ、またはコーヒーとカップケーキの組み合わせになる可能性があります。2人の潜在的な買い手がいて、それぞれコーヒーの価値、カップケーキの価値、つまりいくら支払う意思があるか、あるいはコーヒーとカップケーキの組み合わせについて、異なる価格を持っています。
ここでのタスク、メカニズムのタスクは、相互作用システムをどのように設計するかを考え出すことです。例えば、カップケーキだけを比較する場合、カップケーキを最も価値あるものと考える個人が入札に勝つかもしれません。ここで述べておく価値があるのは、買い手である個人には戦略的である動機があるということです。彼らはアイテムを欲しいのですが、同時にできるだけ少なく支払いたいとも考えています。
ある意味でシステムを出し抜こうとし、できるだけ少なく支払おうとすることと、販売されているアイテムのセットに対して何らかの本質的な価値を持っていることとの間には、この緊張関係があるのです。これは一般的なフレームワークとして理解できますか？
学生：はい、質問があります。この例では、カップケーキについて、一人は3ドル支払う意思があり、もう一人は2ドルです。では、2ドルが価格だと考えると、私たちは一人の人から彼が出せる最大額である3ドルを搾取していることになります。社会的な設定では、これは良い結果でしょうか？私たちはただ、ユーザーがいくら支払う意思があるかを搾取して、3ドルまで行こうとしているだけではないでしょうか。
講師：それは興味深い指摘だと思います。非常に高いレベルで言うと、社会的に価値のある結果が何であるかを決定するのはデザイナー次第です。この問題の多くのフレーミングは、本質的に最大の収益を望ましい結果として使用していると思います。その設定では、支払われる価格を最大化することが目指すべきことになります。非常に高いレベルで言うと、このクラスの範囲を少し超えますが、社会選択について述べたことの多くはここにも当てはまると思います。
デザイナーとして、望ましい結果が何であるかを決定することはあなたの仕事の一部です。そのため、収益を最大化する以外の異なる目標に到達するようなメカニズムを設計することを決定できます。とはいえ、今日話すことのほとんど、少し関わりますが、大部分は行為者の戦略的行動と、戦略的行動に騙されないようにする方法に取り組むことになります。
しかし、社会的善として収益を最大化することを中心にフレーミングされると思います。これに関連する他の概念もあります。福祉のようなもので、それほど異なるわけではありませんが、コストと収益にいくらかの違いがあります。繰り返しますが、10,000フィートの視点から見ると、デザイナーは社会的善と考えるものとして異なる社会的結果を選ぶことができます。そしてその結果に対して、それを達成するためのメカニズムを設計できるのです。ですから、設計には柔軟性があると言えます。
しかし実際には、そして経済学の人々にとっては驚くべきことではないかもしれませんが、収益最大化を良い結果と考えるのは超明白というわけではないかもしれません。つまり、私たちはこれを深く掘り下げませんが、人々が資本主義スタイルの収益最大化を市場を設計する良い方法、他の多くのものを設計する良い方法だと考える理由について、哲学的な議論が存在します。
ですから、私たちはそれにあまり深入りしませんが、その文献から多くを借用します。この点に時間を費やしているかもしれませんが、高いレベルで言うと、他の良い結果を考え、それらのために設計する道があると言っておきます。良い質問です。ありがとうございます。他に考えはありますか？
わかりました。これが選好とどのように結びつくかも明らかだと思います。なぜなら、選好を経済的なものとして、または経済的に価格付けされたり、判断されたり、評価されたりできるものとして考えるなら、前提はここで価格として根拠づけられるからです。人々は特定のアイテムに対して支払う意思があります。ですから、このクラスの全体的なフレームで話してきた多くの種類の選好を考えると、不完全かもしれません。多くのものは経済的に明白に定量化できるようには見えません。しかし、今日カバーすることのほとんど、多くのアプリケーション、特に物事を経済的に根拠づけることができる場合、このアプローチは非常に有用になり得ます。
これはもう少し一般的ですが、これが議論を行う最も簡単な方法だと思います。ですから、ほとんどそうすると思います。これも他のすべてと同様に、ほぼ一つの完全な分野であることを言っておくべきです。そしてここでも、それに関する完全なクラスが存在し、私は素材の表面に触れているだけです。
私が望んでいるのは、特に気づいていない人々に、これがどのように興味深いか、選好を引き出すこと、社会選択の種類の質問についての私たちの問いにどのように情報を与えるかを知らせることです。そして、人々が興味を持っているなら、参考文献を提供しますので、さらに深く掘り下げて、さらなることを考えることができます。これがフレーミングです。これが設定です。あなたができることはたくさんあります。
メカニズムがやらなければならないことをどのように決定するか、非常に明白で標準的なアプローチがあります。3つのアイテムに対する入札をどうするか、あるいは彼らが何を支払うかです。声に出して考えを言うと、どうやって決めるか、推測ですが、これらの人々にアイテムを販売する方法についてどう考えますか。つまり、これらが人々です。これらが買い手です。あなたがデザイナーです。
今は収益を最大化したいとしましょう。人々がこの活動に参加できるように、どのようなメカニズムを設計するか、あなたが決定するかもしれないいくつかの方法は何でしょうか？明白で面白くないものがあります。明白なものは、オークションではないほとんどの場所で起こることです。つまり、何らかの価格を設定して、人々は自分の価値に基づいてアイテムを購入するかどうかを決定するだけです。
多くの場合、私たちはこれを個人レベルで考えます。これは効用として考えるかもしれません。ですからこの価格設定は、コーヒーに1.50ドル、カップケーキに3.50ドルを選ぶかもしれません。そして、おそらくこれを個別に価格設定するので、組み合わせはコストの合計にすぎません。
一方、個人にとって、コーヒーとカップケーキを一緒にした場合の価格または価値は、実際には別々の場合とは異なります。これは多くの異なる種類の経済的意思決定で簡単に起こり得ると考えることができます。この設定では、個人は、3.50ドルプラス1.50ドルは6ドル未満だと考えるので、おそらく購入するでしょう。
彼らにとって、彼らは効用を増加させました。なぜなら、彼らは6ドル支払う意思があるからです。一緒にしたアイテムの合計価格は5ドルです。ですから、価格は彼らの内部効用よりも低いのです。内部価値よりも低いので、ここでの効用は6マイナス5で1になります。
学生：はい。価格は加法的ですか？混乱しています。
講師：それは良い質問です。この例とより一般的なフレーミングでは、これも述べておくべきですが、ここで述べてから、より一般的に橋渡ししようと思います。この設定は、加法的でないアイテムのセット全体での価格を許可しています。そして、それは多くの現実世界の行動と一致するようです。人々は個々のものとは異なる形でものの集合を評価します。コーヒーとケーキで試してみましょう。
実際にこれが真実かもしれない状況を想像できます。実際に両方が必要で、どちらかだけでは満足できない状況です。両方がある場所を選ぶかもしれません。これが現実世界の意思決定であると想像できます。しかし、他のリソースについて考えてみましょう。わかりません、クラスを選んでいて、コースプロジェクトで一緒に働くかもしれないインストラクター、計算リソースを決定しなければならないとします。それぞれのものに個別に何らかの価格設定があります。
実際にそれらのものを共同で持つこと、適切な構成でそれらのものを持つことには、何らかの価格設定があると想像できます。それは個々のものとは非常に異なります。なぜなら、それぞれのものは互いに少し干渉し合うからです。そして、実際に正しい答えは組み合わせなのです。そして、あなたの組み合わせを一致させる必要があります。
ですから、組み合わせを得ることへの価格設定は、好きなインストラクターを得ることや、わかりません、友達がクラスを取っていることや、あるいはクラスが学生一人当たり10個のGPUを提供することを約束していることよりも、はるかに高い可能性があります。個別には、これらは意味があります。そして一部の意思決定者にとっては、単一の問題です。十分なGPUをくれるなら、他のことは気にしません。
あるいは友達がクラスを取っていれば、他のことは気にしません。しかし、私たちの多くにとって、実際には組み合わせが重要だと主張します。そして私たちはこれらのもの間でトレードオフを行っています。そして、トレードオフは加法的ではないかもしれないので、組み合わせは実際に異なる価値を持つ可能性があるのです。あなたの質問をフレーミングするためだけに言いました。
しかし、より一般的には、フレームワークは組み合わせが必ずしも加法的でない設定を許可します。良い質問です。他の考えや質問はありますか？これはおそらく標準的なものです。これはほとんどの場所で起こることです。最後に得られるのは、誰かがある価格であなたのアイテムを購入した場合、純粋に経済的に考えているなら、あなたが知っているのは、彼らの価値があなたの述べた価格よりも高いに違いないということです。
少なくともそれだけは学べます。順序付けのようなものです。なぜなら、そうでなければこのモデルの下で、彼らはあなたのアイテムを購入しないからです。彼らが正の効用を持つ必要があります。個々の選好についてそれほど多くを学ぶわけではありませんが、少なくとも彼らが購入するものをどう評価しているかについて、何らかの方向性を示す信号を学びます。理解できますか？
2.2 買い手の戦略的インセンティブと社会的望ましい結果
講師：何か他のことをするかもしれません。オークションを行うかもしれません。これは、アイテムがあって、全員がアイテムのセットに入札するというものです。そして、勝利入札を持っている人がアイテムを手に入れます。これはおそらく標準的なものです。ある程度まで標準的なものです。ある程度まで、あなたはこれを展開すれば、人々のアイテムに対する実際の価値についてより多くの信号を得られるかもしれないと想像するかもしれません。なぜなら、彼らがアイテムをどれだけ実際に評価しているかと相関する何かを入札することを期待または望むからです。彼らはそうしないかもしれません。
そして実際、これが多くの文献とここでの取り組みの内容です。個々の買い手がこの設定で何をするか、そしてどのようにこのシステムを有利にしようとするかに、再び取り組んでいるのです。何か考えはありますか？このクラスでアイテムに入札していたとしたら、少なくとも対面でここにいる6人の他の人々がいて、私たちは皆、何らかの理由でモナリザを購入することを選んだとします。そして私たちはそれを買う余裕があります。あなた方の中にはモナリザを買う余裕がある人もいるかもしれませんが、実際には買えないと思います。
標準的な入札、標準的なオークションを行います。戦略的になりたくて、おそらくアイテムをより安く手に入れたい場合、何をするかについての考えはありますか？
学生：つまり、最小限の金額だけ入札します。トップにする必要があります。
講師：そうですね。つまり、あなたは見つけ出します。特にあなたが最後に入札する人である場合です。ですから、最も多くの情報を得られるように情報を順序付けようとします。他の全員が何を入札する意思があるかを得ます。あなたの実際の価値はより高いかもしれません。あなたの価値が現在の最高価格よりも高い場合、少し上に行くだけで、入札を終わらせます。それは、戦略的である個人にとって非常に合理的なことをするように思えます。
ですから、社会的福祉を最大の収益として考えているなら、それは悪い結果です。人々の真の効用または物事の価値を見つけ出すという目標について考えているなら、それはおそらく理想的でもありません。なぜなら、人々は必ずしも真の価値を入札する動機がないからです。彼らは勝つために入札する動機があります。
そして勝つことは、実際に彼らが最も価値を置くものを入札することとは異なるのです。他にできる戦略的行動について他に考えはありますか？それが明白なものだと思いますが、他にもあります。どう考えますか？私たちが持つ他の議論のいくつかでそれに到達すると思います。もう一つの選択肢は、あなたが見たことがあり、非常に人気のあるものですが、セカンドプライスオークションです。
2.3 標準的な価格設定方式とその限界
講師：あなたがすることは、全員が入札します。これはあなたが話したばかりの戦略を部分的に緩和します。全員が入札します。全ての入札を一緒に集めますが、あなたが支払う金額は最高入札ではありません。あなたは2番目に高い入札を支払います。なぜこれが興味深いのでしょうか？
学生：同点は？
講師：同点は興味深いですね。それはこれとは少し別のことだと思います。議論のために、各入札が一意であると仮定しましょう。ですから、同点がないようにします。好きなものに入札できますが、この議論を簡単にするために、他の誰かとまったく同じ数字を入札することは許されません。
学生：はい。それは興味深いです。なぜなら、私は100万ドルを入札できるからです。
講師：そうですね。
学生：そして誰もこれを支払いたくないでしょう。だから私は手に入れられます。これは一つの方法です。あなたは、2番目の価格を支払う意思がある限り、法外に大きな数字を入札することで、常に入札に勝つことができます。そして、入札に勝って、価格が何であれ支払うだけで済みます。
講師：つまり、反論としては、誰かがあなたがそれをしたことに腹を立てて、999,000ドルを入札する可能性があるということです。
学生：その通りです。ですから、再び、全員が戦略的です。
講師：ありがとうございます。はい、まさにこれです。他の行為者のことです。誰かが見ます。特にあなたが最後に入札する人でない場合です。繰り返しになりますが、私たちは何らかの順序付けの簡略版を作っています。しかしそうです、まさにこれです。誰かがあなたに対して敵対的になることができます。
そして今、2番目に高い入札は非常に高い数字になり、あなたの価値よりもはるかにはるかに高くなります。それは明らかに、他の行為者からの対抗戦略です。繰り返しになりますが、彼らの自己利益は入札に勝つことであり、他の人々が入札を失うことが理想的な結果なのです。
学生：そうですね。また、売り手がアイテムの価値についてどう考えているかと、購入を選択している参加者のセットとの間に不一致がある可能性があると想像することもできます。
講師：そして、この問題を緩和する一つの方法、他のことには有用ではありませんが、おそらくすべての買い手と売り手との間の価値の不一致の問題を緩和する一つの方法は、リザーブプライスを持つことです。ですから、2番目の価格が勝つのではなく、販売の最小価格があります。売り手は、少なくとも彼らのアイテムの価値についての感覚を決定しました。ですから、一般的な2番目の価格とは異なり、最高入札者は、彼らの入札がリザーブプライスよりも高い場合に勝ちます。
これは、敵対的な共謀を避けるのに役立ちます。例えば、個人が集団的にあまりにも低く入札するように導くことや、彼らの価値が単に不一致である場合です。ですから、これは買い手のセットと販売している人との間のその特定の問題を避けることを可能にします。そして、彼らの入札が、申し訳ありません、彼らの入札が十分に高い場合、彼らは勝ちます。そして彼らが実際に支払う価格は、リザーブプライスと2番目の価格の最大値です。
ですから、2番目の価格がより高い場合、彼らは2番目の価格を支払います。リザーブプライスがより高い場合は、リザーブプライスです。ですから、これは価値のギャップのいくつかを緩和します。また、部分的に緩和します。あなたが言ったことですが、少なくとも売り手はあなたのリザーブを少なくとも満たすことが保証されます。ですから、私たちが話した敵対的行動のいくつかを緩和します。
学生：リザーブプライスは入札者に隠されていますか？
講師：両方できます。この設定では、既知で公開されています。しかし、そうです、どちらのメカニズムも持つことができます。そして、想像できるように、異なる方法で興味深いです。情報の量について少し話します。クール、良い質問です。そうですね。文字通りの例です。いくつかの数字を手に入れました。それらは根拠づけられています。
3. セカンドプライスオークションの理論と特性
3.1 Vickreyオークションの基本構造とリザーブプライス
講師：さて、多くの人々がこれに取り組んできました。実際に多くのノーベル賞受賞者を見ることになります。経済学のノーベル賞がメカニズムデザインの種類の質問に具体的に取り組んだ分野の一つだと思います。特に、セカンドプライスオークションはVickreyオークションとも呼ばれることがあります。
1961年に行われたこの研究は、最終的にノーベル賞につながりました。そして、コンピュータサイエンスの文献でこの質問に関与するフォローアップ研究がたくさんあります。繰り返しになりますが、私たちが少し話したことのいくつかを追加しています。計算可能性のようなもの、学習可能性のようなもの、もし途中に学習アルゴリズムがあれば、異なるエージェントの戦略的行動、異なる設定、そのようなものです。
もう少し形式的に物事を設定しましょう。m個のアイテムとn人の買い手がいるとします。そして、各買い手は、アイテムのセット内のアイテムの可能なバンドルすべてに対して何らかの価値を持っています。バンドルをどのように定義しても構いません。そして時々、アイテムのセット全体にわたるこの価値のリストは、買い手のタイプと呼ばれることがあります。これは、アイテムのセット内のアイテムの可能なバンドルすべてに対する価値を列挙したベクトルとして考えることができます。
例えば、私たちのコーヒーの例では、すでに説明したように、潜在的な買い手の例があります。アイテムのセットは、コーヒーとカップケーキです。何もない場合の価値はゼロです。異なるアイテムの組み合わせすべてに対する数字があります。すでに話したように。そして、彼らのタイプは、異なるアイテムに対する価値のこのリストにすぎません。システム内のすべての異なる買い手にわたってこれを持つことができます。
販売設定では、メカニズムは2つの主要な機能によって定義されます。一つは配分（allocation）で、これはどの買い手がどのアイテムを得るかを決定するプロセスです。そして支払い（payments）は、各買い手がメカニズムに参加した後にいくら支払うかを定義します。そして述べたように、多くの場合、あるいは間違いなく、この設定を考えると、常に収益を測定できます。これは、繰り返しになりますが、一般的にこのメカニズムに参加したすべての買い手にわたる支払いの合計として考えられます。そして再び、あなたはこれを最大化したい目標として考えるかもしれません。あるいは簡単に言及した他のものを持つことができます。それらが最大化したいものです。
メカニズムの詳細によりますが、多くの場合、買い手は好きなものを入札できることも述べておく価値があります。述べたように、多くの場合、彼らは戦略的である動機があるでしょう。このため、彼らはアイテムの真の価値ではない何かを入札するかもしれません。
ですから、これの意味といくつかのことについて話します。買い手がバンドル、アイテムのセットに対する真の価値を入札する可能性を高めるためのメカニズムの設計について知られていることです。
3.2 インセンティブ両立性（IC）の証明と戦略分析
講師：さて、あなたが望むかもしれないいくつかの特性があります。そしてメカニズムを設計する際に欲しいと考えられる核心的なものの一つです。一つは、社会選択で簡単にカバーしました。インセンティブ両立性（incentive compatibility）のアイデアです。
これはエージェントに動機を与えて、彼らの真の価値を入札するようにします。彼らは真実を入札する可能性が高くなります。これには複数の潜在的な意味がありますが、デザイナーとしての私たちの目的からすると、多くの場合これが私たちの目標です。そして、これを純粋にこの経済的収益最大化の意味で考えることができます。
常にこれを選好を引き出すという観点から考えることもできます。真の価値、アイテムに対する真の価値として考えることができます。そして、これはあなたがこの引き出しメカニズムで興味を持つかもしれない目標のようなものです。メカニズムに欲しいと思うことが多いもう一つのことは、これは多くの場合買い手の視点からですが、個人合理的（individually rational）であることです。
ですから、もしあなたが戦略的で、メカニズムに参加することについて最大化しようとしているか、何でもしようとしているなら、理想的には、メカニズムに参加することで失うものが何もないように物事を設定したいでしょう。参加しない場合と比べて。基本的に、これは彼らがメカニズムに参加することを選択するための参入障壁を減らします。ですから、これについて少し話します。
インセンティブ両立性も別の標準的なアイデアです。ですから、2007年のもう一つのノーベル賞です。1972年にHurwiczによって最初に導入されました。そして再び、述べたように、形式的には主に経済学文献でしたが、その後、コンピュータサイエンス文献を含む多くの他の文献にわたってかなり取り組まれてきました。
形式的に言うと、主張を述べて、その主張の非形式的な証明と、興味があれば形式的な証明へのポインタを示します。非形式的な主張は、セカンドプライスオークション、私たちが簡単に話したものは、入札のセットを集め、勝者は最高入札を持つ人で、彼らが支払うのは2番目の価格、2番目に高い価格です。2番目に入札した人の番号です。
そしてここでの主張は、これがインセンティブ両立的であるということです。つまり、ここで買い手、すべての買い手が真実に入札することで自分の効用を最大化するということです。ですから、ここでの主張は、もし私がこれをオークションメカニズムとして選ぶなら、買い手は真の価値を入札する動機があり、母集団の意味で、実行にわたって、戦略的になって真の価値とは異なる何かを入札しようとすることでより良い結果を得ることはできないということです。これを見ていきましょう。
ここでの効用は、繰り返しになりますが、彼らが最終的に勝つ特定のアイテムに対して彼らが置く価値から支払いを引いたものとして測定されます。ですから、このギャップに、彼らが勝ったかどうかの選択の指標を掛けたものです。ですから、一連の設定で、単一の勝者がいると仮定すると、これは単に、勝者の価値マイナス支払いが個人の効用です。これを母集団にわたって平均できます。
では、なぜこれが真実かもしれないのでしょうか？いくつかの戦略について話しましたが、自分の価値より高く入札すべきか、自分の価値より低く入札すべきかというバージョンがありました。最初のものについて話しましょう。一つのアイデアは、実際に支払う必要があるものを入札するのではないことを知っているので、戦略的に自分の価値より大きく入札することです。2番目の価格を支払うつもりです。
では、なぜそれをしないのでしょうか？もし彼らが最高の価値を持っていたために勝者だったなら、彼らは真の価値より高く入札するかどうかにかかわらず、まだ勝者です。これを明確にするために。アイテムに入札した一連の入札者がいるとします。この線上に、アイテムに対して何らかの価格のセットを入札した一連の入札者がいるとします。
このリストで、個人kがアイテムに対して最高の価値を持っていたのでこのオークションの勝者になるとします。もし彼らが真の価値より高い何かを入札したなら、彼らは他の状況と比較してまだ勝つつもりですし、価格は変わりません。ですから、彼らは真の価値より高く入札するというこの追加の作業をしても何も得られませんでした。
ですから、ここでの主張は、再び、とにかく勝者だったであろう設定では、何かより高いものを入札することによる追加の利益はないということです。別に、もし彼らが入札を失うつもりだったなら、つまり他の誰かがアイテムに対してより高い価値を持っていたなら、彼らは自分の価値より高い何かを入札することで勝つことになるかもしれませんが、その場合彼らは自分の価値より多く支払います。
そして、このギャップは正から負になります。効用は負になります。これが機能するかどうか見てみましょう。私が好きな時に機能します。そして今、機能していません。カーソルを試してみましょう。さて、効用のこの評価、つまりアイテムに対して彼らが真に評価するものと彼らが支払うもののこのギャップは、正であると仮定されています。なぜなら、アイテムの価値以下を支払っていると仮定しているからです。
しかし、もし彼らが本当に高く入札したなら、他の全員が好きなように入札できます。そして、彼らが高く入札したなら、2番目の価格の勝者も彼らの価値を上回っている可能性が高いです。そして、彼らは価値より多く支払うことになります。ですから、その状況では負の効用を持ちます。そして、個々の入札者の視点から、ここでの主張は、非形式的に、再び形式的に述べることができますが、このメカニズムで価値より高く入札することによる利益がないということです。個々の行為者の視点から。
もう一つの戦略は、戦略的に、ここで「戦略」という言葉を使いすぎていますが。あなたは低く入札することを選択できます。何が起こるかを見ていきましょう。ですから、再び、議論できます。彼らが勝者だったとします。ですから、彼らは全員の中で最高の価値を持っていました。今、彼らが真の価値より低く入札すると、彼らの真の価値は、真の価値で入札することを選択する他の誰かより高い真の価値を持つ人よりも低くなるかもしれません。そして、彼らはオークションを失うことになります。そして再び、彼らはゼロ効用を得ます。ですから、参加者または買い手の視点からの観点で再び、あなたは正の効用を持つつもりです。価値は支払うものより高いです、ゼロ効用を持ちます。
単純に、彼らが勝たないか、彼らが価値と同じだけ支払うと考えることができます。または負の効用を持ちます。あなたは価値より高く過払いします。
そして議論は、もしあなたがこれを最大化しようとしているか、あなたへの決定とそれらの影響が何であるかもしれないかの違いを最大化しようとしているなら。ですから、もしあなたがあまりにも低く入札すると、あなたは他の方法で勝ったかもしれないオークションを失うかもしれません。
そして、あなたはオークションを失うことから負の効用またはゼロ効用を得ることになります、申し訳ありません。別に、もしあなたがとにかく負けるつもりなら、他の人々があなたよりもそれに対してより高い価値を持っているので、あなたはまだ負けるつもりです。リアルタイムでそれを読んでいます。私はわずかに異なる言葉を使ったかもしれませんが、同じことです。もし彼らが負けるつもりなら、彼らはオークションに負けるでしょう。そして効用はゼロです。
ですから、彼らの個人的な戦略的視点からは、本質的に彼らはより良い結果を得られません。ここで議論されているように、戦略的に低く入札することを選択することでメカニズムに参加しても、または前のスライドで議論されたように高く入札しても。考えや質問はありますか?
わかりました、セカンドプライスは、再び、オークションに関連する何かに関わったことがあるなら、ほぼ間違いなくそれについて聞いたことがあると思います。この特性、特にこの特性が、より成功した戦略の一つになるように導いたと思います。少しでこれに到達します。多くの検索メカニズムがセカンドプライスを使用することが判明します。それらが完全に一致しているわけではなく、セカンドプライスが入札されている単一のアイテムに対するものであることが判明します。
一方、検索設定では、通常、アイテムのバンドル上で入札しています。ですから、それが判明します。私たちはそれに2分間費やしますが、そこには不一致があります。とはいえ、セカンドプライスは実際に大きな影響を与えており、本質的に主導的なオークションメカニズムです。部分的にこの主張、このアイデアのためです。合理的な購買エージェントにとって、彼らの最良の行動はアイテムに対する真の価値を入札することです。
ですから、戦略的に、価値より高く入札しようとすること、または戦略的に価値より低く入札しようとすることは、母集団設定では、彼らが真の価値を入札した場合よりも悪い結果になることを意味します。
学生：はい？それは販売するアイテムに対しても最良のことですか？
講師：必ずしもそうではありません。そして実際、私たちは2秒でこれに到達します。いいえ。
ですから、ここでの主張、質問は私が理解する限り、セカンドプライスは、最大の、例えば収益を最大化しようとしている場合の収益の観点で最適なメカニズムですか、ということです。そして答えはノーです。単一アイテムオークションの種類の入札に対して。しかし、それはこの特性を満たすことに対しては最適です。しかし、収益最大化メカニズムではありません。それは正しいです。
3.3 個人合理性（IR）と参加のインセンティブ
講師：さて、別の特性、私たちが簡単に述べたものは、この個人合理性のアイデアです。ですから、セカンドプライスの別の良い特性は、それが個人合理的であるということです。主張を再び非形式的に述べます。そして、より注意深く読みたい場合や形式的な証明を得たい場合は参考文献を示します。主張は、各入札者は、彼らが真の価値を入札することを選択した場合、参加しない場合よりも参加して悪い状況になることはないということです。
ですから、再び、参加するか参加しないかの個人的な合理的選択の観点で言うと、彼らは、アイテムのセットに対する真の価値を使用するつもりであれば、参加することを選択することで何も失いません。彼らが関与するつもりであれば、です。それを繰り返しました。これを見る方法は、アイテムの最終価格が彼らの価値より低い場合、彼らは何も支払わないか、彼らの支払いは価値より小さいです。
申し訳ありません。実際、それが主張です。そうですね。ですから、何も支払わないか、支払いは参加した場合のアイテムの真の価値より小さいです。なぜなら、再び覚えておいてください、もし彼らが真の価値を入札したなら、彼らはオークションに勝って2番目の価格を支払うか、またはオークションを失うかのどちらかです。ですから、彼らは正の効用を持ちます。または彼らはオークションを失いますが、アイテムに対してより高い価値を持つ誰かがオークションに勝つでしょう。
そして、戦略的に、これに関与する観点で、彼らが真の価値を使用することを選択する限り、彼らは関与することを選択することで何も失いません。明確ですか？少し言葉のサラダのような感じがします。それで十分に明確に伝わっていることを確認したいです。クールです。
さて、しばしばこれらの分析が行われる方法でもう少し形式的に言うと、もう少し多くの情報が必要です。一般的に、入札者の価値を確率分布によって定義されたものとして考えることができます。ですから、これらを潜在的なアイテムのセットのバンドル上のいくつかの分布からのサンプルとして考えてください。そしてその観点から、IC特性を分析できる多くの異なる方法があります。最初のものは、しばしば呼ばれるものです。私はこれらを定義としてリストするだけで、詳細には関与しません。
ここから得られる主なものは、各入札者が持つかもしれないメカニズムの残りについての異なるレベルの情報、エージェントが持つかもしれないものです。一つの分析は純粋に分布的です。ですから、すべての入札者からのアイテムにわたる価値についていくつかの分布を想定します。
そして、これはしばしばex-ante ICまたはインセンティブ両立性と呼ばれます。ですから、ここでのメカニズムの目標は、価値がサンプリングされる分布の知識が与えられた場合、入札者の価値にわたる期待において真実性を保証することです。わずかに強い概念はex-interimと呼ばれます。今度は、入札者は自分の価値と他者の価値の分布を知っています。そして、この設定でさえ、何らかの真実性の概念が支配戦略であることを望みます。
このメカニズムに関与するために行う最良のこと、それはex-interim ICと呼ばれます。そして最後に、ex-postと呼ばれる用語があります。ex-post ICがあり、それは最も強いバージョンとして考えることができます。ですから今、私は分布を知らず、全員の実際の入札を知っています。または実際にはノー、申し訳ありません、全員の実際の価値を知っています。
私は本質的に、全員がすべてのアイテムに対して何を評価しているかを知っています。そして、あなたはまだ望むでしょう。あるいは、入札者がその設定でまだ真実である動機を持っているべきだと期待するでしょう。ですから、これを、入札者が知るかもしれない異なる量の情報、そしてこれらの異なる種類の設定でのICの定義として考えることができます。
そして、インセンティブ両立性に関する文献を見ると、これが見られます。さて、世界には多くのメカニズムがあり、異なる種類の価格設定システム、私たちが話した選択肢があります。推測ですが、一般的にファーストプライスです。その多くは、推測ですが、インセンティブ両立的でないことが知られているか、いくつかの設定では、それらは十分に複雑で、完全な分析がまだ行われていないため、それらがそうであるかどうかは知られていません。
一般的なもの、ファーストプライスオークションのようなもの、これは多くのディスプレイ広告が使用するものです。ですから、勝者は多くのディスプレイ広告に対して彼らが入札した価格を支払います。そして、これを持っていない場合、これが意味するのは、戦略的な行為者が、あなたが販売しているものに対する真の価値ではない入札を選ぶことでより良い結果を得るかもしれないということです。
ですから、再び、それは潜在的な損失です。インセンティブ両立性を持っていないことに対するメカニズムの潜在的なコストは、参加者が真の価値を入札する動機があるという主張または保証を失うことです。ファーストプライスオークションのようなもの、私たちは簡単に話しました。多くのスポンサー付き検索広告、Googleが使用するようなものは、一般化セカンドプライスオークションと呼ばれます。
主な違いは、再び、ファーストプライスの主張は複数の入札者と単一アイテムに対するもので、検索広告では、検索広告の複数の配置の順位付けと複数のアイテム上で入札しています。そして実際には、一般的に。ですから、次のことが知られていると思います。人々はまだほとんどの検索広告でとにかく一般化セカンドプライスオークションを使用します。人々は、一般化セカンドプライスオークションを有利にできる戦略があることを示しています。
ですから、それはインセンティブ両立的でないことが知られています。それでも、それはおそらくまだ最も人気のある展開されたアルゴリズムだと思います。ですから、それはおそらく興味深い、楽しい認知的不協和です。それは私たちが望む強い特性です。非常に強い保証を持つ設定から着想を得たアイデアがあります。人々はそれをこの新しい設定に移します。保証は失われますが、実際にはまだ使用されています。
そうですね。そしてまた、他の多くの、より複雑な組合せオークションやそのようなものは、インセンティブ両立的でないことが知られているか、分析が不完全であるため知られていません。問題のいくつかには、価値を見つけ出すことが計算コスト的に高価かもしれないということが含まれます。
ですから、これは計算的な議論です。ルールと説明の容易さの問題もあります。入札プロセスとオークションメカニズムの間に何らかの情報漏洩があるかもしれません。ですから、例えば、将来どのように入札するかを調整するために、入札を使用して機能やパラメータを調整することは、多くの場合、物事を変えます。メカニズムがどのように正確に設計されているかによります。またはエージェントがリスク中立でない場合によります。
そして、全体の前提が実際に私たちがメカニズムに参加するエージェントについて行っている仮定を無効にします。さて、文献には多くの研究があります。これも特性として述べましたが、インセンティブ両立性の近似的な概念についての主張を試みる多くの研究もあります。それからの何らかの逸脱の測定です。
全く関与したくありませんが、興味があれば、近似ICの他の概念についてより詳細を得るための参考文献を示します。さて、それがインセンティブ両立性について言いたいことのほとんどです。個人合理性についても同様のことを言うことができます。純粋にここで言うと、ですから、覚えておいてください、ここでは、入札者があなたのメカニズムに参加することを選択するか、しないかについての議論です。そして、IRメカニズムは、各入札者が参加することを選択して悪い状況にならないという特性を持っています。
そして、これを再び、異なるレベルの入札者情報で分析できます。次に行きましょう。さて、実際に収益を最大化することについて質問がありました。ですから、これは単一アイテムオークションに対して知られています。ですから、これはMyersonによるものです。別の、3つ目のノーベル賞だと思います。このクラスには3つしかなかったと思います。
これに関連する他のものがあるかもしれません。ですから、1981年に、収益最大化単一オークションを示しました。これはやや複雑なセカンドプライスです。2秒で話します。
4. IC特性の形式的分析と実際のメカニズムの課題
4.1 Ex-ante、Ex-interim、Ex-post ICの定義
講師：一般的に、入札者の価値を確率分布によって定義されたものとして考えることができます。ですから、これらを潜在的なアイテムのセットのバンドル上のいくつかの分布からのサンプルとして考えてください。そしてその観点から、IC特性を分析できる多くの異なる方法があります。最初のものは、しばしば呼ばれるものです。私はこれらを定義としてリストするだけで、詳細には立ち入りません。
ここから得られる主なものは、各入札者が持つかもしれないメカニズムの残りの部分についての異なるレベルの情報、エージェントが持つかもしれないものです。一つの分析は純粋に分布的です。ですから、すべての入札者からのアイテムにわたる価値についていくつかの分布を想定します。
そして、これはしばしばex-ante ICまたはインセンティブ両立性と呼ばれます。ですから、ここでのメカニズムの目標は、価値がサンプリングされる分布の知識が与えられた場合、入札者の価値にわたる期待において真実性を保証することです。わずかに強い概念はex-interimと呼ばれます。今度は、入札者は自分の価値と他者の価値の分布を知っています。そして、この設定でさえ、何らかの真実性の概念が支配戦略であることを望みます。
このメカニズムに関与するために行う最良のこと、それはex-interim ICと呼ばれます。そして最後に、ex-postと呼ばれる用語があります。ex-post ICがあり、それは最も強いバージョンとして考えることができます。ですから今、私は分布を知らず、全員の実際の入札を知っています。または実際にはノー、申し訳ありません、全員の実際の価値を知っています。
私は本質的に、全員がすべてのアイテムに対して何を評価しているかを知っています。そして、あなたはまだ望むでしょう。あるいは、入札者がその設定でまだ真実である動機を持っているべきだと期待するでしょう。ですから、これを、入札者が知るかもしれない異なる量の情報、そしてこれらの異なる種類の設定でのICの定義として考えることができます。
そして、インセンティブ両立性に関する文献を見ると、これが見られます。
4.2 ファーストプライスと一般化セカンドプライスオークション
講師:さて、世界には多くのメカニズムがあり、異なる種類の価格設定システム、私たちが話した選択肢があります。推測ですが、一般的にはファーストプライスです。その多くは、推測ですが、インセンティブ両立的でないことが知られているか、いくつかの設定では、それらは十分に複雑で、完全な分析がまだ行われていないため、それらがそうであるかどうかは知られていません。
一般的なもの、ファーストプライスオークションのようなもの、これは多くのディスプレイ広告が使用するものです。ですから、勝者は多くのディスプレイ広告に対して彼らが入札した価格を支払います。そして、これを持っていない場合、これが意味するのは、戦略的な行為者が、あなたが販売しているものに対する真の価値ではない入札を選ぶことでより良い結果を得るかもしれないということです。
ですから、再び、それは潜在的な損失です。インセンティブ両立性を持っていないことに対するメカニズムの潜在的なコストは、参加者が真の価値を入札する動機があるという主張または保証を失うことです。ファーストプライスオークションのようなもの、私たちは簡単に話しました。多くのスポンサー付き検索広告、Googleが使用するようなものは、一般化セカンドプライスオークションと呼ばれます。
主な違いは、再び、ファーストプライスの主張は複数の入札者と単一アイテムに対するもので、検索広告では、検索広告の複数の配置の順位付けと複数のアイテム上で入札しています。そして実際には、一般的に。ですから、次のことが知られていると思います。人々はまだほとんどの検索広告でとにかく一般化セカンドプライスオークションを使用します。人々は、一般化セカンドプライスオークションを有利にできる戦略があることを示しています。
ですから、それはインセンティブ両立的でないことが知られています。それでも、それはおそらくまだ最も人気のある展開されたアルゴリズムだと思います。ですから、それはおそらく興味深い、楽しい認知的不協和です。それは私たちが望む強い特性です。非常に強い保証を持つ設定から着想を得たアイデアがあります。人々はそれをこの新しい設定に移します。保証は失われますが、実際にはまだ使用されています。
4.3 実用メカニズムにおけるIC特性の欠如
講師:そうですね。そしてまた、他の多くの、より複雑な組合せオークションやそのようなものは、インセンティブ両立的でないことが知られているか、分析が不完全であるため知られていません。問題のいくつかには、価値を見つけ出すことが計算コスト的に高価かもしれないということが含まれます。
ですから、これは計算的な議論です。ルールと説明の容易さの問題もあります。入札プロセスとオークションメカニズムの間に何らかの情報漏洩があるかもしれません。ですから、例えば、将来どのように入札するかを調整するために、入札を使用して機能やパラメータを調整することは、多くの場合、物事を変えます。メカニズムがどのように正確に設計されているかによります。またはエージェントがリスク中立でない場合によります。
そして、全体の前提が実際に私たちがメカニズムに参加するエージェントについて行っている仮定を無効にします。さて、文献には多くの研究があります。これも特性として述べましたが、インセンティブ両立性の近似的な概念についての主張を試みる多くの研究もあります。それからの何らかの逸脱の測定です。
全く立ち入りたくありませんが、興味があれば、近似ICの他の概念についてより詳細を得るための参考文献を示します。さて、それがインセンティブ両立性について言いたいことのほとんどです。個人合理性についても同様のことを言うことができます。純粋にここで言うと、ですから、覚えておいてください、ここでは、入札者があなたのメカニズムに参加することを選択するか、しないかについての議論です。そして、IRメカニズムは、各入札者が参加することを選択して悪い状況にならないという特性を持っています。
そして、これを再び、異なるレベルの入札者情報で分析できます。次に行きましょう。
5. 収益最大化：Myersonの最適オークション理論
5.1 セカンドプライスオークションの収益上の限界
講師:さて、実際に収益を最大化することについて質問がありました。ですから、これは単一アイテムオークションに対して知られています。ですから、これはMyersonによるものです。別の、3つ目のノーベル賞だと思います。このクラスには3つしかなかったと思います。これに関連する他のものがあるかもしれません。ですから、1981年に、収益最大化単一オークションを示しました。これはやや複雑なセカンドプライスです。2秒で話します。
セカンドプライスオークションの問題は、すでに部分的に特定されているように、より強い入札者が常により弱い入札者の入札額を支払うということです。そして、売り手の視点からの収益は、参加者の価値にはるかに強く依存します。そして、売り手の視点から言うと、彼らが望むのは実際の最大入札の真の価値だと主張できるでしょう。しかし、もし彼らがそれを求めるなら、つまり最高入札額を支払うように求めるなら、インセンティブ両立性を失います。なぜなら、そこで使用できる戦略があるからです。
もしお望みなら、トレードオフを行う必要があります。売り手が望むのは収益を最大化することです、最高の価格を得ることです。もし彼らがすべての価値を知っていたなら、彼らが選ぶのは最高の価値を持つ買い手でしょう。もし彼らがそれを行うなら、それはあなたのメカニズムが脆弱であることを意味します。なぜなら、それらの買い手は戦略的になることができ、実際には他の何かを入札して、結局より少なく支払うことになるからです。
そして、この陰陽の奇妙な状況が起こっています。最高価格を支払うという明白なメカニズムは戦略的有用性を失います。しかし、戦略的に正しいことが知られているメカニズム、これは再び、セカンドプライスのものですが、収益をテーブルに残します。ですから、そこにはギャップがあるのです。そしてMyersonは代替戦略を提案し、それからこれがICを保つが、また収益を最大化することも示しました。これは比較的単純なアイデアです。
5.2 仮想価値（Virtual Values）とMyersonメカニズム
講師:分布的設定において、入札者iの価値が特定のPDFを持つ分布を持つとしましょう。Fと呼びます。0と1の間でサポートされているとします。ですから、価値が0と1の間になるように正規化するだけです。そしてこの設定で、私たちは仮想価値のセットを定義します。これは差です。ですから、これは関数的な定義です。
ですから、各個人に対する価値の分布を与えられて、私は新しい関数を定義します。その分布を取るこの関数は、そこから新しい特性を計算します。ですから、これは、私がプラグインしようとしている一つのものは価値です。ですから、私は価値の観点でこれについて話します。
ですから、価値からその個々の入札者に対する価値の分布の何らかの正規化された概念を引きます。ですから、これを計算したら、すべての入札者から入札を募集します。そして手順は、まず、すべての仮想価値、各入札者に対するすべてのアイテムにわたって計算されたこれらの量をチェックします。もしそれらがすべてゼロより小さい場合、それが意味するのは、これもまた、価値とCDF補正の間のギャップが負であることを意味します。
そうしたらアイテムを割り当てません。メカニズムは終了します。もし少なくとも一つがゼロより大きい場合、最高の仮想価値を持つ買い手にアイテムを割り当てます。そして彼らは閾値での入札を支払います。これはこの順方向関数の逆として計算されます。ですから、定義を見ることができます。これはセカンドプライスのバリエーションです。実際に言う価値があるでしょう。
ですから、この最大値は、他の全員の仮想入札をすべて計算しています。そして、勝者でないものの最大値を見ています。ですから、これは仮想入札に対して正確にセカンドプライスです。そしてそれはゼロより大きくなければなりません。これがここでの最初の基準です。
そして、価値への逆変換を行います。そしてそれが彼らが結局支払うものです。そしてMyersonが示したのは、もし入札がこのように設定されるなら、これはセカンドプライスに似た特性を持ちます。お分かりかもしれませんが、なぜなら、あなたが実際に支払う価格は他の全員の最大仮想入札だからです。彼らが勝者であると仮定して、彼ら以外の。
ですから、Myersonが示したのは、これがIC特性を保つということです。つまりインセンティブ両立的であり、最適戦略がまだ真の価値を入札することであることを意味します。それでも、これが収益最大化戦略であることを示すことができます。ですから、これは売り手の視点から、彼らが得られる収益を最大化します。すべての入札者がまだアイテムごとに持つ真の価値を入札する動機があることを保証しながらです。
単純な設定では、買い手の価値がIID、つまり同じ分布を持つ場合、これを、ファイの逆数ゼロのリザーブプライスを持つ標準的なセカンドプライスオークションに変換できることが判明します。これは見ることができます。なぜなら仮想価値はすべて互いのオフセットになるからです。
そして支払われる実際の価格はこの逆関数のように見えます。最大値はゼロです。少なくとも口語的な視点から、これがどのように接続されているかは明確だと思います。そうですね。そして同じアイテムですが、アイテムの複数のユニットについての研究もあります。そしてその設定に対する最適な、収益最大化、インセンティブ両立的選択肢をどう考えるかについてです。
5.3 複数アイテムオークションの未解決問題
講師:さて、それを超えて、単一アイテムを収益最大化の観点で最適に行う方法は知っていることが判明します。私の知識では、少なくとも私がこの文献を調べた時から今までの間に何かが起こらない限り、それはまだ真実だと思いますが、それは数分または数時間前かもしれませんが、2つのアイテムさえも最適に行う方法を知りません。
ですから、これは少し驚くべきかもしれませんが、事実の陳述として述べているだけです。これに取り組む多くの研究があり、経済側とコンピュータサイエンスの両方であります。そして、これらの質問について考える意味のある進歩があります。しかし、おそらく難しい、興味深い問題です。もし誰かが理論的に傾倒していて、本当に難しい問題を望むなら、これは楽しいものかもしれません。
そして、おそらく驚くべきことでもあります。冒頭で述べたことと、全体的な設定のいくつかの説明を考えると。
6. 機械学習とメカニズムデザインの統合
6.1 学習アルゴリズムを含むメカニズムの設計
講師:これもまた、人々がこれを機械学習の設定に接続するにつれて、ますます関与するようになります。ですから、特に、ご存知かもしれませんが、現代の、例えば広告入札インフラの多くは、その下に学習モデルを持っています。これは、例えば価格を予測したり、配置を予測したりするのを助けます。その下に多くの学習があります。
ですから、学習方法をメカニズムと接続し、それらの相互作用について質問しようとする多くの研究があります。ですから、例えば、収益と入札について質問するためにオンライン学習を使用しようとする側面があります。ですから、例えば潜在的に何度も、1週間の間に何度もアイテムを購入することを選択するかもしれない買い手について考えるかもしれません。
ですから、彼らが到着します。彼らまたは買い手の集団です。そしてアイテムに対して何らかの価格があり、彼らは購入するかどうかを選択するかもしれません。ですから、これは固定価格タイプの設定のバージョンです。冒頭で述べたように。しかし、他の種類の興味深いメカニズム内でこれを行うことも想像できます。そして、この設定で学習を行う方法に関与する多くの研究があります。
ですから、あなたが尋ねることに興味があるかもしれないいくつかの質問には、学習に関する質問、リグレットが含まれます。ご存知のように、これは主要な方法の一つです。私たちはすでに、例えばベイズ最適化の研究で、前回の講義で行ったものでこれをカバーしました。ですから、売り手にとっての累積収益と、事後的に得られたであろう最良の価格との間のこの差です。そして、これが研究されてきた多くの設定があります。
潜在的に敵対的な買い手の価値を扱う研究があります。確率的な買い手の価値、おそらくより簡単なケースです。買い手が真実に振る舞うと仮定される場合、買い手による様々な種類の戦略的行動です。他の研究、そしておそらく私たちにとってより直接的に関連するものは、買い手が入札方法を学習しなければならないメカニズムのようなものです。
6.2 オンライン学習、リグレット、入札戦略の学習
講師:ですから、彼らは時間をかけてエコシステムまたはメカニズムに参加しています。そしてメカニズムから得る信号に基づいて行動します。そして、これは売り手から得るものであり、他の参加者から学ぶものでもあります。彼らは入札方法を学習するためのプロセスを更新しようとします。ですから、例えば、これの単純なバージョンは、入札を学習する設定のようなもので、最初、買い手は各ラウンドでアイテムの価値について何も知りません。彼らは実際に勝つアイテムに対する価値のみを学習します。
ですから、彼らは何かを選択します。そして、もし彼らが勝てば、価値を学びます。もし彼らが勝たなければ、何も学びません。そして目標は、事後的な最良の固定入札と競争することです。ですから、最適戦略は、もし私が真の価値を知っていて、実際にそれらを入札できたならというものです。そして、リグレット設定は、再び、もし私が最適な固定入札を知っていたなら、その戦略からのギャップは何ですか、というものです。過去数回の講義で話したリグレットについて話した方法と同様です。ですから、同じアイデアです。
6.3 敵対的・確率的シナリオにおける学習
講師:これの他の興味深い側面には、利益不平等(Profit Inequality)の種類の問題と呼ばれるものがあります。ですから、ここでは買い手が敵対的な順序で到着し、ランダムな評価を持ちます。ですから、再び、興味深い設定です。人々は多くの興味深い研究を行ってきました。その多くは競合する学会で発表されており、学習が再びメカニズムとどのように関与または相互作用するかについて尋ねています。
秘書問題(Secretary problem)、この命名は買い手がランダムな順序で到着することを暗示することを意図しています。ですから、ここでのギャップは、再び、介入する2つの要素は、買い手が到着する順序、そして評価です。ですから、ここでの違いは、利益設定では、買い手は順序付けの観点で敵対的ですが、評価は何らかの一般的な分布です。
秘書問題では、買い手はランダムに到着しますが、評価は敵対的です。何らかの最悪ケースの概念と考えられます。そして、人々はこれらの設定で学習がメカニズムとどのように相互作用するかに関与しようとする多くの研究を行ってきました。クラスでカバーしたものにも関連しています。ですから、様々な種類の顕示選好を伴う学習について尋ねることができます。ですから、経済的意思決定ですでに議論したことのいくつかと同様です。
しかし、ここでは、個々の買い手の行動を反復にわたって観察することに結びついた価格設定について扱います。そして将来の彼らの行動を予測したい、そしてこれらの設定での価格設定のためのメカニズムが何であるかを考え抜きたいのです。ですから、多くの興味深い質問があり、その多くは学習理論的です。
ですから、いくつの訓練例が必要かというようなものです。ですから、学習設定で尋ねるかもしれない一種のサンプル複雑性の種類の質問です。アルゴリズム的な質問もあります。購買行動を捉える設定で選好関数をどのように学習するか？そして、それはメカニズム的選択とどのように結びつくか？ですから、この分野で多くの楽しい研究があります。
冒頭で述べたように、これは完全に豊かな分野です。私たちは深く関与していません。このクラスの目的のために、そして、この種の素材が興味深いと思う人々のために、深く掘り下げる機会があると思います。私がこれを実際に提示している理由は、AIにおける選好引き出しと選好最適化のタスクに対する多くの教訓があると思うからです。それは、翻訳が十分に活用されていないと思います。ですから、この文献から学ぶ興味深いことがあると思います。
7. デジタル財のためのメカニズムとペアワイズフィードバック
7.1 デジタル財における情報非対称性の問題
講師:一つの例、デジタル財の設定のためのペアワイズフィードバックオプションです。これは、少しの引き出し、オンライン学習のようなもの、少しのメカニズムデザインを混ぜたものです。ですから、これがすべて一緒になって選好推定最適化設定に来ることができる一つの例です。ですから、これはデジタル財のために動機付けられています。ですから、このクラスですでに関与したようなもの、プロンプト補完のようなもの、合成画像のようなもの、そのようなものです。しかし、広告配置や他の設定のようなものにこれを使用することも想像できます。
標準的なオークションと入札設定では、市場は明白だと思います。入札者は事前にアイテムを知ることができ、エコシステムについて何か、そして多くの場合、実際にメカニズムも知っています。ですから、彼らは多くのインフラについて知っています。
もし私がGoogle AdWordsで広告を購入するつもりなら、あるいはeBayでアイテムを販売しているなら、私はそれらのオークションシステムを構築したいです。デジタル財では、あなたは応答がどれだけ良いかを、実際に製品を完成させるまで知りません。ですから、作業が本質的に行われているのです。ですから、私は価格設定を見ています。売り手の視点から想像できます。私はOpenAIまたは他の大きな生成モデル構築者を構築しています。私は特定のプロンプト補完に対して何らかの価格を割り当てたいと思っています。
ちなみに、これは今行われている方法ではありません。あなた方全員がご存知のように。今のところ、すべてが固定価格です。オプションはありません。しかし、おそらく経済的インセンティブが補完に対する変動価格につながることを想像できます。これについて考える合理的な方法は、このようなオークションかもしれません。
もちろん、オークションの課題は、私が補完を見るまで補完がどれだけ良いかを知らないということです。ですから、私が得るすべての情報は、私がすでに実際に関与した後です。実際に、補完を得ません。実際にクエリを行って、補完があります。そして、もし私が、売り手が特定のプロンプトを完成させるかどうかを決定するための価格設定の信号を探していたなら、ある意味で、これは、買い手が特定の金額をそれに対して支払う意思があるかどうかに基づいて作業を行うかどうかを選択するというアイデア全体を無効にします。
これは明確ですか？別の難解な話です。しかしはい。ですから、もう一度、少なくとも自分のために言いますが、たとえあなた方が聞いていて、うなずいているのを見ていますが、ただの礼儀正しいうなずきではないことを願っています。ですから、メカニズムは、デジタル財の売り手がプロンプト補完のようなものをどのように価格設定するかを決定しなければならないということです。理想的には、実際にプロンプトを完成させる前にこれを行いたいでしょう。
そして、これを行うために、売り手は実際のプロンプト補完が何であるかを知らなければなりません。ですから、ここには情報の不一致があります。売り手はプロンプト補完が実際に行われるまでプロンプト補完を知らないからです。そして、彼らは補完が実際に行われるまで補完に対して持つであろう価値を知りません。つまり、買い手は事前に特定の補完を購入したいかどうかを決定できないということです。売り手は、買い手が特定の価格で買い手に売るかどうかの決定を行うことができません。なぜなら、買い手はこの特定の補完が良いかどうかを把握できないからです。ですから、この奇妙な循環的な状況があります。誰かが最初に決定を下さなければなりません。そして、この設定でどのように関与するかは不明確です。ですから、これは、再び、私たちが議論してきた多くの問題に関連しています。
しかし、主なポイントは、これが一般的なオークション設定と比較してやや独特であると主張することです。なぜなら、この追加の欠落情報があるからです。なぜなら、標準的な設定とは異なり、価格設定があり、そして実際には、アイテムは実際にはプロセスが完了するまで実際のものではありません。ですから、価格設定を少し複雑にします。やるべきではないことはわかっています。ええ、どうぞ、どうぞ。
学生:私は最近これを呼んでいます。それは文献で2つの当事者間の情報非対称性と呼ばれるために使用されています。最初、あなたはこのセットピースオークションを持っていました。
講師:ええ。
学生:その文脈での例は、ある時、彼らが絵画を売りました。そして、オークションが完了するとすぐに、絵画は自動的に自己破壊しました。
講師:ああ、私はこれを覚えています。これは最近のことです。
学生:ええ。
講師:さて、それは楽しいものです。もし買い手が事前に知っていたなら、彼らは評価を変えたかもしれないと思います。私の記憶では、これは知られていませんでした。これは驚きでした。
学生:さて。誰かがこの話を知っていますか？これは実際のことです。ですから、それはちょうど売られるとすぐに、それは実際に紙シュレッダーのようなものでした。
講師:ですから、それは自動化されました。芸術は芸術を破壊することを含みました。あなたは目の前で芸術が破壊されることに対してお金を払っています。ですから、芸術家として、あなたはこれが完全に合理的に見えるかもしれないと想像できます。しかし、買い手の視点から、これは敵対的に見えるかもしれません。しかし、ここでのポイントは、限られた情報の観点で、良い方法だと思います。
学生:ええ、しかしこれは起こります。
講師:時々、もし私がClaude Oneか何かに話しかけると、あなたは巨大なプロンプトを入れて、それは2分間考えて、それからゼロトークンを吐き出します。
学生:ええ。確かに。それは実際に非常に現代的だと思います。これを行った時にはそれは利用できませんでした。それは素晴らしい例です。確かに、この問題の。
講師:さて、何が起こる必要があるか？入札者はオファーを提出しなければなりません。そして、競争的な設定で想像できます。価格設定を強制しているものは、例えば計算リソースだとします。ですから、あなたは決定しなければなりません。あなたは10億のリクエストを得ます。あなたはこれらの小さなサブセットを決定しなければなりません。繰り返しになりますが、これは今起こっていることではありませんが、物事が使用されている方法を考えると簡単に想像できます。これは一部かもしれません。もしリソース制約があるなら、リソース制約を緩和する一つの方法は、人々の補完に対する価値に結びつけられるかもしれない適応的な価格設定を持つことです。
そして、ここでの課題は、再び、この情報非対称性です。ですから、入札者は、応答が実際に何であるかを実際に見る前に、リクエストを満たすためにオファーを提出しなければなりません。そして、背後に配分される必要があるこのリソースがあります。ですから、あなたはどの補完を行いますか？ですから、質問は公正な価格設定を決定しようとすることです。そして、理想的な設定と標準的な、あなたが一般的なオークション設定で得るほど得られないものは、再び、完全な情報を持つユーザーです。
そして、あなたは彼らの評価を形成するためにユーザー情報を改善または増加させる何らかの方法を考えたいです。そして、メカニズム全体がインセンティブ両立的であることも望みます。すでに議論したように。ですから、入札者、このメカニズムに関与している誰でも、動機づけられています。または彼らの最適戦略は補完に対する真の価値を入札することです。その時点では、彼らは持っていません。これはもちろん、課題です。
そして設定は、より形式的には、ユーザーのセットがあるということです。時刻tで、i番目のユーザーがいます。i番目のユーザーに対して時刻tでリクエストxに対するリクエストがあります。それを選択するメカニズムが存在します。到着するリクエストを満たすかどうかを。ですから、これは時刻tでi番目のユーザーに対するリクエストxです。エージェントは効用を得ます。何らかの真の効用u_itと、配分に対する報告された効用r_itです。ですから、リクエストが実際に完了するかどうかです。
そして、リクエストと報告された効用の観察のみを与えられて、オークションを設計したいのです。ここでの「良い」は、効用を最大化し、インセンティブ両立的と定義します。ですから、あなたが望むのは、再び、個人および収益効用の視点から、グローバルに最大化することです。前に述べたように。
そして個々のステークホルダーの視点から、彼らは嘘をつこうとするのではなく、実際に真の価値を述べるべきです。ですから、既存の研究の多くと比較して、ギャップのいくつかには次のことが含まれます。多くの場合、エージェントが結果に対する価値を知っていると仮定することです。先ほどの議論のいくつかで述べたように。また、特に不確実性がここで大きな役割を果たします。これらの種類の確率的生成モデル設定で。
ですから、メカニズムは今、動的である必要があります。そしてエージェントが事前に価値を知ることができない設定です。そして価値は文脈やそのようなものに基づいて時間とともに変化するかもしれません。そして加えて、結果は様々な方法で不確実かもしれません。ですから、想像できるように。ですから、これは挑戦的な問題です。そして少なくとも今日カバーした既存の標準的なメカニズム設定とはやや異なります。
7.2 ペアワイズ選好を用いた価値予測メカニズム
講師:ですから、提案されるメカニズムは、ペアワイズ選好や他の種類の部分的選好に基づいています。そして、これは初期段階のループです。アイテム全体にわたる潜在的価値を学習しようとします。ですから、理想的には、関数を学習したいのです。特定の応答リクエストに対する価値を事前に予測できるような。そして、これは舞台裏の学習問題です。xを取り、価値を予測することです。
そして、戻ってくる信号は、ペアワイズ選好やサムズアップ、特定の価格設定に対するサムズダウンのようなものとして設定されます。ですから、例えば、買い手から尋ねるかもしれません。あなたのプロンプトへの補完としてこれまたはこれが好きですか？その例のクラスにいたあなた方のために言うと、私は今実際に完全に信じています。それはこのグループ全体で一様かもしれません。ここにいたあなた方、私たちはクラス内でペアワイズを行いました。そして人々はバタフライについて非常に異なるものに対して強く議論しました。ですから、個別に言いましょう、高い分散です。
あるいは、もし私がこれを合成したら、あなたは2ドル支払いますか、のような質問を尋ねることができます。サムズアップ、サムズダウン。ですから、これは様々な種類の単純なペアワイズタイプのクエリに対する低信号応答と考えられます。そして、舞台裏のメカニズムは、再び、セカンドプライス上に構築されています。しかし今、価格は事前に知られていません。私たちは価格の予測を使用しなければなりません。
なぜなら、再び、あなたは実際に尋ねるまで補完の価格を知らないからです。そして、初期学習段階があります。その後、主張には次のことが含まれます。まあ、本質的に、主張は、この設定で十分な例を見たら、セカンドプライスオファーを十分によく予測できるはずだということです。
ですから、価格設定にセカンドプライスオファーを使用すれば、望むすべての特性を満たすであろうように、価値を十分によく予測します。これらは再び、高収益とインセンティブ両立性です。ですから、舞台裏の重要なことは、ちょうど示したような応答、ペアワイズ選好、サムズアップ、サムズダウンに基づいてユーザー評価を予測することを学習することです。
そして、はい、推測ですが、それが主なものです。そして、使用される実際のメカニズムは、特定の補完に対する最高予測オファー、2番目に高い予測オファーです。ですから、現実世界のユースケースでは、メカニズムは何らかのサイロの背後にあります。ユーザーとしての私が入ってきます。私は特定の補完を求めます。私はあなたに私のxを与えます。
メカニズムは、私がそのxの補完に対して持つであろうと彼らが考える価値を予測し、この部屋の全員に対してこれを行います。その後、2番目に高い予測オファーを計算します。その後、勝者に請求します。申し訳ありません。私は勝者ではないと仮定します。そのインタラクションの勝者である誰でもです。
ですから、最高予測オファーを持つ人は誰でもオークションに勝ちます。その後、彼らは2番目に高い予測オファーを支払います。さて、これは直接価格設定に使用できるメカニズムです。ですから、物事を行う方法として。情報非対称設定のようなもの。デジタル財オークションのようなもの、または先ほど話した、あなたのオークションハウス、そして破壊されるかもしれない絵画を販売するかもしれません。
実際、その後オークションに何が起こったのか気になります。とても魅力的な話です。とにかく、それは奇妙です。私はフォローアップしていません。その話は知っていますが、残りは知りません。
学生:その絵画、バンクシーが非常に人気になったようです。バンクシーだったと思います。
講師:ええ、まさに。
学生:しばらくして、それははるかに高い価格でオークションにかけられました。
講師:なぜなら今、それは歴史的な価値を持っていたからです。
学生:ああ、興味深い。
講師:ああ、それは楽しいです。さて、おそらくそれは、ですから、推測ですが、意図的に物を破壊して価格を上げるという楽しいメタメカニズムでしょう。
学生:それがポイントです。
講師:いいえ、確かに。いいえ、確かに。ええ。そして、特に芸術のようなもので、評価がまさに個人的な評価である場合です。楽しいですね。
7.3 実験結果：リグレット削減と効用分配
講師:とにかく、ここで言いたかったのは、おそらく興味深い代替設定に適用したということです。ここでは、ユーザー補完のアイテムの価格設定を試みるのではなく、逆を望みました。ここで、私たちが興味を持っていたのは、現代の生成AIシステムの多くに対して起こる必要がある多くのことには、潜在的に有害または心理的に困難な素材、テキストと画像補完の両方のラベリングが含まれるという事実です。
そして、これに関与することを想像できる方法の一つ、そしてこれが完璧な解決策ではないことを述べるように注意したいのですが。これは、潜在的に心理的にダメージを与える補完に関与するために使用できるレバーの一つとして有用かもしれません。もしあなたが個人の危害を何らかの経済的価値に結びつけることができると考えるなら、そして再び、これは必ずしも良いアイデアであるという規範的な主張ではありません。しかし、特定の設定ではこれは合理的かもしれません。
もしそれが真実なら、人々に特定の補完に対して彼らが被るかもしれない危害にどれだけ結びついて支払うことを想像できます。ですから、もしあなたが特定の補完を行うつもりで、それがあなたに重大な危害を引き起こすつもりなら、その価格を想像できます。申し訳ありません、そのラベリングの価格は、同じ個人にとってより敏感でない補完や、異なる困難なラベリングの異なる量に対して異なるプロファイルと異なる感度を持つだけの異なる個人よりも、はるかにはるかに高いかもしれません。ですから、この質問に関与する多くの方法があります。
繰り返しますが、おそらく3回目ですが。これは興味深い提案として考えられています。すべてのための解決策としてではありません。ラベリングエコシステムをキュレートして心理的ダメージが少なくなるようにできるか、これが重要な質問だと思います。
しかし、一つの興味深い潜在的なレバーは、特定のラベリングからの潜在的な個人リスクまたは危害に適応する適応的支払いシステムを使用することです。そして、これは例えば結びつけることができます。公平性の議論をすることができます。ですから、これを公平性として考えることができます。例えば、公平性が意味するのは、あなたの支払いはそのタスクに関与することからあなたが被っているかもしれない危害の量に相関すべきだと主張するかもしれません。
そして、ここでさえ、もしあなたがただ人々に尋ねるつもりだったなら、戦略的であるインセンティブがあるかもしれないと想像するかもしれません。そして、実際にこの種の設定で個人の経済的危害または経済的に評価可能な危害を正確に評価するという同じ質問に取り組むメカニズムを考え出そうとすることを想像するかもしれません。ですから、これで対処するメカニズムの方法は、これを逆オークションとして扱うことです。
ですから、価値を負または正にする代わりに、それらは非負です。そして、収益を最大化したいのではなく、負のものを最大化したいのです。推測ですが、あなたはまだ最大化したいですが、今あなたは負のものを最大化しています。ですから、物事を得たいのです。あなたは人々が持つ負の価値の量を最小化したい、または人々が被るかもしれない負の危害を最小化したいのです。
そして、様々な種類の危険なラベリングに対する報酬にこれを適用することを検討できます。ですから、私たちはこれを適用しました。結果だけを示します。詳細のいくつかについては論文を見ることができます。ですから、ここでの重要なことは、はるかに少ない情報を使用できるメカニズムが欲しかったということです。
なぜなら、再び、情報非対称があるからです。話したように、あなたは実際に関与するまで補完を見ることができません。実際に補完を得ません。実際にクエリを行い、補完があります。そして、各ステークホルダーからの価値を学習するために必要な信号の量を減らす方法として、このすべてのペアワイズメカニズムを使用したいです。
舞台裏には、述べたように、特定の補完からの潜在的価値、この場合は負の効用を予測しようとする予測システムがあります。そして、私たちは以前と同じように、セカンドプライスのことを行います。そして、これは、あなたが想像するかもしれない他の一般的なことと比較されます。一つの一般的なことは、あなたが値を観察して、ただ回帰を行い、そこから直接予測することです。もう一つは、ステークホルダーのセット全体で一様に使用することです。そして、私たちは、ペアワイズフィードバックのことを使用して、全体的なリグレットの観点で、はるかに少ない情報を使用することを示します。ですから、最良可能配分から予測配分へのこのギャップは、一様配分よりもはるかに低いのです。個人の価値を考慮に入れないものと比べて。
また、他の種類の損失も見ました。実際、時間だと思います。ですから、Q&Aの時間はありません。いつものように残念ながら。しかし、私は急いでそれを見ていきます。ですから、再び、母集団全体で、福祉損失の特定の概念のより良い分布を持つことを示します。ですから、メカニズムデザインのルールです。ですから、参加者による戦略的行動がまだ望ましい結果につながります。ここで、私たちが主に興味を持っているのは、それが真実の引き出しステークホルダー選好または最適化とどのように関与するかです。ですから、引き出しまたは最適化、それを少し更新します。
主要な評価測定のいくつかには、インセンティブ両立性、個人合理性、そしてその後、多くの場合、それに結びついた収益または効用、または社会的福祉の他の何らかの概念が含まれます。次の講義では、Joseph Jay Williamsによる招待講演があります。彼は、A/Bテストや他の種類のオンライン学習選好最適化設定にこれらのものを使用するために関連するアイデアについて話します。さて、ありがとうございます。
また述べておくべきです。ですから、これの多くは、Elonとたくさんの他の共同研究者による素晴らしいチュートリアルから借用しています。ですから、興味があれば、その素材のいくつかを見ることを強く勧めます。そして、今Columbiaにいる Tim Roughgardenは、興味があれば、その詳細についてより多く扱う優れたコースを教えています。そして、ここでの素材は、彼がカバーするものの講義1または2にほぼ相当します。
8. 逆オークションと有害ラベリングへの応用
8.1 心理的ダメージの経済的評価
講師:とにかく、ここで言いたかったのは、おそらく興味深い代替設定に適用したということです。ここでは、ユーザー補完のアイテムの価格設定を試みるのではなく、逆のアプローチを望みました。ここで私たちが興味を持っていたのは、現代の生成AIシステムの多くに対して必要となる作業の多くには、潜在的に有害または心理的に困難な素材、テキストと画像補完の両方のラベリングが含まれるという事実です。
そして、これに対処することを想像できる方法の一つ、そしてこれが完璧な解決策ではないことを明確に述べておきたいのですが、これは潜在的に心理的にダメージを与える補完に関与するために使用できるレバーの一つとして有用かもしれません。もしあなたが個人の危害を何らかの経済的価値に結びつけることができると考えるなら—そして再び、これは必ずしも良いアイデアであるという規範的な主張ではありません—しかし、特定の設定ではこれは合理的かもしれません。
もしそれが真実なら、人々に特定の補完に対して彼らが被るかもしれない危害にどれだけ結びついて支払うことを想像できます。ですから、もしあなたが特定の補完を行うつもりで、それがあなたに重大な危害を引き起こすつもりなら、そのラベリングの価格は、同じ個人にとってより敏感でない補完や、異なる困難なラベリングの異なる量に対して異なるプロファイルと異なる感度を持つだけの異なる個人よりも、はるかにはるかに高い可能性があります。ですから、この質問に関与する多くの方法があります。
繰り返しますが、おそらく3回目ですが、これは興味深い提案として考えられています。すべてのための解決策としてではありません。ラベリングエコシステムをキュレートして心理的ダメージが少なくなるようにできるか、これが重要な質問だと思います。
8.2 個人リスクに適応した報酬システム
講師:しかし、一つの興味深い潜在的なレバーは、特定のラベリングからの潜在的な個人リスクまたは危害に適応する適応的支払いシステムを使用することです。そして、これは例えば結びつけることができます。公平性の議論をすることができます。ですから、これを公平性として考えることができます。例えば、公平性が意味するのは、あなたの支払いはそのタスクに関与することからあなたが被っているかもしれない危害の量に相関すべきだと主張するかもしれません。
そして、ここでさえ、もしあなたがただ人々に尋ねるつもりだったなら、戦略的である動機があるかもしれないと想像するかもしれません。そして、実際にこの種の設定で個人の経済的危害または経済的に評価可能な危害を正確に評価するという同じ質問に取り組むメカニズムを考え出そうとすることを想像するかもしれません。ですから、これで対処するメカニズムの方法は、これを逆オークションとして扱うことです。
ですから、価値を負または正にする代わりに、それらは非負です。そして、収益を最大化したいのではありません。あなたは負のものを最大化したいのです。推測ですが、あなたはまだ最大化したいですが、今あなたは負のものを最大化しています。ですから、あなたは人々が持つ負の価値の量を最小化したい、または人々が被るかもしれない負の危害を最小化したいのです。
そして、様々な種類の危険なラベリングに対する報酬にこれを適用することを検討できます。
8.3 公平性の観点と実装上の考察
講師:ですから、私たちはこれを適用しました。結果だけを示します。詳細のいくつかについては論文を見ることができます。ですから、ここでの重要なことは、はるかに少ない情報を使用できるメカニズムが欲しかったということです。
なぜなら、再び、情報非対称があるからです。話したように、あなたは実際に関与するまで補完を見ることができません。補完を得られません。実際にクエリを行って、補完があるのです。そして、各ステークホルダーからの価値を学習するために必要な信号の量を減らす方法として、このすべてのペアワイズメカニズムを使用したかったのです。
舞台裏には、述べたように、特定の補完からの潜在的価値、この場合は負の効用を予測しようとする予測システムがあります。そして、私たちは以前と同じように、セカンドプライスの仕組みを行います。そして、これは、あなたが想像するかもしれない他の一般的なアプローチと比較されます。一つの一般的なことは、値を観察して、ただ回帰を行い、そこから直接予測することです。もう一つは、ステークホルダーのセット全体で一様に使用することです。そして、私たちは、ペアワイズフィードバックの仕組みを使用して、全体的なリグレットの観点で、はるかに少ない情報を使用することを示します。ですから、最良可能配分から予測配分へのこのギャップは、個人の価値を考慮に入れない一様配分よりもはるかに低いのです。
また、他の種類の損失も見ました。実際、時間になったと思います。ですから、Q&Aの時間はありません。いつものように残念ながら。しかし、私は急いでそれを見ていきます。ですから、再び、母集団全体で、福祉損失の特定の概念のより良い分布を持つことを示します。
ですから、メカニズムデザインのルールです。参加者による戦略的行動がまだ望ましい結果につながります。ここで、私たちが主に興味を持っているのは、それが真実のステークホルダー選好の引き出しまたは最適化とどのように関与するかです。ですから、引き出しまたは最適化、それを少し更新します。
主要な評価測定のいくつかには、インセンティブ両立性、個人合理性、そしてその後、多くの場合、それに結びついた収益または効用、または社会的福祉の他の何らかの概念が含まれます。次の講義では、Joseph Jay Williamsによる招待講演があります。彼は、A/Bテストや他の種類のオンライン学習選好最適化設定にこれらを使用するために関連するアイデアについて話します。さて、ありがとうございます。
また述べておくべきです。ですから、これの多くは、Elonとたくさんの他の共同研究者による素晴らしいチュートリアルから借用しています。ですから、興味があれば、その素材のいくつかを見ることを強く勧めます。そして、今Columbiaにいる Tim Roughgardenは、興味があれば、その詳細についてより多く扱う優れたコースを教えています。そして、ここでの素材は、彼がカバーするものの講義1または2にほぼ相当します。
Stanford CS329H: Machine Learning from Human Preferences | Autumn 2024 | Mechanism Design
For more information about Stanford's online Artificial Intelligence programs visit: https://stanford.io/ai To learn more about enrolling in this course visit: https://online.stanford.edu/courses/cs329h-machine-learning-human-preferences To follow along with the course schedule and syllabus visit: https://web.stanford.edu/class/cs329h/ Sanmi Koyejo Assistant Professor of Computer Science, Stanford University View the entire course playlist: https://www.youtube.com/playlist?list=PLoROMvodv4rNm525zyAObP4al43WAifZz
youtu.be
