論文の概要: Scalable Virtual Valuations Combinatorial Auction Design by Combining
Zeroth-Order and First-Order Optimization Method
- arxiv url: http://arxiv.org/abs/2402.11904v1
- Date: Mon, 19 Feb 2024 07:45:04 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-20 17:52:48.618427
- Title: Scalable Virtual Valuations Combinatorial Auction Design by Combining
Zeroth-Order and First-Order Optimization Method
- Title(参考訳): zeroth-order と first-order optimization を併用したスケーラブルな仮想評価型コンビネートオークション設計
- Authors: Zhijian Duan, Haoran Sun, Yichong Xia, Siqiang Wang, Zhilin Zhang,
Chuan Yu, Jian Xu, Bo Zheng, Xiaotie Deng
- Abstract要約: 自動オークションデザインは、機械学習を用いて経験的に高効率でインセンティブに適合するメカニズムを発見することを目指している。
既存のアプローチでは、スケーラビリティの問題や収益の非差別化といった課題に直面している。
本稿では,VVCAパラメータを最適化するために,ゼロ階法と1階法を組み合わせた新しい最適化手法を提案する。
- 参考スコア(独自算出の注目度): 33.11929291593751
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Automated auction design seeks to discover empirically high-revenue and
incentive-compatible mechanisms using machine learning. Ensuring dominant
strategy incentive compatibility (DSIC) is crucial, and the most effective
approach is to confine the mechanism to Affine Maximizer Auctions (AMAs).
Nevertheless, existing AMA-based approaches encounter challenges such as
scalability issues (arising from combinatorial candidate allocations) and the
non-differentiability of revenue. In this paper, to achieve a scalable
AMA-based method, we further restrict the auction mechanism to Virtual
Valuations Combinatorial Auctions (VVCAs), a subset of AMAs with significantly
fewer parameters. Initially, we employ a parallelizable dynamic programming
algorithm to compute the winning allocation of a VVCA. Subsequently, we propose
a novel optimization method that combines both zeroth-order and first-order
techniques to optimize the VVCA parameters. Extensive experiments demonstrate
the efficacy and scalability of our proposed approach, termed Zeroth-order and
First-order Optimization of VVCAs (ZFO-VVCA), particularly when applied to
large-scale auctions.
- Abstract(参考訳): 自動オークションデザインは、機械学習を用いて経験的に高効率でインセンティブに適合するメカニズムを発見しようとしている。
主要な戦略インセンティブ互換性(DSIC)の確保は不可欠であり、最も効果的なアプローチはAffine Maximizer Auctions(AMA)のメカニズムを限定することである。
それでも、既存のAMAベースのアプローチは、スケーラビリティの問題(組み合わせ候補の割り当てから生じる)や収益の非差別性といった課題に直面している。
本稿では、スケーラブルなAMAベースの手法を実現するために、パラメータが大幅に少ないAMAのサブセットであるVVCA(Virtual Valuations Combinatorial Auctions)にオークション機構をさらに制限する。
まず、並列化可能な動的プログラムアルゴリズムを用いて、VVCAの入賞割り当てを計算する。
次に,VVCAパラメータを最適化するために,ゼロ階法と1階法を組み合わせた新しい最適化手法を提案する。
VVCAのゼロ次最適化(ZFO-VVCA)と1次最適化(ZFO-VVCA)と呼ばれる提案手法の有効性と拡張性を実証した。
関連論文リスト
- BOtied: Multi-objective Bayesian optimization with tied multivariate
ranks [49.85896045032822]
非支配解と最高多変量階との自然な関係を示し、これは合同累積分布関数(CDF)の最外層線と一致する。
我々はCDFインジケータに基づくBOtiedと呼ばれる取得関数を提案する。
論文 参考訳(メタデータ) (2023-06-01T04:50:06Z) - A Scalable Neural Network for DSIC Affine Maximizer Auction Design [20.177823187525107]
AMenuNetは、入札者およびアイテム表現からAMAパラメータを構成するスケーラブルなニューラルネットワークである。
我々は、AMenuNetがコンテキストおよび非コンテキストのマルチイテムオークションにおいて、強いベースラインよりも優れていることを示すための広範な実験を行った。
論文 参考訳(メタデータ) (2023-05-20T10:42:00Z) - An Auction-based Coordination Strategy for Task-Constrained Multi-Agent
Stochastic Planning with Submodular Rewards [7.419725234099728]
既存のタスク調整アルゴリズムはプロセスを無視したり、計算強度に悩まされる。
新たに定式化されたスコア関数を用いた分散オークションベースのコーディネート戦略を提案する。
大規模アプリケーションの実装には,提案手法の近似変種,すなわちDeep Auctionも提案されている。
論文 参考訳(メタデータ) (2022-12-30T10:25:25Z) - Bayesian Optimization-based Combinatorial Assignment [10.73407470973258]
オークションやコースアロケーションを含むアサインドメインについて検討する。
この領域の主な課題は、バンドル空間がアイテム数で指数関数的に増加することである。
論文 参考訳(メタデータ) (2022-08-31T08:47:02Z) - Late Fusion Multi-view Clustering via Global and Local Alignment
Maximization [61.89218392703043]
マルチビュークラスタリング(MVC)は、異なるビューからの補完情報を最適に統合し、クラスタリング性能を改善する。
既存のアプローチの多くは、クラスタリングに最適な類似性行列を学ぶために、複数の事前定義された類似性を直接融合する。
これらの問題に対処するために、アライメントを通してレイトフュージョンMVCを提案する。
論文 参考訳(メタデータ) (2022-08-02T01:49:31Z) - Efficient Neural Network Analysis with Sum-of-Infeasibilities [64.31536828511021]
凸最適化における総和係数法に着想を得て,広範な分岐関数を持つネットワーク上での検証クエリを解析するための新しい手法を提案する。
標準ケース分析に基づく完全探索手順の拡張は、各検索状態で実行される凸手順をDeepSoIに置き換えることによって達成できる。
論文 参考訳(メタデータ) (2022-03-19T15:05:09Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Batch Sequential Adaptive Designs for Global Optimization [5.825138898746968]
効率的なグローバル最適化(EGO)は、高価なブラックボックス最適化問題に対する最も一般的なSAD手法の1つである。
これらの複数点のEGO法では、重い計算とポイントのクラスタリングが障害となる。
本研究では, 改良されたサンプリング/インポータンス・リサンプリング(SIR)法を用いて, 「加速EGO」と呼ばれる新しいバッチSAD法を転送する。
提案したSADの効率は,次元が2~12の9つの古典的テスト関数によって検証される。
論文 参考訳(メタデータ) (2020-10-21T01:11:35Z) - Bilevel Optimization: Convergence Analysis and Enhanced Design [63.64636047748605]
バイレベル最適化は多くの機械学習問題に対するツールである。
Stoc-BiO という新しい確率効率勾配推定器を提案する。
論文 参考訳(メタデータ) (2020-10-15T18:09:48Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - Differentiable Expected Hypervolume Improvement for Parallel
Multi-Objective Bayesian Optimization [11.956059322407437]
我々は、期待されるハイパー改善(EHVI)を用いた多目的BOのプログラミングモデルとハードウェアアクセラレーションの最近の進歩を活用する。
我々は、EHVIを並列な制約付き評価設定に拡張する取得関数であるq-Expected Hyper Improvement (qEHVI) の新規な定式化を導出する。
実験により,qEHVIは実運用シナリオの多くで計算可能であり,壁面時間のごく一部で最先端の多目的BOアルゴリズムより優れていることが示された。
論文 参考訳(メタデータ) (2020-06-09T06:57:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。