論文の概要: Learning Optimal Tax Design in Nonatomic Congestion Games

• arxiv url: http://arxiv.org/abs/2402.07437v1
• Date: Mon, 12 Feb 2024 06:32:53 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-13 15:17:46.103820
• Title: Learning Optimal Tax Design in Nonatomic Congestion Games
• Title（参考訳）: 非原子間混雑ゲームにおける最適課税設計の学習
• Authors: Qiwen Cui, Maryam Fazel and Simon S. Du
• Abstract要約: 我々は,非原子的混雑ゲームにおいて,最適な税制設計を学習し,効率を最大化する方法について検討する。 プレイヤー間の自己関心行動がシステムの効率を損なうことが知られている。
• 参考スコア（独自算出の注目度）: 63.89699366726275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study how to learn the optimal tax design to maximize the efficiency in nonatomic congestion games. It is known that self-interested behavior among the players can damage the system's efficiency. Tax mechanisms is a common method to alleviate this issue and induce socially optimal behavior. In this work, we take the initial step for learning the optimal tax that can minimize the social cost with \emph{equilibrium feedback}, i.e., the tax designer can only observe the equilibrium state under the enforced tax. Existing algorithms are not applicable due to the exponentially large tax function space, nonexistence of the gradient, and nonconvexity of the objective. To tackle these challenges, our algorithm leverages several novel components: (1) piece-wise linear tax to approximate the optimal tax; (2) an extra linear term to guarantee a strongly convex potential function; (3) efficient subroutine to find the ``boundary'' tax. The algorithm can find an $\epsilon$-optimal tax with $O(\beta F^2/\epsilon)$ sample complexity, where $\beta$ is the smoothness of the cost function and $F$ is the number of facilities.
• Abstract（参考訳）: 非原子的混雑ゲームにおける最適税制設計の学習方法について検討する。 プレイヤー間の自己関心行動がシステムの効率を損なうことが知られている。 税制は、この問題を緩和し、社会的に最適な行動を引き起こす一般的な方法である。 本研究では, 社会コストを最小化できる最適税法を学習する最初のステップとして, すなわち, 強制課税下の均衡状態のみを, 設計者が観察できることを述べる。 既存のアルゴリズムは指数的に大きな税関数空間、勾配の非存在、目的の非凸性のために適用できない。 これらの課題に対処するために,本アルゴリズムは,(1)最適税を近似する分級線形税,(2)強い対流ポテンシャル関数を保証する余剰線形用語,(3)「境界」税を見つけるための効率的なサブルーチンなど,いくつかの新しい成分を活用する。 このアルゴリズムは、$O(\beta F^2/\epsilon)$サンプルの複雑さで$\epsilon$-optimal taxを見つけることができ、$\beta$はコスト関数の滑らかさ、$F$は施設数である。

関連論文リスト

• Subsidy design for better social outcomes [24.2043855572415]
  セントラルプランナーは これらの問題を 大幅に軽減できる 補助金を注入することで システムに関連する コストを削減できる 我々は、社会的利益を完璧に最適化する補助金の設計について、アナーキー価格の最小化や情報回避行動の防止の観点から、標準的な複雑性理論の仮定の下で計算的に困難であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T23:38:30Z)
• A Taxation Perspective for Fair Re-ranking [61.946428892727795]
  本稿では,2項目間の実用性の違いに基づいて税率を上昇させる,税率という新たな公正な再格付け手法を提案する。 我々のモデルである税ランクは、公正な優遇措置として優れた税率政策を提供し、理論的には、精度損失よりも連続性と制御性の両方を実証している。
  論文  参考訳（メタデータ） (2024-04-27T08:21:29Z)
• On Tractable $Φ$-Equilibria in Non-Concave Games [53.212133025684224]
  非凹面ゲームはゲーム理論と最適化に重大な課題をもたらす。 Phi$が有限であるとき、対応する$Phi$-equilibriaに収束する効率的な非結合学習アルゴリズムが存在することを示す。 また,オンライングラディエントDescentは,非自明な状況下で効率よく$Phi$-equilibriaを近似できることを示した。
  論文  参考訳（メタデータ） (2024-03-13T01:51:30Z)
• On the Potential and Limitations of Few-Shot In-Context Learning to Generate Metamorphic Specifications for Tax Preparation Software [12.071874385139395]
  納税者の50%近くが、FY22にアメリカで税ソフトウェアを使って個人所得税を申告した。 本稿では,税制文書から抽出した属性間の翻訳タスクとして,変成仕様を作成するタスクを定式化する。
  論文  参考訳（メタデータ） (2023-11-20T18:12:28Z)
• Adaptive maximization of social welfare [1.556652483029531]
  我々は、社会福祉を最大化するための政策を繰り返し選択する問題を考える。 我々は, Exp3アルゴリズムの変形に対して, 後悔に対する低い境界と, 一致する逆上界を導出する。
  論文  参考訳（メタデータ） (2023-10-14T15:09:56Z)
• Towards convergence to Nash equilibria in two-team zero-sum games [17.4461045395989]
  2チームゼロサムゲームは、プレイヤーが2つの競合するエージェントに分割されるマルチプレイヤーゲームとして定義される。 我々はNash equilibria(NE)の解の概念に焦点をあてる。 このクラスのゲームに対する計算 NE は、複雑性クラス $mathrm$ に対して $textithard$ であることを示す。
  論文  参考訳（メタデータ） (2021-11-07T21:15:35Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Almost Optimal Algorithms for Two-player Markov Games with Linear Function Approximation [92.99933928528797]
  同時動作による2プレイヤーゼロサムマルコフゲームの強化学習について検討した。 我々は,「不確かさの最適性」に基づくアルゴリズムナッシュ-UCRL-VTRを提案する。 我々は、Nash-UCRL-VTR が $tildeO(dHsqrtT)$ regret を確実に達成できることを示し、$d$ は線型関数次元である。
  論文  参考訳（メタデータ） (2021-02-15T09:09:16Z)
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium [116.56359444619441]
  両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。 オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。 オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
  論文  参考訳（メタデータ） (2020-02-17T17:04:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。