The Fisher market is one of the most fundamental models for resource allocation problems in economic theory, wherein agents spend a budget of currency to buy goods that maximize their utilities, while producers sell capacity constrained goods in exchange for currency. However, the consideration of only two types of constraints, i.e., budgets of individual buyers and capacities of goods, makes Fisher markets less amenable for resource allocation settings when agents have additional linear constraints, e.g., knapsack and proportionality constraints. In this work, we introduce a modified Fisher market, where each agent may have additional linear constraints and show that this modification to classical Fisher markets fundamentally alters the properties of the market equilibrium as well as the optimal allocations. These properties of the modified Fisher market prompt us to introduce a budget perturbed social optimization problem (BP-SOP) and set prices based on the dual variables of BP-SOP's capacity constraints. To compute the budget perturbations, we develop a fixed point iterative scheme and validate its convergence through numerical experiments. Since this fixed point iterative scheme involves solving a centralized problem at each step, we propose a new class of distributed algorithms to compute equilibrium prices. In particular, we develop an Alternating Direction Method of Multipliers (ADMM) algorithm with strong convergence guarantees for Fisher markets with homogeneous linear constraints as well as for classical Fisher markets. In this algorithm, the prices are updated based on the tatonnement process, with a step size that is completely independent of the utilities of individual agents. Thus, our mechanism, both theoretically and computationally, overcomes a fundamental limitation of classical Fisher markets, which only consider capacity and budget constraints.
翻译:渔业市场是经济理论资源分配问题的最根本模式之一,在这种模式中,代理商花费一笔货币预算购买能最大限度地提高公用事业的商品,而生产者则以货币换取销售能力限制货物,然而,只考虑两种类型的制约因素,即个别买方的预算和货物能力,使渔业市场对资源分配环境不那么适合,因为代理商有额外的线性限制,如Knapsack和相称性限制。在这项工作中,我们引入一个修改的渔业市场,每个代理商都可能有额外的线性限制,并表明对传统渔业市场的这种修改从根本上改变了市场平衡和最佳分配的特性。修改后的渔业市场的这些特性促使我们引入一个预算过激的社会优化问题(BP-SOP),并根据BP-SOP能力限制的双重变量确定价格。为了计算预算渗透性和相称性,我们制定了一个固定点的迭接合机制,通过数字性试验来验证其趋同性。由于这一固定点迭接合机制需要解决每个步骤的集中问题,我们建议一种新的分配算法,以平衡价格和最佳分配的配置。