その他の計算機科学 · 2026年10月30日(金)

分散計算、ゲーム理論、情報理論など。

RSS で購読
★★★★☆ 注目
arXiv cs.GT · econ.TH

Finding Competitive Equilibria in Online Marketplaces with Platform Fees, Taxes, and Subsidies

説明プラットフォーム手数料・税・補助金を含むオンライン市場での競争均衡の探索

要約本論文は、一般化された完全代替性を満たす評価値と、買い手・取引ごとに異なる区分線形の移転関数を持つ複数単位取引ネットワークにおける均衡計算を研究している。この移転関数は、オンラインマーケットプレイスのプラットフォーム手数料、税、補助金、会員割引を表す。提案する昇順手続きは価格を異なる速度で引き上げ、有限回の反復で最小均衡価格ベクトルに到達する。各反復は強多項式時間で実行可能で、その後均衡配分を効率的に復元できる。手法は、購入と販売の補完性を子モジュラーフロー定式化で扱うことで、昇順オークションの原始双対技法を拡張している。

注目点プラットフォーム手数料や税・補助金を含む多単位取引ネットワークに原始双対オークション手法を拡張し、強多項式時間の均衡計算を与える。

Taihei Oki, Ryosuke Sato

★★★★☆ 注目
arXiv cs.DC · cs.DS · math.PR

Nearly-Optimal Time-Sample Trade-off in Consensus Dynamics

説明合意ダイナミクスにおけるサンプル数と合意時間の近最適なトレードオフ

要約本論文は、分散合意ダイナミクスにおいて各ノードが参照する意見のサンプル数が、合意に至るまでの時間にどう影響するかを研究している。各ラウンドで各ノードがh個のノードを無作為に抽出し、最も多く現れた意見を採用する同期型のh-Majorityを分析する。その結果、幅広い合意ダイナミクスの中で、h-Majorityがサンプル規模と合意時間の間の近最適なトレードオフを達成することを示している。

注目点h≥3の全ての値と任意の初期配置に対し、h-Majorityの合意時間の上界を示し、対数因子を除き一致する下界も与えている。

Francesco d'Amore, Joel Rybicki, Nobutaka Shimizu ほか

arXiv cs.IT · math.IT

An SCL-Aware Design of PAC Codes

説明SCL復号を考慮したPAC符号の設計:リスト復号向けの符号設計手法

要約本論文は、連続消去リスト(SCL)復号に適した極性調整畳み込み(PAC)符号のレートプロファイルを設計する手法を提案する。誤りがある場合の復号過程を解析するため条件付き密度進化ガウス近似(CDEGA)を、有限リスト内のビット誤りの条件付き占有を求めるため危険経路占有指標を導入している。これらを用いて設計した長さ512以下の符号は、FER10^-3において従来のPAC符号より少なくとも0.5dB優れるとされている。

Tyler Kann, Shrinivas Kudekar, Matthieu R. Bloch

arXiv cs.DC · astro-ph.IM

SPECTRUM: A Strategic Framework and Technical Blueprint for European Exascale Research Data and Compute Infrastructure

説明SPECTRUM:欧州のエクサスケール研究データ・計算基盤に向けた戦略的枠組みと技術ブループリント

要約本論文は、SPECTRUMプロジェクトによる二つの成果物、「技術ブループリント」と「戦略的研究・イノベーション・展開アジェンダ(SRIDA)」を概説するものです。HL-LHC、SKA天文台、LOFAR 2.0により、今後10年で高エネルギー物理学と電波天文学がエクサバイト規模のデータに直面することを指摘しています。両文書は同じ根拠に基づき、技術的行動の提言と段階的なロードマップを示しています。あわせて、その協議の方法とSRIDAが見込む効果もまとめています。

Sergio Andreozzi, Stefano Bagnasco, Florian Berberich ほか

★★★★☆ 注目
arXiv math.CO · cs.DM · cs.IT

Average pairwise Hamming distance of a subset in a hypercube

説明超立方体の部分集合における平均二点間ハミング距離

要約本論文は、密度 1/8 の {0,1}^n の部分集合について、平均二点間ハミング距離が少なくとも (n-3)/2 であることを証明し、等号が成り立つのは (n-3) 次元部分立方体のみであることを示す。これは Lei Yu の問いに答えるものであり、1977 年に Ahlswede と Katona が提起した一般的問題の重要な未解決事例を解決している。

注目点著者は、超立方体の密度1/8の部分集合について、平均2点間ハミング距離が少なくとも(n-3)/2であり、等号は(n-3)次元部分立方体に限ると示したと報告している。これはYuの問いに答え、Ahlswede と Katona が1977年に提起した一般問題の重要な未解決事例を扱うものである。

Yijia Fang, Hao Huang

arXiv cs.DC

Can We Rely on Language Models to Orchestrate Services across the Edge-Cloud Continuum?

説明エッジ・クラウド連続体にわたるサービス編成を言語モデルに任せられるか?

要約本論文は、エッジ・クラウド連続体におけるサービス編成で言語モデルを用いる研究39件を体系的にレビューしています。システム文脈、編成判断、言語モデルの権限、運用上の安全策、評価根拠の5つの観点からなる分析枠組みを提案しています。レビューの結果、言語モデルは解釈、候補案の生成、緩和策の立案を担い、実行可能性の検証と実行権限は後段のコンポーネントが保持する混合型設計が主流であることが分かりました。

Zhenghao Wu, Ruihai Dong, Reza Farahani ほか

arXiv cs.GT · math.OC

First-Order Bilevel Optimization for Non-truthful Auction Design

説明非真実的オークション設計のための一次双レベル最適化

要約本論文はオークション設計を複数の追随者を持つシュタッケルベルクゲームとして定式化し、非真実的オークションの収益最適化を行う完全一次の手法を提案しています。超勾配近似について非漸近的な保証を示し、標準的な滑らかさと強単調性の仮定の下で、約 O(ε⁻²) 回の一次オラクル呼び出しで O(ε) 定常点に到達することを示しています。対称・非対称の単一財オークションおよび複数財オークションの実験では、二次・ゼロ次の基準手法より速く収束し、入札者数の増加にも良く対応すること、真実的オークションに近い収益を達成する機構を発見できることが報告されています。

Shing-Hei Ho, April Niu, Ellen Vitercik ほか

arXiv cs.NI · cs.DC · eess.SP

True 3D Holography: A Communication Service of Tomorrow and Its Requirements for a New Converged Cloud and Network Architecture on the Path to 6G

説明真の3Dホログラフィー:6Gに向けた次世代通信サービスと新たな融合型クラウド・ネットワーク構造への要件

要約本論文は、研究プロジェクト6G NeXtがユースケースとして真の3Dホログラフィーを検討している背景のもとで、通信およびコンピューティング基盤に課される要件を示しています。分散型の高速バックボーン計算基盤による分割計算と、処理設備と無線ネットワークの密な統合が不可欠であると論じています。また、提案する通信・計算の全体アーキテクチャに基づき、新たな技術的アプローチを検討しています。

Ingo Friese, Mandy Galkow-Schneider, Louay Bassbouss ほか