論文の概要: Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
- arxiv url: http://arxiv.org/abs/2508.11874v1
- Date: Sat, 16 Aug 2025 02:18:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-19 14:49:10.431204
- Title: Discovering Expert-Level Nash Equilibrium Algorithms with Large Language Models
- Title（参考訳）: 大規模言語モデルを用いたエキスパートレベルナッシュ平衡アルゴリズムの探索
- Authors: Hanyu Li, Dongchen Li, Xiaotie Deng,
- Abstract要約: LegoNEは、アルゴリズム設計の創造的なプロセスと形式解析の厳密なプロセスとを融合させるフレームワークである。
最先端の大規模言語モデルであるLegoNEを使用することで、数時間以内に2人のプレイヤーによるゲームの最先端のアルゴリズムが再発見された。
この研究は、理論科学のための新しい人間と機械の協調パラダイムを実証する。
- 参考スコア（独自算出の注目度）: 8.041049362762593
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Algorithm design and analysis is a cornerstone of computer science, but it confronts a major challenge. Proving an algorithm's performance guarantee across all inputs has traditionally required extensive and often error-prone human effort. While AI has shown great success in finding solutions to specific problem instances, automating the discovery of general algorithms with such provable guarantees has remained a significant barrier. This challenge stems from the difficulty of integrating the creative process of algorithm design with the rigorous process of formal analysis. To address this gap, we propose LegoNE, a framework that tightly fuses these two processes for the fundamental and notoriously difficult problem of computing approximate Nash equilibria. LegoNE automatically translates any algorithm written by a simple Python-like language into a constrained optimization problem. Solving this problem derives and proves the algorithm's approximation bound. Using LegoNE, a state-of-the-art large language model rediscovered the state-of-the-art algorithm for two-player games within hours, a feat that had taken human researchers 15 years to achieve. For three-player games, the model discovered a novel algorithm surpassing all existing human-designed ones. This work demonstrates a new human-machine collaborative paradigm for theoretical science: humans reason at a higher-abstract level, using symbols to compress the search space, and AI explores within it, achieving what neither could alone.
- Abstract（参考訳）: アルゴリズムの設計と分析はコンピュータ科学の基盤だが、大きな課題に直面している。
アルゴリズムの性能保証を全ての入力で証明するには、伝統的に広範囲でしばしばエラーを起こしやすい人間の努力が必要である。
AIは特定の問題インスタンスのソリューションを見つけることに大きな成功をおさめているが、そのような証明可能な保証で一般的なアルゴリズムの発見を自動化することは、依然として大きな障壁となっている。
この課題は、アルゴリズム設計の創造的プロセスと形式解析の厳密なプロセスを統合することの難しさに起因している。
このギャップに対処するために、我々はLegoNEを提案します。これは、Nash平衡を近似的に計算する基本的な問題と悪名高い問題に対して、これらの2つのプロセスを密に融合するフレームワークです。
LegoNEは、単純なPythonのような言語で書かれた任意のアルゴリズムを、制約付き最適化問題に自動的に変換する。
この問題の解法はアルゴリズムの近似境界を導出し証明する。
最先端の大規模言語モデルであるLegoNEを使用することで、数時間以内に2人のプレイヤーによるゲームの最先端のアルゴリズムが再発見された。
3人プレイのゲームでは、既存の人間設計のゲームに勝る新しいアルゴリズムが見つかった。
この研究は、理論科学のための新しい人間と機械の協調パラダイムを実証している。人間はより高い抽象レベルで推論し、記号を使って検索空間を圧縮し、AIはその内部を探索し、どちらも達成できないことを達成している。
関連論文リスト
- Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - A Generalized Evolutionary Metaheuristic (GEM) Algorithm for Engineering Optimization [1.6589012298747952]
近年の大きなトレンドは、自然に着想を得たメタヒュースティックアルゴリズム(NIMA)の利用である。
文献には540以上のアルゴリズムがあり、異なるアルゴリズムの探索機構を理解するための統一的なフレームワークはない。
20以上の異なるアルゴリズムを統一する一般化された進化的メタヒューリスティックアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-02T09:55:15Z) - From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
この調査は、推論中に計算をスケールするメリットに焦点を当てている。
我々はトークンレベルの生成アルゴリズム、メタジェネレーションアルゴリズム、効率的な生成という3つの領域を統一的な数学的定式化の下で探索する。
論文 参考訳（メタデータ） (2024-06-24T17:45:59Z) - Algorithm Evolution Using Large Language Model [18.03090066194074]
大規模言語モデル(AEL)を用いた進化的アルゴリズムを提案する。
AELはモデルトレーニングなしでアルゴリズムレベルの進化を行う。
人間の努力とドメイン知識の要求は大幅に削減できる。
論文 参考訳（メタデータ） (2023-11-26T09:38:44Z) - The Clock and the Pizza: Two Stories in Mechanistic Explanation of
Neural Networks [59.26515696183751]
ニューラルネットワークにおけるアルゴリズム発見は、時としてより複雑であることを示す。
単純な学習問題でさえ、驚くほど多様なソリューションを許容できることが示されています。
論文 参考訳（メタデータ） (2023-06-30T17:59:13Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳（メタデータ） (2023-02-09T08:46:23Z) - Towards algorithm-free physical equilibrium model of computing [0.0]
新しい計算モデルが提案され、アルゴリズムの逐次パラダイムを物理プロセスの固有の並列性に置き換える。
平衡状態が所望の解に対応する物理系を構築し、解を探すためにそれらを進化させる。
モデルの主な要件は特定され、潜在的な実装のために量子回路が提案される。
論文 参考訳（メタデータ） (2021-11-30T09:48:39Z) - Nature-Inspired Optimization Algorithms: Research Direction and Survey [0.0]
自然に着想を得たアルゴリズムは、様々な最適化問題を解くのによく用いられる。
我々は自然に触発されたアルゴリズムを自然進化ベース、群知性ベース、生物ベース、科学ベースなどと分類する。
本研究の目的は, インスピレーション源, 基本演算子, 制御パラメータ, 特徴, 変種, 適用範囲に基づいて, 様々な自然に着想を得たアルゴリズムを網羅的に解析することである。
論文 参考訳（メタデータ） (2021-02-08T06:03:36Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。
ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
論文 参考訳（メタデータ） (2020-07-07T17:03:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。