文件名称：瓦尔拉斯和戈尔曼极形式平衡不等式的近似解-研究论文
文件大小：169KB
文件格式：PDF
更新时间：2024-06-30 04:00:06
Algorithmic game theory
最近 Cherchye 等人。 (2011) 将 Brown 和 Matzkin (1996) 引入的瓦尔拉斯均衡不等式重新表述为整数规划问题，并证明求解瓦尔拉斯均衡不等式是 NP 难的。 继 Brown 和 Shannon (2000) 之后，我们将瓦尔拉斯均衡不等式重新表述为对偶瓦尔拉斯均衡不等式。 Brown 和 Shannon 证明了瓦尔拉斯均衡不等式是可解的，当条件是对偶瓦尔拉斯均衡不等式是可解的。 我们表明，求解对偶瓦尔拉斯均衡不等式等效于求解 NP 难最小化问题。 近似定理是多项式时间算法，用于计算 NP 难最小化问题的近似解。 本文的主要贡献是等效 NP-hard 最小化问题的近似定理。 在这个定理中，我们提出了一种多项式时间算法，用于计算对偶瓦尔拉斯均衡不等式的近似解，其中收入的边际效用是统一有界的。 我们从可观察的市场数据中推导出近似程度的明确界限。 第二个贡献是导出了交换经济的戈尔曼极性形式的均衡不等式，其中每个消费者都被赋予了戈尔曼极性形式的间接效用函数。 如果收入的边际效用是一致有界的，那么我们证明了戈尔曼极坐标形式均衡不等式的类似近似定理。