How to Allocate Goods in an Online Market?

作者：Azar Yossi; Buchbinder Niv^*; Jain Kamal

来源：Algorithmica, 2016, 74(2): 589-601.

DOI：10.1007/s00453-014-9964-7

• Online algorithm
• Allocation
• Social welfare
• Fairness
• Market equilibrium

We study an online version of linear Fisher market. In this market there are buyers and a set of dividable goods to be allocated to the buyers. The utility that buyer derives from good is . Given an allocation in which buyer has utility we study a quality measure that is based on taking an average of the ratios with respect to any other allocation . Market equilibrium allocation is the optimal solution with respect to this measure. Our setting is online and so the allocation of each good should be done without any knowledge of the upcoming goods. We design an online algorithm for the problem that is only worse by a logarithmic factor than any other solution with respect to this quality measure, and in particular competes with the market equilibrium allocation. We prove a tight lower bound which shows that our algorithm is optimal up to constants. Our algorithm uses a primal dual convex programming scheme. To the best of our knowledge this is the first time that such a scheme is used in the online framework.

• 出版日期2016-2