一般的なマッチング、または応募者と結婚して配布する方法

実際には、オブジェクトまたは人を互いにペアで配布するという問題がしばしば発生します。 たとえば、空席による従業員の分布、委員会の形成、大学への志願者の分布。 今日の講義は、個人の好みを考慮に入れて、そのような分布のメカニズムを構築する理論と実践に捧げられます。 Yandexの支援を受けてHSEで開かれたコンピューターサイエンス学部で読まれました。







講師-Sofya Gennadyevna Kiselgof 、HSEの分析および意思決定のための国際研究所のジュニア研究員。 経済学部数学科講師。 彼は、コンピューターサイエンス学部でオペレーションズリサーチとゲーム理論のコースを教えています。 彼女は「線形注文ではない選好との一般化されたマッチング」というトピックに関する論文を擁護しました。 ソフィア・ゲンナディエフナは、ロシアの大学に志願者を登録するメカニズムの研究を実施し、その結果、大学を選択するときの志願者の行動を記述するモデルが構築されました。



カットの下-講義の詳細なトランスクリプト。



私が理解しているように、経済学はこのセミナーのトピックではありません。多分私はここで通常聞こえるかもしれないことを少し得るでしょう。 しかし、トピックは非常に魅惑的であり、またはトピックのサブタイトルであるため、完全に公開できるかどうかはわかりませんが、試してみます。 実際、一般化されたマッチングと呼ばれるものについて話を始める前に、経済のセクションについて少し言いたいと思います。それは経済の概念よりも広く、社会メカニズムの開発などの一般的な社会科学です。



問題の記述は、特定の目標を達成するメカニズムを開発するエンジニアに対する問題の記述に似ています。 たとえば、荷物を持ち上げる必要がある場合、必要な高さまで最小限の労力でこれを行うメカニズムを考え出します。 しばらくの間、経済学者は、経済主体、つまり人々、企業、組織、企業などの相互作用のメカニズムを考え出すようなタスクを提起し始めました。それは、個々の経済主体がそれぞれの特性に従って振る舞うという条件で、望ましい結果をもたらします。自分の利益を追求します。 一般に、タスクは次のようにメカニズムの開発で定式化されます。未知の特性を持つエージェントがプレイする特定のゲームを開発しています。 メカニズムの開発者のタスクは、ゲームのルールを考え出すことです。参加者はそれぞれ、自分の利益のために（利己的または協力的）独特の行動をとって、「良い」結果になります。



残り2つの質問があります。 まず、通常、参加者については何も知りません。いくつかの前提があります。 そして、「良い」結果を意味する2番目は、メカニズムの開発者によってすでに決定されています。 経済的および社会的側面では、このタスクは多くの場合より困難です。 誰が開発タスクを設定するかによって、望ましい結果が異なる場合があります。



今日は、メカニズムの開発で考えられるすべてのタスクについては説明しませんが、一般的なマッチングのトピックについて説明します。 誰もがマッチのマッチングのタスクに精通していると思います。 2部グラフがあり、このグラフで最も単純な一致を見つける必要があります。つまり、エッジのサブセットを見つけて、その数が最大になり、頂点の各サブセットに1つのエッジがあるようにします。 この問題はよく知られていますが、最終的なマッチングにこれらの接続を含めることが望ましいため、これらのエッジにいくつかの重みを割り当てることができる場合、さまざまな変更があり、タスクは機能を最大化するという点で最適化に変わります。 これにより、さまざまな社会経済的状況の現実により近いタスクになります。



古典的な設定では、この問題はグラフの頂点のサブセットの「労働者、欠員による労働者の男女間の分布」と呼ばれることがあります。 本質的に、グラフの頂点のサブセットで形成される可能性のある接続を除き、それらのプロパティはいずれも問題を解決する際に考慮されません。 タスクを設定する特定の中央計画者がいます：最大数のペアを置くと、この問題は解決されます。 これらのピークが、中央の主催者の影響の外で、フレームワークの外で行動する独立した目標とタスクを持つ経済エージェントに対応する場合、参加者は受け取ったものに不満があり、選択の自由がある場合、離散数学からの通常のタスクは機能しなくなります不幸になるだけでなく、積極的に不幸になる、つまり、提供されたものを拒否する。



