ﻻ يوجد ملخص باللغة العربية
Computing market equilibria is a problem of both theoretical and applied interest. Much research focuses on the static case, but in many markets items arrive sequentially and stochastically. We focus on the case of online Fisher markets: individuals have linear, additive utility and items drawn from a distribution arrive one at a time in an online setting. We define the notion of an equilibrium in such a market and provide a dynamics which converges to these equilibria asymptotically. An important use-case of market equilibria is the problem of fair division. With this in mind, we show that our dynamics can also be used as an online item-allocation rule such that the time-averaged allocations and utilities converge to those of a corresponding static Fisher market. This implies that other good properties of market equilibrium-based fair division such as no envy, Pareto optimality, and the proportional share guarantee are also attained in the online setting. An attractive part of the proposed dynamics is that the market designer does not need to know the underlying distribution from which items are drawn. We show that these convergences happen at a rate of $O(tfrac{log t}{t})$ or $O(tfrac{(log t)^2}{t})$ in theory and quickly in real datasets.
We study the problem of fairly dividing a heterogeneous resource, commonly known as cake cutting and chore division, in the presence of strategic agents. While a number of results in this setting have been established in previous works, they rely cru
We study a new but simple model for online fair division in which indivisible items arrive one-by-one and agents have monotone utilities over bundles of the items. We consider axiomatic properties of mechanisms for this model such as strategy-proofne
We study the problem of fairly allocating indivisible items to agents with different entitlements, which captures, for example, the distribution of ministries among political parties in a coalition government. Our focus is on picking sequences derive
This paper combines two key ingredients for online algorithms - competitive analysis (e.g. the competitive ratio) and advice complexity (e.g. the number of advice bits needed to improve online decisions) - in the context of a simple online fair divis
Two simple and attractive mechanisms for the fair division of indivisible goods in an online setting are LIKE and BALANCED LIKE. We study some fundamental computational problems concerning the outcomes of these mechanisms. In particular, we consider