Fair Resource Allocation in A Volatile Marketplace

We consider the setting where a seller must allocate a collection of goods to budgeted buyers, as exemplified by online advertising systems where platforms decide which impressions to serve to various advertisers. Such resource allocation problems are challenging for two reasons: (a) the seller must strike a balance between optimizing her own revenues and guaranteeing fairness to her (repeat) buyers and (b) the problem is inherently dynamic due to the uncertain, time-varying supply of goods available with the seller. We propose a stochastic approximation scheme akin to a dynamic market equilibrium. Our scheme relies on frequent re-solves of an Eisenberg-Gale convex program, and does not require the seller to have any knowledge about how goods arrival processes evolve over time. The scheme fully extracts buyer budgets (thus maximizing seller revenues), while at the same time provides a 0.47 approximation of the proportionally fair allocation of goods achievable in the offline case, as long as the supply of goods comes from a wide family of (possibly non-stationary) Gaussian processes. We then extend our results to a more general family of metrics called \alpha-fairness. Finally, we deal with a multi-objective problem where the seller is concerned with both the proportional fairness and efficiency of the allocation, and propose a hybrid algorithm which achieves a 0.27 bi-criteria guarantee against fairness and efficiency.

• Algorithms and Theory