実際、一般化された一致を検索する問題のまさに声明は、オブジェクトの好みを設定するという点で、グラフで最大一致を見つける通常のタスクとは異なります。 これらのメカニズムは実際に実際に使用されており、特に結婚式を開催する場合は、おそらくその理由を推測できます。それらを男性と女性と呼ぶ場合、これらのオブジェクトについて話す方が便利です。



この例では、2番目の男性M2が女性W2または女性W4とペアリング（ダンス、結婚）できることがわかっています。 一般化されたマッチングのタスクにより、この男性は自分の好みを伝えることができます。 これらの結婚をしたり、ダンスをさせたりする特定の中央計画者がいます。そうすれば、彼は自由人として、そのような申し出を単に拒否します。 最も単純なケースでは、すべての男性と女性がすべての潜在的なパートナーを合理化できます。



一般的に言えば、「経済」という言葉が聞こえるので、彼らはそれらを整理するだけでなく、ルーブルでいくつかの値を設定することはできません。 実際にそれを行うことができます。 これを結婚に適用すると、深刻な考えと見なされるよりもむしろ笑顔をもたらします。 さまざまな理由で、この通貨要素が間違っていて、理論モデルに追加できる状況がいくつかありますが、実際の人々では：a）これらの推定値を定式化できない、b）何らかの理由でそのような関係を翻訳できたとしても金銭的な形では望ましくないと認識されています。 したがって、このセクションでは、ユーティリティ関数または定量単位ではなく、任意のバイナリ関係によって優先度が与えられるエージェントを扱います。



つまり、一方ではこれは制限ですが、他方では、この制限がないと、問題は根本的に変わります。 そして、一般化されたマッチングは、男性と女性の一般化と呼ばれます。男性と女性は誰とペアになり、単純な場合、各男性は1人の女性とのみペアリングされ、各女性は1人の男性とのみペアリングされます。 そして、誰かが放っておかれるかもしれません。 すべてがいつも通りです。



このタスクで理解した場合：一致の最大数を構築し、エージェントの好みを考慮したい場合、メカニズムの開発者の観点から目標とすることができます。 これは正式な定義であり、研究者によって策定された一連の願いです。



ここで必要なのは、2つの非常に単純なことです。 第一に（個々に合理的）：男性を容認できないと考える女性とペアにするべきではありません。 彼女とペアにすれば。 それから彼は、自由人として、私たちのシステム全体を壊して去ります。 2番目の要件（ペアワイズ安定性）も非常に簡単です。 右の図のようにペアが形成されている場合。 最初の男性は最初の女性とペアになっています。 2番目の男性は2番目の女性とペアになっています。 何が問題なのか。 最初の男性は、2番目の女性が私たちのディストリビューションが彼に提供した潜在的な配偶者よりも彼にとってかわいいと主張しています。 そして、2番目の女性は、最初に与えられた男性よりも最初の男性の方が望ましいと考えます。 彼らが無料の市民である場合、これら2つは逃げ出し、提供されたものではなく、赤のカップルを作成しようとします。



私はそのような状況を観察したくないので、写真を禁止し、ブロックペアがないように構築します（最初の男性と2番目の女性はブロックペアと呼ばれます）、彼らは分布を見た後、彼らがそれをブロックするので同意します。 これらは二つの願いです。 そのようなマッチングはいつでも構築できるため、男性と女性の好みが順序付けられた行で与えられている場合、これらの2つの要件を満たすことができるマッチングを常に構築できるため、これらは非常に制限的ではないことがわかりました



