Fair Allocation in Online Markets

A key characteristic of a successful online market is the large specific participation of agents (producers and consumers) on both definition sides of the market. While there has been a long line of tion problems, impressive work on understanding such markets in terms of main revenue maximizing (also called max-sum) objectives, particularly in the context of allocating online impressions to interested advertisers, fairness considerations have surprisingly not received much attention in online allocation algorithms. Allocations that are inherently fair to participating entities, we believe, will contribute significantly to retaining current participants and attracting new ones in the long run, thereby enhancing the performance of online markets. We give two generic online allocation algorithms to address this problem: the first algorithm only focuses on the max-min fairness objective whereas the second algorithm balances between the max-min and the max-sum objectives. We compare these algorithms with existing online allocation algorithms that are based on only the max-sum objective by performing experiments on real-world data in two different online markets. Moreover, we analytically show that both our algorithms have strong theoretical guarantees for their respective objectives.