其它计算机科学 · 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-Majority规则:每轮每个节点随机采样h个节点并采用出现最多的意见,平局随机打破。结果表明,在一类广泛的共识动力学中,h-Majority实现了采样规模与共识时间之间的近最优权衡。

看点证明h-Majority对所有h≥3和任意初始配置给出近乎最优的共识时间上界,并给出匹配下界,改进了已有分析。

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的码,据称在误帧率10^-3下比传统PAC码有至少半dB的增益。

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)。文件指出,高亮度大型强子对撞机、SKA天文台和LOFAR 2.0将把高能物理与射电天文推向未来十年的EB级数据规模。两份文件基于同一证据,分别提出技术行动建议与分阶段的优先事项路线图,并总结了其咨询方法及SRIDA预期的影响。

Sergio Andreozzi, Stefano Bagnasco, Florian Berberich 等

★★★★☆ 值得关注
arXiv math.CO · cs.DM · cs.IT

Average pairwise Hamming distance of a subset in a hypercube

说明超立方体子集的平均两两汉明距离

简介本文研究超立方体 {0,1}^n 中密度为 1/8 的子集,证明其平均两两汉明距离至少为 (n-3)/2,且只有 (n-3) 维子立方体能取到等号。该结论回答了 Lei Yu 提出的问题,并解决了 Ahlswede 与 Katona 在 1977 年提出的一般问题中的一个重要未解情形。

看点作者证明超立方体中密度为1/8的子集,其平均两两汉明距离至少为(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项主要研究,探讨语言模型在边缘-云连续体服务编排中的应用。作者提出一个五维分析框架,连接系统环境、编排决策、语言模型的决策权限、运行保障措施与评估证据。综述发现,目前多为混合式设计:语言模型负责解读、生成候选方案和规划缓解措施,而可行性校验与执行权通常仍由下游组件掌握。

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

说明真三维全息通信:面向6G的未来通信服务及其对融合云网架构的需求

简介该论文以研究项目6G NeXt将真三维全息作为用例为背景,阐述真三维全息通信的特点及其对通信与计算基础设施的要求。文中指出,全息服务需要分布式高速骨干计算基础设施支持拆分计算,并需要处理设施与无线网络紧密集成以提供沉浸式体验。作者在此基础上提出整体通信与计算架构,并讨论相关新技术方案。

Ingo Friese, Mandy Galkow-Schneider, Louay Bassbouss 等