さらに、これはすべてGaleとShapleyによって設定された最初のタスクの結果です。 彼らは、この一致を見つけることができるメカニズムを正確に提案しました。 次のように機能します。 理論レベルでは、男性と女性のグループは対称的であるためです。 最初のステップで、男性は自分が一番好きな女性にオファーをします。 結婚したくない人がいる場合、彼は考慮されません。 一部の女性は、一度に複数のオファーを受け取ることができます。彼女は何をしますか。彼女は受け取ったすべてのオファーを検討し、最も気に入っているオファーを選択します。 彼女が一番好きな男を選びます。 そして、彼女は彼の申し出を受け入れますが、一時的に。 他のすべての男性は、彼女との結婚は不可能であることがわかり、さらに行動を開始します。 2番目のステップで、話は繰り返されます。男性はリストの次の女性にオファーをします。 繰り返しますが、いくつかの女性はいくつかの申し出を受けるかもしれません、彼女は再び最高のものを選びます。



私が言いたいのは、まだ経済的要素について心配していることだけです。 さて、私たちは実際の生活やコンピューティングの観点からそれを実装するためのそのようなメカニズムを提案しました。参加者の好みが必要です。 私たちは彼らの頭の中に何があるのか​​わからないので、彼らが私たちに真実を語るかどうかという疑問が生じます。 質問：彼らは真実を語りますか？ 良い答えは、そうです-彼らはそうしますが、残念ながら、彼はそのようではありません。 提供する男性とメカニズムを考えると、男性は真実を語ることに興味があります。彼らにとって弱い支配的な戦略は、本当の好みを伝えたいということです。 彼らは何か他のものを報告するかもしれません。 これは結果を変えたり悪化させたりしません。 残念なことに、これは女性については言えません。なぜなら、女性はメカニズムに誤った情報を提供したので、結果を改善できるからです。 最初に。 彼らが自分の利益のために操作する場合、構築されるマッチングは初期設定の下で安定します。 嘘をついたとしても、女性は明らかに男性を犠牲にして自分の立場を改善したので、マッチングは持続可能だろうが、判明した結果はまだ安定している。



さらに、選好をうまく操作するために、女性は他の全員の選好に関する情報を必要とします。 このストーリーは、プリファレンスのみに基づいて最大一致数を検索します。 実際には、1対多のタスクは興味深いものです。 それは条件付きで「入学者および大学」の観点から説明されています;実際、このタスクは実際に志願者および大学に適用されます。 しかし、それは志願者や大学だけではありません。 違いがあります。 すべては男性と女性と対称的でした。男性は女性1人と結婚し、女性は男性1人と結婚しました。



志願者が1つの大学に入学すると、その大学は一定のクォータを設定し、志願者を最大の場所に登録します。 さらに、入学の管理数ではなく、応募者を選択するための特定のメカニズムがあると言えます。 受信桁はこのようなものです。 オリンピアードが多数ある場合は、管理番号よりも多く受け入れます。 延期受諾のメカニズム、プロパティなどを含むすべてが、クォータだけでなく、ある種の選択機能、登録済み申請者のサブセットに対する選好がある場合に拡張されます。



ここで、持続可能なマッチングの定義が定式化されます。 要件は非常に似ており、個々の合理性です。 軍隊に行くよりもひどく勉強している大学で勉強するために申請者を送らなければなりません。 そして大学にとって：大学がそのような志願者の教育がこの場所を満たさないよりも悪いと信じているなら。



追加要件：ブロックペア。 ブロッキングペアの可能性があるもの。 男性や女性と同じカップルになることがあります。 イワノフは参入したペトロフよりも優れているので、イヴァノフ、「火」ペトロフを選択します。 現実にはこれがあらゆる種類の官僚的な理由で起こるという事実ではありません。 2番目のオプション：Ivanovはモスクワ州立大学で勉強しており、HSEに行きたい、空きスペースがあり、HSEがIvanovを勉強する価値があると考えている場合、IvanovはHSEに行く必要があります。 そのような要件は、持続可能性の概念の拡張であり、そのようなマッチングが存在し、同様のメカニズムを使用して構築できます。最後の例では、男性が女性に申し出を行い、ここで志願者が申し出をすると、大学は多くの志願者から申し出を受け入れます。 多くの問題では、安定したマッチングを構築するメカニズムはどの大学でも選好を操作できるため、選好を操作するという観点からの生活はさらに損なわれます。「大学-大学」分布の応用問題について話し始めるとき、大学は彼女は自分の好みが内部試験である「単一試験」によって設定されているため、操作することができません。つまり、私は最初に試験を実施し、申請者の結果を調べてから申請書を提出します 。 したがって、この試験の採点の段階で操作することはほとんど不可能です。なぜなら、私は応募者の好みについて何も知らないからです。 大学側の操作の問題は理論的ですが、情報の制限などのために実際的な問題を引き起こすことはありません。



