本サイトは 12 時間以上更新されていません（通常は 3 時間ごと）。以下の内容は最新でない可能性があります。
このページに条件に合う項目はありません（絞り込みはこのページ内のみ）。
説明トーナメント均衡集はPSPACE完全問題であり、遺伝的一意性の下でも成り立つ
要約本論文は、two対の多数決比較に基づく古典的投票ルールであるトーナメント均衡集（TEQ）を扱う。TEQの定義は再帰的で、ある候補が支配者（自分に勝つ候補）によって評価される。論文は、ある候補がTEQに属するかどうかの判定がPSPACE完全であることを証明し、従来のNP困難かつPSPACEに属するという既知の結果の間隔を埋めた。すべての非空の部分トーナメントが一意の最小保持集合を持つ場合でも困難性は残る。さらに、支配者数の上限によって計算量がどう変わるかも分析している。
注目点TEQの所属判定がPSPACE完全であることを初めて示し、一意性の性質を満たす場合でも成り立つと作者は主張。投票理論と計算量理論の範囲に影響する。
説明劣モジュラ秘書問題：単調目的関数における厳密な1-1/e、一般の場合に1/eと1/2の間に収まる比率
要約本論文は、基数制約付きの劣モジュラ秘書問題を扱う。n 個の要素がランダムな順序で到着し、アルゴリズムは到着時に受理か棄却かを取り消せない形で決め、要素数が高々 k の集合上で非負の劣モジュラ関数を最大化する。単調な目的関数に対しては、k が無限大に近づくときの最適競合比が厳密に 1-1/e であることを示し、高々 4n+1 回の価値照会で達成するアルゴリズムを与える。一般の目的関数については、最適な極限比率が 1/e と 1/2 の間に厳密に収まることを示し、新たな手法として「資格減衰」を提案する。
注目点単調目標に対して1-1/eのタイトな競合比を達成する単一アルゴリズムを示し、一般目標では最適比を1/eと1/2の間に位置づけ、資格減衰という新手法を導入している。
説明期待効用最大化者でない場合の仮想プレイ：2×2ゲームにおける幾何学的分析
要約本論文は、エージェントが相手の経験的信念のもとで収益分布を非線形の汎関数で評価する非線形仮想プレイ（NL-FP）を研究する。著者らは、2×2ゲームで古典的な仮想プレイの幾何構造を保つ単一交差性質（SCP）を提示し、SCPが成り立たない場合の収束挙動も幾何学的に分析している。さらに、2×3ゲームで一方のプレイヤーが条件付きバリュー・アット・リスク（CVaR）を用いると、連続時間のNL-FPでも収束しない場合があることを示す。また、一般の2×nゲームにおける収束を保証する有限交差条件を提示している。
説明『難解性の種をまく：Kalah は PSPACE 完全である』：播種ゲーム Kalah は盤面が大きくなると判定問題が PSPACE 完全になることを示す論文
要約本論文は、マンカラ系の播種ゲームである二人用ゲーム Kalah を扱う。各側の穴数を入力の一部とし、任意の局面が与えられたとき、指定したプレイヤーが勝利を強制できるかを判定する問題が PSPACE 完全であることを示す。証明では中間問題 Line Kalah を導入し、量化ブール式をこれに帰着させたうえで、直線上の局面を両側の貯蔵庫が空の Kalah に埋め込んでいる。
注目点新規性は、任意盤面のKalahの必勝判定がPSPACE完全であることを示し、中間問題Line Kalahを導入した点にある。作者は両捕獲規約と追加手ルール下でも成立すると述べ、主に組合せゲーム理論の複雑性に影響する。
説明PACER：機械学習ワークロード向けGPUの電力超過管理
要約本論文は、現代のGPUにおいて、定格電力を一時的に超える電力超過（EDPp）が性能のばらつきの主な原因の一つであることを示しています。著者らはこの電力超過の大きさと頻度を初めて特徴づけ、大規模言語モデルなどの機械学習ワークロードで特に頻繁に起きることを明らかにしました。そのうえで、ハードウェアとファームウェアの仕組みを設計し、EDPpによるばらつきを抑えています。評価では、既存のGPU電力管理と比べて性能が3〜12%向上し、理想的な手法との差は3%以内に収まったと報告されています。
説明資源地形における影響者ゲームの学習ダイナミクス：競争が収束か分断かを左右する仕組みの研究
要約本論文は、プレイヤーの戦略を特性空間上の位置として表す新しい空間ゲーム「影響者ゲーム（influencer's game）」を提案している。プレイヤーは各資源の特性地点における相対的な影響力に応じて資源の分け前を得る。影響核が厳密な対数凹である場合に唯一の対称ナッシュ均衡が存在することを示し、その安定性が影響核のパラメータ、プレイヤー数、資源分布の形状に依存することを分析している。さらに、実世界の資源データや多エージェント強化学習を用いて結果を検証している。
注目点新しい空間ゲーム枠組みを提案し、対称ナッシュ均衡の一意性と安定性閾値、分岐の種類を示す。実データと多エージェント強化学習で検証。
説明複製ではなく放送：データセンターのLLM推論で重みHBMを不要にする
要約本論文は、従来の光ファイバー遅延線メモリ方式に代わる、階層型のタップ・増幅光ファイバーアーキテクチャ「光ブロードキャストメモリ（OBM）」を提案しています。中央のメモリサーバーが重みを分散推論ノードへ連続的に放送し、ノードは受信専用の共パッケージ光学素子でデータストリームを受動的に取り込みます。8万台のアクセラレータ規模で評価され、HBMベースのシステムと比べてスループットとトークンあたりエネルギーで同等以上と報告されています。