Loading article…
延期承認オークション（DAA）は、最も魅力のない入札を繰り返し拒否することによって割り当てを選択するオークションです。これは、無線スペクトル再割り当てオークションのような複雑なオークションに特に適した戦略的特性を備えた真実のメカニズムです。 [ 1 ]より有名なVCGオークションに対するDAAの重要な利点は、DAAは入札者の連合による操作に対して耐性があるのに対し、VCGは個々の入札者による操作に対してのみ耐性がある点です。
繰延受諾オークションは、日本のオークションのようなクロックオークションと関連があり、どちらも落札できない入札を拒否し、最終的に落札しなければならない入札だけが残るように仕組みが作られている。
政府が北部と南部の2つの地域で放送権を販売したいと考えているとします。3つの事業者がこれらの権利をめぐって競争します。
政府は社会福祉を最大化したいと考えている。この場合、実現可能な配分は2つある。アリスにすべての権利を与える（福祉＝3）か、ボブに北部を、カールに南部を与える（福祉＝2）かである。評価はエージェントの私的情報であるため、政府はエージェントが真の評価を明らかにするよう促すために、真実性メカニズムを使用する必要がある。ここでは、2種類の真実性メカニズムを比較する。
ヴィックリー・クラーク・グローブス（VCG）アルゴリズムは、社会的に最適な配分、すなわち両方の地域をアリスに与えるという配分を見つけ出す。アリスは、他のエージェントに与える外部性に応じて決定される価格を支払うべきである。この場合、アリスがいなければボブとカールの福祉は200万ドルであったため、アリスは200万ドルを支払う。ボブとカールは何も受け取らず、何も支払わない。
延期承認オークションでは、最適なアクティブエージェントのセットを維持しながら、拒否可能な最低価格のエージェントを繰り返し拒否します。そのため、最初にカールが拒否され、次にボブが拒否されます。アリスは残り、受け入れられます。その後、彼女はしきい値価格を支払います。これは、彼女が入札しても落札できたであろう最低入札額です。この場合、アリスのしきい値価格は100万ドルであり、彼女はそれを支払います。
どちらのオークションタイプも正直であり、どのエージェントも異なる値を報告しても利益を得ることはできません。しかし、エージェントが連合を形成できる場合、両者は異なります。ボブとカールが一緒に400万ドルに入札額を上げたとします。この場合、ボブもカールも単独ではアリスに何の影響も与えません。そのため、VCGオークションはボブとカールを受け入れ、それぞれに0ドルを請求します。一方、DAAはアリスを拒否し、ボブとカールを受け入れ、それぞれにしきい値価格である300万ドルを請求します。彼らはそれぞれ200万ドルを失うため、試みた戦略は報われません。
延期受諾オークションのパフォーマンスは、2014 年に Dütting らによって分析されました。彼らはナップサックオークションと単一入札者向けのオークションに焦点を当てました。[ 2 ]このアイデアをダブルオークション設定に適用したものが、同年 2014 年に、当時スタンフォード大学のコンピュータサイエンス研究者であったTim Roughgardenらによって概説されました。 [ 3 ]