Haris Aziz – Péter Biró – Ronald de Haan – Baharak Rastegari
Abstract
The assignment problem is one of the most well-studied settings in multi-agent resource allocation. Agents express preferences over indivisible items and then the items are allocated based on these preferences. Pareto optimality is regarded as a desirable property for the chosen allocation, requiring that no other allocation exists in which no agent is worse off and at least one agent is better of. We consider the assignment problem with the additional feature that agents’ preferences involve uncertainty. The setting with uncertainty leads to a number of interesting questions including the following ones. How to compute an assignment with the highest probability of being Pareto optimal? What is the complexity of computing the probability that a given assignment is Pareto optimal? Does there exist an assignment that is Pareto optimal with probability one? We consider these problems under five natural uncertainty models. For all of the models, we present a number of algorithmic and complexity results highlighting the differences and similarities in the complexity of the models. We also present some general characterization and algorithmic results that apply to large classes of uncertainty models.
Az MTA KRTK Közgazdaság-tudományi Intézet teljesítményéről Az MTA KRTK KTI a RePEc/IDEAS rangsorában, amely a világ közgazdaságtudományi tanszékeit és intézeteit rangsorolja publikációs teljesítményük alapján, ... Részletek »
Tisztelt Kollégák! Tudományos kutatóként, intézeti vezetőként egész életünkben a kutatói szabadság és felelősség elve vezetett bennünket. Meggyőződésünk, hogy a tudomány csak akkor érhet el ... Részletek »
MUNKAERŐPIACI TÜKÖR 2018 Szerkesztette: Fazekas Károly, Csillag Márton, Hermann Zoltán és Scharle Ágota Közgazdaság- és Regionális Tudományi Kutatóközpont, Budapest, 2019 ISSN 1586-460X Copyright © ... Részletek »
Török Ádám elnöki köszöntőjét követően ″Jobb ma egy veréb, mint holnap egy túzok? – Alternatív növekedési utak keresése a visegrádi országokban″ címmel tartott előadást ... Részletek »
Az idei közgazdasági Nobel-díjasok előadásai – A. Banerjee, E. Duflo, M. Kremer 2019 Nobel Prize Lectures in Economic Sciences at Aula Medica Karolinska Institutet ... Részletek »
