标题： 效用最大化的隐式障碍：市场均衡的内点方法 显示英文标题

标题： The Implicit Barrier of Utility Maximization: An Interior-Point Approach for Market Equilibria

摘要： 我们研究具有可分商品和异质效用的交换市场中均衡的计算。 在本文中，我们重新审视更新\emph{仅}的多项式时间内部点策略，模拟价格的拍卖过程。 关键在于效用最大化中的\emph{隐式屏障}：当商品几乎免费时，效用会变得无界。 专注于一个普遍的效用类，我们将这一观察结果形式化为从原始和对偶视角出发的缩放Lipschitz连续性。 一个相关结果表明，计算高阶导数不需要额外努力；当收集最佳响应时，所有必要的信息都已就绪。 为了解决牛顿系统，我们提出了一种具有高概率保证的Hessian算子显式可逆近似，以及一个使线性系统的条件数最小化的缩放矩阵。 基于这些工具，我们设计了两种不精确的内部点方法。 其中一种方法具有 O(ln(1/{\epsilon })) 的复杂度速率。 在温和条件下，另一种方法实现了非渐近超线性收敛速率。 还介绍了扩展和初步实验。 显示英文摘要

摘要： We study the computation of equilibria in exchange markets with divisible goods and players endowed with heterogeneous utilities. In this paper, we revisit the polynomial-time interior-point strategies that update \emph{only} the prices, mirroring the t\^atonnement process. The key ingredient is the \emph{implicit barrier} inherent in the utility maximization: the utility turns unbounded when the goods are almost free of charge. Focusing on a ubiquitous class of utilities, we formalize this observation into Scaled Lipschitz Continuity for utility maximization from both the primal and dual perspectives. A companion result suggests that no additional effort is required for computing high-order derivatives; all the necessary information is readily available when collecting the best responses. To tackle the Newton systems, we present an explicitly invertible approximation of the Hessian operator with high probability guarantees, and a scaling matrix that minimizes the condition number of the linear system. Building on these tools, we design two inexact interior-point methods. One such method has O(ln(1/{\epsilon})) complexity rate. Under mild conditions, the other method achieves a non-asymptotic superlinear convergence rate. Extensions and preliminary experiments are presented.