論文の概要: Differentiable Equilibrium Computation with Decision Diagrams for
Stackelberg Models of Combinatorial Congestion Games
- arxiv url: http://arxiv.org/abs/2110.01773v1
- Date: Tue, 5 Oct 2021 01:14:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-06 13:57:14.512302
- Title: Differentiable Equilibrium Computation with Decision Diagrams for
Stackelberg Models of Combinatorial Congestion Games
- Title（参考訳）: 組合せ共役ゲームにおけるスタックルバーグモデルに対する決定ダイアグラムを用いた微分平衡計算
- Authors: Shinsaku Sakaue and Kengo Nakamura
- Abstract要約: 渋滞ゲーム(CCG)のスタックルバーグモデルに対処する。
我々は,CCGのパラメータを最適化して,非原子プレーヤの利己的行動が望ましい平衡を達成することを目指している。
- 参考スコア（独自算出の注目度）: 18.909661013764055
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address Stackelberg models of combinatorial congestion games (CCGs); we
aim to optimize the parameters of CCGs so that the selfish behavior of
non-atomic players attains desirable equilibria. This model is essential for
designing such social infrastructures as traffic and communication networks.
Nevertheless, computational approaches to the model have not been thoroughly
studied due to two difficulties: (I) bilevel-programming structures and (II)
the combinatorial nature of CCGs. We tackle them by carefully combining (I) the
idea of \textit{differentiable} optimization and (II) data structures called
\textit{zero-suppressed binary decision diagrams} (ZDDs), which can compactly
represent sets of combinatorial strategies. Our algorithm numerically
approximates the equilibria of CCGs, which we can differentiate with respect to
parameters of CCGs by automatic differentiation. With the resulting
derivatives, we can apply gradient-based methods to Stackelberg models of CCGs.
Our method is tailored to induce Nesterov's acceleration and can fully utilize
the empirical compactness of ZDDs. These technical advantages enable us to deal
with CCGs with a vast number of combinatorial strategies. Experiments on
real-world network design instances demonstrate the practicality of our method.
- Abstract（参考訳）: 組合せ共役ゲーム(CCG)のStackelbergモデルに対処し、CCGのパラメータを最適化し、非原子的プレイヤーの利己的な振る舞いが望ましい均衡を達成することを目指す。
このモデルは、交通や通信ネットワークのような社会基盤を設計するのに不可欠である。
しかしながら、モデルに対する計算的アプローチは、(I)バイレベルプログラミング構造と(II)CCGの組合せの性質という2つの困難のために、十分に研究されていない。
I) <textit{differentiable} 最適化のアイデアと (II) 組合せ戦略の集合をコンパクトに表現できる \textit{zero-suppressed binary decision diagrams} (ZDDs) と呼ばれるデータ構造を慎重に組み合わせることで、それらに取り組む。
本アルゴリズムはCCGの平衡を数値的に近似し,自動微分によりCCGのパラメータを微分することができる。
その結果、ccgsのstackelbergモデルに勾配に基づく手法を適用することができる。
本手法はNesterovの加速を誘導するために調整され,ZDDの実証的コンパクト性を完全に活用できる。
これらの技術的アドバンテージにより、多数の組合せ戦略でCGを扱うことができます。
実世界のネットワーク設計事例実験により,本手法の実用性が実証された。
関連論文リスト
- Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
最適化問題に取り組むための新たな戦略は、従来のアルゴリズムに代わるグラフニューラルネットワーク(GNN)の採用である。
GNNや従来のアルゴリズムソルバがCOの領域で人気が高まっているにもかかわらず、それらの統合利用とエンドツーエンドフレームワークにおけるそれらの相関について限定的な研究がなされている。
我々は、GNNを利用してCO問題に補助的なサポートで対処する決定に焦点を当てたフレームワークを導入する。
論文 参考訳（メタデータ） (2024-06-05T22:52:27Z) - Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [56.26113670151363]
グラフ凝縮(Graph condensation)は、大きなグラフを小さいが情報的な凝縮グラフに置き換えるための、データ中心のソリューションである。
既存のGCメソッドは複雑な最適化プロセスに悩まされており、過剰な計算資源を必要とする。
我々は、CGC(Class-partitioned Graph Condensation)と呼ばれるトレーニング不要なGCフレームワークを提案する。
CGCはより効率的な凝縮プロセスで最先端の性能を達成する。
論文 参考訳（メタデータ） (2024-05-22T14:57:09Z) - Training Single-Layer Morphological Perceptron Using Convex-Concave
Programming [0.4895118383237099]
コンベックス・コンケーブ計画法(DCCP)を用いた単層型パーセプトロンの訓練について検討する。
リタロポロスとマラゴスによって提案された既存の単層型形態素パーセプトロン(SLMP)モデルを組み合わせたK-DDCCPを提案する。
実験により,K-DDCCPアルゴリズムによる二項分類問題の解法の有効性が確認された。
論文 参考訳（メタデータ） (2024-01-04T14:34:58Z) - A Comprehensive Study on Knowledge Graph Embedding over Relational
Patterns Based on Rule Learning [49.09125100268454]
KGE(Knowledge Graph Embedding)は、KGC(Knowledge Completion Graph)タスクを解決するための効果的なアプローチであることが証明されている。
関係パターンはKGEモデルの性能において重要な要素である。
我々は,KGEモデルの性能を様々な関係パターン上で向上させるトレーニングフリー手法を提案する。
論文 参考訳（メタデータ） (2023-08-15T17:30:57Z) - Knowledge Graph Contrastive Learning Based on Relation-Symmetrical
Structure [36.507635518425744]
関係対称構造に基づく知識グラフコントラスト学習フレームワークKGE-SymCLを提案する。
我々のフレームワークは、KGEモデルの識別能力を高めるために、KGの対称構造情報をマイニングする。
論文 参考訳（メタデータ） (2022-11-19T16:30:29Z) - A Differentiable Approach to Combinatorial Optimization using Dataless
Neural Networks [20.170140039052455]
我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。
特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
論文 参考訳（メタデータ） (2022-03-15T19:21:31Z) - Training Generative Adversarial Networks with Adaptive Composite
Gradient [2.471982349512685]
本稿では,二線形ゲームにおいて線形収束する適応型コンポジットグラディエント法を提案する。
ACGは、各ステップの勾配を計算する必要がないため、半漸進的なアルゴリズムである。
結果は、ACGが以前のアルゴリズムと競合していることを示している。
論文 参考訳（メタデータ） (2021-11-10T03:13:53Z) - Cogradient Descent for Dependable Learning [64.02052988844301]
双線形最適化問題に対処するために,CoGDアルゴリズムに基づく信頼度の高い学習法を提案する。
CoGDは、ある変数がスパーシティ制約を持つ場合の双線形問題を解くために導入された。
また、特徴と重みの関連を分解するためにも使用できるため、畳み込みニューラルネットワーク(CNN)をより良く訓練するための我々の手法をさらに一般化することができる。
論文 参考訳（メタデータ） (2021-06-20T04:28:20Z) - A Bi-Level Framework for Learning to Solve Combinatorial Optimization on
Graphs [91.07247251502564]
本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。
このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
論文 参考訳（メタデータ） (2021-06-09T09:18:18Z) - Learning Gaussian Graphical Models with Latent Confounders [74.72998362041088]
我々は、グラフィカルモデルにおける推論のための2つの戦略を、潜伏した共同創設者と比較し、対比する。
これら2つのアプローチは、類似した目標を持っているが、それらは共起に関する異なる仮定によって動機付けられている。
これら2つのアプローチの強みを組み合わせた新しい手法を提案する。
論文 参考訳（メタデータ） (2021-05-14T00:53:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。