例については、すべて使用されています。 卒業生の配布システム-病院へのインターン。 理論的なメカニズムは偶然に発明されたもので、実際に実際に適用されています。 幼稚園での子供の分布。 その他。



最初の国民居住プログラムから始めましょう。 分布はどうですか。 医師は大学での勉強を終えた後、医療免許を取得するために、まだインターンシップを受けなければなりません。 これは仕事であり、彼を雇用する医師会と契約が結ばれます。 大学および病院の流通システムは、今年の卒業生との契約に署名するための単一の日付を確立することを提案しました。 マイルストーンが設定されると、すぐに最も精通した病院幹部は、できるだけ早く最高の卒業生を獲得するために、これらの日付の前に契約を締結しようとしました。 これはすべて電話で行われ、インターネットはありませんでした。 Unified Medical Associationはさまざまな方法を使用しました（確立された日付より前にオファーを行うことを禁じた名誉規定、さまざまなアルゴリズムを使用）。 彼らは約6年間苦しみ、その後集中治療を提供し始めました（各卒業生は仕事をしたい病院への希望を表明しました）。 病院は、誰が服用したいかを報告しました。 最初に、マッチングを構築するメカニズムが提案されました。 事実の後の研究者が彼らが提案したメカニズムを分析したとき、彼らは彼がディストリビューションを構築したが、不安定である、つまりブロッキングペアが形成されたことがわかりました。 このメカニズムは2年も続きませんでした。 好みや空き場所に関するオープンな情報がない場合、このメカニズムは機能しませんでした。 それはすべて、契約の予備的な結論に帰着しました。



1952年、彼らは病院が提案を行い、このメカニズムが修正されたときに受け入れが遅延するメカニズムに相当する複雑なメカニズムを思い付きました。 このメカニズムは1990年代初頭まで機能していました。 女性はすべてを台無しにしました。



すべてが始まった1950年代には、解放のレベルは低く、女性の3〜5％でした。 1980年代までには、約50/50でした。 家族が形成され始め、家族の好みは一人の好みではなく、はるかに複雑です（同じ地域にいるために、各配偶者の個人的な利益が考慮されます）。 そのようなカップルは、1つの場所で仕事をするために回避しようとしましたが、ここには誰にも何も負わない民間の診療所や卒業生が現れているため、病院には、中央集権的な手順で場所の一部を宣言せずに、システムをバイパスするように人々と手配する権利がありました。



理論モデルに関与した研究者のエリオットとピランソンは、問題の解決に参加しました。 理論的な観点から、彼らの結果は悲しかった。 夫婦の選好という点では、安定性はまったくないかもしれません。 持続可能なマッチングが存在する場合、それらを構築するメカニズムを考案しました。 または、彼は見つけたブロックペアの特定の数で停止します。 1998年、彼らは実装を完了し、メカニズムが不安定なマッチングで停止することはなかったことを発見しました。



大学の入学者の言葉に戻ると、中央集権的な入学制度がさまざまな国で使用されています。 そのようなシステムが存在するためには、統一された国家試験または単一の評価システムは必要ありません。 これは予備的なインタビューかもしれません。 操作の問題に戻ると、大学はインタビューした相手のランキング段階で選好を操作しません。 , . .



, , , ? : , .



, — « », , . – , , . , , , , - , , , .



: , , . ? , , . , , , , , . , . : , . . , , - , - - , . , . , , . , , . , : 1- 2- , 2- 1- , , , , , . , , .