論文の概要: Optimization-friendly generic mechanisms without money
- arxiv url: http://arxiv.org/abs/2106.07752v1
- Date: Mon, 14 Jun 2021 20:42:23 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-16 14:56:23.450356
- Title: Optimization-friendly generic mechanisms without money
- Title（参考訳）: お金のない最適化フレンドリーなジェネリックメカニズム
- Authors: Mark Braverman
- Abstract要約: 我々は,近代最適化アルゴリズムを,自己関心エージェントから入力を得る機構に変換するための汎用フレームワークを開発した。
この設定の特別な例としては、投票、宝くじによるアイテムの割り当て、マッチングがある。
主要な技術的貢献は、apexと呼ばれる新しいメタアルゴリズムです。
- 参考スコア（独自算出の注目度）: 8.98272353392094
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The goal of this paper is to develop a generic framework for converting
modern optimization algorithms into mechanisms where inputs come from
self-interested agents. We focus on aggregating preferences from $n$ players in
a context without money. Special cases of this setting include voting,
allocation of items by lottery, and matching. Our key technical contribution is
a new meta-algorithm we call \apex (Adaptive Pricing Equalizing Externalities).
The framework is sufficiently general to be combined with any optimization
algorithm that is based on local search. We outline an agenda for studying the
algorithm's properties and its applications. As a special case of applying the
framework to the problem of one-sided assignment with lotteries, we obtain a
strengthening of the 1979 result by Hylland and Zeckhauser on allocation via a
competitive equilibrium from equal incomes (CEEI). The [HZ79] result posits
that there is a (fractional) allocation and a set of item prices such that the
allocation is a competitive equilibrium given prices. We further show that
there is always a reweighing of the players' utility values such that running
unit-demand VCG with reweighed utilities leads to a HZ-equilibrium prices.
Interestingly, not all HZ competitive equilibria come from VCG prices. As part
of our proof, we re-prove the [HZ79] result using only Brouwer's fixed point
theorem (and not the more general Kakutani's theorem). This may be of
independent interest.
- Abstract（参考訳）: 本論文の目的は,現代的な最適化アルゴリズムを自己利己的なエージェントから入力されるメカニズムに変換する汎用フレームワークを開発することである。
私たちは、お金のないコンテキストで、n$プレーヤーの好みを集約することに集中しています。
この設定の特別なケースには、投票、抽選によるアイテムの割り当て、マッチングが含まれる。
私たちの重要な技術的貢献は、新しいメタアルゴリズムである \apex (Adaptive Pricing Equalizing Foreignities) です。
このフレームワークは、ローカル検索に基づくあらゆる最適化アルゴリズムと組み合わせるのに十分一般的である。
本稿では,アルゴリズムの特性とその応用について概説する。
この枠組みを宝くじを用いた一方的な割当問題に適用する特別の事例として、1979年のヒルランドとツェックハウザーによる均等所得からの競争均衡(CEEI)による割当結果の強化が得られる。
hz79]の結果は、(矛盾した)割り当てと、その割り当てが与えられた価格の競争均衡であるような一連のアイテム価格が存在することが示される。
さらに,需要単価vcgを高利得ユーティリティで実行するとhz平衡価格となるような,プレーヤのユーティリティ値が常に緩和されることを示す。
興味深いことに、HZの競争均衡はすべてVCG価格によるものではない。
証明の一部として、ブローワーの不動点定理のみを用いて [HZ79] の結果を再証明する(より一般的な角谷の定理ではない)。
これは独立した関心事かもしれない。
関連論文リスト
- Fair Allocation in Dynamic Mechanism Design [57.66441610380448]
競売業者が各ラウンドの買い手グループに、合計で$T$で分けない商品を販売している問題を考える。
競売人は、各グループの最低平均配分を保証する公正な制約に固執しつつ、割引された全体の収益を最大化することを目的としている。
論文 参考訳（メタデータ） (2024-05-31T19:26:05Z) - Benefits of Permutation-Equivariance in Auction Mechanisms [90.42990121652956]
競売人の収益を最大化しつつ、競売人の過去の後悔を最小限にする競売メカニズムは、経済学において重要であるが複雑な問題である。
ニューラルネットワークによる最適なオークションメカニズムの学習を通じて、注目すべき進歩が達成されている。
論文 参考訳（メタデータ） (2022-10-11T16:13:25Z) - On Scheduling Mechanisms Beyond the Worst Case [17.281501828240877]
機構Kは各入力における機構Pよりも社会的コストが小さいことが分かる。
また、メカニズムPの平均ケース近似比は、同じ定数に収束する。
論文 参考訳（メタデータ） (2022-04-14T20:57:50Z) - Fair Algorithm Design: Fair and Efficacious Machine Scheduling [0.0]
公正なアルゴリズムは低い社会福祉ソリューションをもたらすが、福祉最適化アルゴリズムは非常に不公平である。
本稿では,この二分法が,無視できる量のバイアスを許容すれば克服できることを実証する。
論文 参考訳（メタデータ） (2022-04-13T14:56:22Z) - Inducing Equilibria via Incentives: Simultaneous Design-and-Play Finds
Global Optima [114.31577038081026]
本稿では,デザイナーとエージェントの問題を同時に1ループで解くための効率的な手法を提案する。
設計者は平衡問題を何度も解決しないが、エージェントに対するインセンティブの全体的な影響を予測できる。
このアルゴリズムは,幅広い種類のゲームに対して,サブ線形速度で大域的最適値に収束することを示す。
論文 参考訳（メタデータ） (2021-10-04T06:53:59Z) - Online Learning of Competitive Equilibria in Exchange Economies [94.24357018178867]
経済学では、複数の有理エージェント間の資源不足の共有は古典的な問題である。
エージェントの好みを学習するためのオンライン学習機構を提案する。
数値シミュレーションにより,本機構の有効性を実証する。
論文 参考訳（メタデータ） (2021-06-11T21:32:17Z) - Automated Mechanism Design for Classification with Partial Verification [64.69418921224529]
部分検証による自動機構設計の問題点について検討する。
私たちは、すべてのタイプが結果よりも同じ好みを共有する設定における真実のメカニズムに焦点を当てています。
論文 参考訳（メタデータ） (2021-04-12T03:29:31Z) - Regularized Online Allocation Problems: Fairness and Beyond [7.433931244705934]
本稿では, 総資源消費に作用する非線形正規化器を含む変種である, 語彙化オンライン割当問題を紹介する。
この問題では、要求は時間とともに繰り返し届き、各要求に対して、意思決定者は報酬を生成しリソースを消費するアクションを取る必要があります。
目的は、資源制約を受ける加算可分な報酬と非分離可正則化器の値とを同時に最大化することである。
論文 参考訳（メタデータ） (2020-07-01T14:24:58Z) - VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit
Feedback [104.06766271716774]
本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。
まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。
当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
論文 参考訳（メタデータ） (2020-04-19T18:00:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。