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

• arxiv url: http://arxiv.org/abs/2402.07437v2
• Date: Wed, 15 Jan 2025 14:02:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-16 15:50:40.859772
• Title: Learning Optimal Tax Design in Nonatomic Congestion Games
• Title（参考訳）: 非原子的混雑ゲームにおける最適税制設計の学習
• Authors: Qiwen Cui, Maryam Fazel, Simon S. Du,
• Abstract要約: マルチプレイヤーゲームでは、プレイヤー間の利己的な行動が社会福祉を損なうことがある。 我々は、渋滞ゲームにおいて、限られたフィードバックで社会福祉を誘導できる最適税を学習する最初のステップを採っている。
• 参考スコア（独自算出の注目度）: 56.85292809260111
• License:
• Abstract: In multiplayer games, self-interested behavior among the players can harm the social welfare. Tax mechanisms are a common method to alleviate this issue and induce socially optimal behavior. In this work, we take the initial step of learning the optimal tax that can maximize social welfare with limited feedback in congestion games. We propose a new type of feedback named \emph{equilibrium feedback}, where the tax designer can only observe the Nash equilibrium after deploying a tax plan. 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, we design a computationally efficient algorithm that leverages several novel components: (1) a piece-wise linear tax to approximate the optimal tax; (2) extra linear terms to guarantee a strongly convex potential function; (3) an efficient subroutine to find the exploratory tax that can provide critical information about the game. 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（参考訳）: マルチプレイヤーゲームでは、プレイヤー間の利己的な行動が社会福祉を損なうことがある。 税制は、この問題を緩和し、社会的に最適な行動を引き起こすための一般的な方法である。 本研究では,渋滞ゲームにおいて,限られたフィードバックで社会福祉を最大化できる最適税を学習する第一歩を踏み出した。 本稿では,納税計画の展開後のみナッシュ均衡を観測できる「emph{equilibrium feedback}」という新しいタイプのフィードバックを提案する。 既存のアルゴリズムは指数的に大きな税関数空間、勾配の非存在、目的の非凸性のために適用できない。 これらの課題に対処するために,(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)

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

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