论文标题
随机在线费舍尔市场：静态定价限制和适应性增强
Stochastic Online Fisher Markets: Static Pricing Limits and Adaptive Enhancements
论文作者
论文摘要
费舍尔市场是资源分配的最基本模型之一。但是，计算费舍尔市场平衡价格的问题通常依赖于用户的预算和公用事业功能的完全了解，并且需要在所有用户同时出现的静态市场中进行交易。在这些实际考虑因素的激励下，我们研究了Fisher Markets的在线变体，其中具有私人公用事业和预算参数的用户，绘制了I.I.D.从分布中，顺序到达。在这种情况下，我们首先研究了静态定价算法的局限性，该算法为所有用户设定了统一的价格，沿两个绩效指标：（i）遗憾，即在在线算法和甲骨文之间的甲骨文和具有完整信息的甲骨文和（ii）违规行为的eisenberg-gale计划目标中的最佳差距，即相对范围，相对范围。鉴于静态定价的局限性，我们设计了自适应张贴定价算法，一种了解用户的预算和公用事业参数的分配，而另一个仅基于过去对用户消费的观察结果（即揭示了偏好反馈）的调整价格，并具有提高的绩效保证。最后，我们提出了数值实验，以将揭示的偏好算法的性能与几个基准测试进行比较。
Fisher markets are one of the most fundamental models for resource allocation. However, the problem of computing equilibrium prices in Fisher markets typically relies on complete knowledge of users' budgets and utility functions and requires transactions to happen in a static market where all users are present simultaneously. Motivated by these practical considerations, we study an online variant of Fisher markets, wherein users with privately known utility and budget parameters, drawn i.i.d. from a distribution, arrive sequentially. In this setting, we first study the limitations of static pricing algorithms, which set uniform prices for all users, along two performance metrics: (i) regret, i.e., the optimality gap in the objective of the Eisenberg-Gale program between an online algorithm and an oracle with complete information, and (ii) capacity violations, i.e., the over-consumption of goods relative to their capacities. Given the limitations of static pricing, we design adaptive posted-pricing algorithms, one with knowledge of the distribution of users' budget and utility parameters and another that adjusts prices solely based on past observations of user consumption, i.e., revealed preference feedback, with improved performance guarantees. Finally, we present numerical experiments to compare our revealed preference algorithm's performance to several benchmarks.
