Discrete convex analysis: A tool for economics and game theory
Discrete convex analysis: A tool for economics and game theory
复制标题
DOI：
10.22574/jmid.2016.12.005
复制
发表时间：
2016-12
期刊：
影响因子：
--
通讯作者：
K. Murota
中科院分区：
文献类型：
--
作者：
K. Murota
本文提出将离散凸分析作为经济学和博弈论中的一种工具。离散凸分析是近二十年来发展起来的一种新的离散数学和最优化框架。最近，它被认为是分析不可分割的经济或博弈模型的有力工具。离散凸分析的主要特点是区分了整数或二元函数的两个凸性概念：M-凸性和L-凸性及其共轭关系。关键的事实是，其变体的M-凹性等同于经济学中的总替代性质。离散凸分析中的基本定理，如M-L共轭定理、离散分离定理和离散不动点定理，产生了经济学中的结构性结果，如均衡的存在性和均衡价格向量的格结构。离散凸分析中的算法提供了寻找均衡的迭代拍卖算法。
This paper presents discrete convex analysis as a tool for use in economics and game theory. Discrete convex analysis is a new framework of discrete mathematics and optimization, developed during the last two decades. Recently, it has been recognized as a powerful tool for analyzing economic or game models with indivisibilities. The main feature of discrete convex analysis is the distinction of two convexity concepts, M-convexity and L-convexity, for functions in integer or binary variables, together with their conjugacy relationship. The crucial fact is that M-concavity in its variant is equivalent to the gross substitutes property in economics. Fundamental theorems in discrete convex analysis such as the M-L conjugacy theorems, discrete separation theorems and discrete fixed point theorems yield structural results in economics such as the existence of equilibria and the lattice structure of equilibrium price vectors. Algorithms in discrete convex analysis provide iterative auction algorithms for finding equilibria.