会员服务
近似 · 操作 · 论文 · 博弈论 ·
1 月 25 日
Constant Inapproximability of Pacing Equilibria in Second-Price Auctions
翻译：暂无翻译
Xi Chen,Yuhao Li
Xi Chen,Yuhao Li

In this paper, we revisit the problem of approximating a pacing equilibrium in second-price auctions, introduced by Conitzer, Kroer, Sodomka, and Moses [Oper. Res. 2022]. We show that finding a constant-factor approximation of a pacing equilibrium is PPAD-hard, thereby strengthening previous results of Chen, Kroer, and Kumar [Math. Oper. Res. 2024], which established PPAD-hardness only for inverse-polynomial approximations.


翻译：暂无翻译
0
下载
关闭预览

相关内容

O’Reilly报告：知识图谱崛起——面向现代数据集成和数据结构体系，“The Rise of the Knowledge Graph——Toward Modern Data Integration and the Data Fabric Architecture”
O’Reilly报告：知识图谱崛起——面向现代数据集成和数据结构体系，“The Rise of the Knowledge Graph——Toward Modern Data Integration and the Data Fabric Architecture”
专知会员服务
47+阅读 · 2022年2月18日
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
专知会员服务
41+阅读 · 2020年5月30日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
30+阅读 · 2019年10月18日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
49+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
35+阅读 · 2019年10月17日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16（1）
From Softmax to Sparsemax-ICML16（1）
KingsGarden
73+阅读 · 2016年11月26日
Hamilton-Jacibi方程的弱KAM理论
国家自然科学基金
1+阅读 · 2017年12月31日
城市“建成环境——空间行为”的多尺度影响关系与机理研究
国家自然科学基金
11+阅读 · 2017年12月31日
“Fishes-in-net” 酵母孢子微胶囊式近平滑假丝酵母SCRII酶有机相高效手性合成机制研究
国家自然科学基金
2+阅读 · 2016年12月31日
Musielak-Orlicz-Sobolev 空间中的迹嵌入及其应用
国家自然科学基金
1+阅读 · 2015年12月31日
高频ZnO/IDT/SiO2/金刚石SAW乳腺癌抗原免疫传感器研究
国家自然科学基金
0+阅读 · 2015年12月31日
基于自主学习的Ad hoc Agent序贯决策研究
国家自然科学基金
41+阅读 · 2015年12月31日
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
2+阅读 · 2015年12月31日
PPP项目争端谈判及其治理机制研究
国家自然科学基金
2+阅读 · 2015年12月31日
动态Gr？bner 基与GVW算法
国家自然科学基金
0+阅读 · 2014年12月31日
“杰文斯”悖论、能效政策改进与“双控目标”分解
国家自然科学基金
0+阅读 · 2014年12月31日
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Arxiv
0+阅读 · 2月22日
Best of Both Worlds: Regret Minimization versus Minimax Play
Arxiv
0+阅读 · 2月17日
Checking Trustworthiness of Probabilistic Computations in a Typed Natural Deduction System
Arxiv
0+阅读 · 2月13日
Global Convergence Rate of Deep Equilibrium Models with General Activations
Arxiv
0+阅读 · 2月13日
Properties of Wasserstein Gradient Flows for the Sliced-Wasserstein Distance
Arxiv
0+阅读 · 2月10日
Complexity of Minimal Faithful Permutation Degree for Fitting-free Groups
Arxiv
0+阅读 · 2月9日
Still More Shades of Null: An Evaluation Suite for Responsible Missing Value Imputation
Arxiv
0+阅读 · 2月5日
Asynchronous Fault-Tolerant Language Decidability for Runtime Verification of Distributed Systems
Arxiv
0+阅读 · 1月31日
Single-Letter Characterization of the Mismatched Distortion-Rate Function
Arxiv
0+阅读 · 1月23日
Inferring Past Human Actions in Homes with Abductive Reasoning
Arxiv
0+阅读 · 1月22日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
近似
操作
论文
博弈论
相关VIP内容
O’Reilly报告：知识图谱崛起——面向现代数据集成和数据结构体系，“The Rise of the Knowledge Graph——Toward Modern Data Integration and the Data Fabric Architecture”
O’Reilly报告：知识图谱崛起——面向现代数据集成和数据结构体系，“The Rise of the Knowledge Graph——Toward Modern Data Integration and the Data Fabric Architecture”
专知会员服务
47+阅读 · 2022年2月18日
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
生成性对抗网络:理论模型、评估指标和最近发展的概述，Generative Adversarial Networks (GANs): An Overview of Theoretical Model, Evaluation Metrics, and Recent Developments
专知会员服务
41+阅读 · 2020年5月30日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
30+阅读 · 2019年10月18日
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
Auto-Sizing the Transformer Network: Improving Speed, Efficiency, and Performance for Low-Resource Machine Translation
专知会员服务
49+阅读 · 2019年10月17日
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
Connections between Support Vector Machines, Wasserstein distance and gradient-penalty GANs
专知会员服务
35+阅读 · 2019年10月17日
Stabilizing Transformers for Reinforcement Learning
Stabilizing Transformers for Reinforcement Learning
专知会员服务
60+阅读 · 2019年10月17日
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
Deep Learning Based Detection and Correction of Cardiac MR Motion Artefacts During Reconstruction for High-Quality Segmentation
专知会员服务
58+阅读 · 2019年10月17日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
31+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
154+阅读 · 2019年10月12日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
41+阅读 · 2019年10月9日
热门VIP内容
相关资讯
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
强化学习的Unsupervised Meta-Learning
强化学习的Unsupervised Meta-Learning
CreateAMind
18+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
disentangled-representation-papers
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
STRCF for Visual Object Tracking
STRCF for Visual Object Tracking
统计学习与视觉计算组
14+阅读 · 2018年5月29日
Focal Loss for Dense Object Detection
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
IJCAI | Cascade Dynamics Modeling with Attention-based RNN
KingsGarden
13+阅读 · 2017年7月16日
From Softmax to Sparsemax-ICML16（1）
From Softmax to Sparsemax-ICML16（1）
KingsGarden
73+阅读 · 2016年11月26日
相关论文
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Arxiv
0+阅读 · 2月22日
Best of Both Worlds: Regret Minimization versus Minimax Play
Arxiv
0+阅读 · 2月17日
Checking Trustworthiness of Probabilistic Computations in a Typed Natural Deduction System
Arxiv
0+阅读 · 2月13日
Global Convergence Rate of Deep Equilibrium Models with General Activations
Arxiv
0+阅读 · 2月13日
Properties of Wasserstein Gradient Flows for the Sliced-Wasserstein Distance
Arxiv
0+阅读 · 2月10日
Complexity of Minimal Faithful Permutation Degree for Fitting-free Groups
Arxiv
0+阅读 · 2月9日
Still More Shades of Null: An Evaluation Suite for Responsible Missing Value Imputation
Arxiv
0+阅读 · 2月5日
Asynchronous Fault-Tolerant Language Decidability for Runtime Verification of Distributed Systems
Arxiv
0+阅读 · 1月31日
Single-Letter Characterization of the Mismatched Distortion-Rate Function
Arxiv
0+阅读 · 1月23日
Inferring Past Human Actions in Homes with Abductive Reasoning
Arxiv
0+阅读 · 1月22日
相关基金
Hamilton-Jacibi方程的弱KAM理论
国家自然科学基金
1+阅读 · 2017年12月31日
城市“建成环境——空间行为”的多尺度影响关系与机理研究
国家自然科学基金
11+阅读 · 2017年12月31日
“Fishes-in-net” 酵母孢子微胶囊式近平滑假丝酵母SCRII酶有机相高效手性合成机制研究
国家自然科学基金
2+阅读 · 2016年12月31日
Musielak-Orlicz-Sobolev 空间中的迹嵌入及其应用
国家自然科学基金
1+阅读 · 2015年12月31日
高频ZnO/IDT/SiO2/金刚石SAW乳腺癌抗原免疫传感器研究
国家自然科学基金
0+阅读 · 2015年12月31日
基于自主学习的Ad hoc Agent序贯决策研究
国家自然科学基金
41+阅读 · 2015年12月31日
Schr？dinger-Poisson方程守恒DDG方法研究
国家自然科学基金
2+阅读 · 2015年12月31日
PPP项目争端谈判及其治理机制研究
国家自然科学基金
2+阅读 · 2015年12月31日
动态Gr？bner 基与GVW算法
国家自然科学基金
0+阅读 · 2014年12月31日
“杰文斯”悖论、能效政策改进与“双控目标”分解
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员
Top