論文の概要: 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$は施設数である。
関連論文リスト
- A Taxation Perspective for Fair Re-ranking [61.946428892727795]
本稿では,2項目間の実用性の違いに基づいて税率を上昇させる,税率という新たな公正な再格付け手法を提案する。
我々のモデルである税ランクは、公正な優遇措置として優れた税率政策を提供し、理論的には、精度損失よりも連続性と制御性の両方を実証している。
論文 参考訳（メタデータ） (2024-04-27T08:21:29Z) - On Partial Optimal Transport: Revising the Infeasibility of Sinkhorn and
Efficient Gradient Methods [17.14725907264431]
本稿では,少なくとも$n$の支持を持つ2つの不均衡測度間の部分最適輸送(POT)問題について検討する。
我々はPOTの新しいラウンドリングアルゴリズムを提案し、次に、$mathcalwidetilde O(n2/varepsilon4)$の複雑さを補正した実行可能なシンクホーン手順を提供する。
論文 参考訳（メタデータ） (2023-12-21T15:56:09Z) - 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) - 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) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。