اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدMost Competitive Mechanisms in Online Fair Division
68
0
0.0
(
0
)
نشر من قبل
Martin Aleksandrov D
تاريخ النشر
2020
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 division model where items arrive one by one and are allocated to agents via some mechanism. We consider four such online mechanisms: the popular Ranking matching mechanism adapted from online bipartite matching and the Like, Balanced Like and Maximum Like allocation mechanisms firstly introduced for online fair division problems. Our first contribution is that we perform a competitive analysis of these mechanisms with respect to the expected size of the matching, the utilitarian welfare, and the egalitarian welfare. We also suppose that an oracle can give a number of advice bits to the mechanisms. Our second contribution is to give several impossibility results; e.g. no mechanism can achieve the egalitarian outcome of the optimal offline mechanism supposing they receive partial advice from the oracle. Our third contribution is that we quantify the competitive performance of these four mechanisms w.r.t. the number of oracle requests they can make. We thus present a most-competitive mechanism for each objective.
قيم البحث
اقرأ أيضاً
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
ss, envy-freeness, and Pareto efficiency. We prove a number of impossibility results that justify why we consider relaxations of the properties, as well as why we consider restricted preference domains on which good axiomatic properties can be achieved. We propose two mechanisms that have good axiomatic fairness properties on restricted but common preference domains.
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
what expected outcomes are possible, what outcomes are necessary, and how to compute their exact outcomes. In general, we show that such questions are more tractable to compute for LIKE than for BALANCED LIKE. As LIKE is strategy-proof but BALANCED LIKE is not, we also consider the computational problem of how, with BALANCED LIKE, an agent can compute a strategic bid to improve their outcome. We prove that this problem is intractable in general.
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.
Behavioural economists have shown that people are often averse to inequality and will make choices to avoid unequal outcomes. In this paper, we consider how to allocate indivisible goods fairly so as to minimize inequality. We consider how this inter
acts with axiomatic properties such as envy-freeness, Pareto efficiency and strategy-proofness. We also consider the computational complexity of computing allocations minimizing inequality. Unfortunately, this is computationally intractable in general so we consider several tractable greedy online mechanisms that minimize inequality. Finally, we run experiments to explore the performance of these methods.
We consider fair division problems where indivisible items arrive one-by-one in an online fashion and are allocated immediately to agents who have additive utilities over these items. Many existing offline mechanisms do not work in this online settin
g. In addition, many existing axiomatic results often do not transfer from the offline to the online setting. For this reason, we propose here three new online mechanisms, as well as consider the axiomatic properties of three previously proposed online mechanisms. In this paper, we use these mechanisms and characterize classes of online mechanisms that are strategy-proof, and return envy-free and Pareto efficient allocations, as well as combinations of these properties. Finally, we identify an important impossibility result.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
