Logo image
Back
Fair and Efficient Online Allocations with Normalized Valuations
Conference proceeding   Open access

Fair and Efficient Online Allocations with Normalized Valuations

Vasilis Gkatzelis, Alexandros Psomas, Xizhi Tan and Assoc Advancement Artificial Intelligence
THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, v 35(6), pp 5440-5447
18 May 2021
DOI: https://doi.org/10.1609/aaai.v35i6.16685
url
https://doi.org/10.1609/aaai.v35i6.16685View
Published, Version of Record (VoR) Open

Abstract

Computer Science Computer Science, Artificial Intelligence Computer Science, Interdisciplinary Applications Education & Educational Research Education, Scientific Disciplines Science & Technology Social Sciences Technology
A set of divisible resources becomes available over a sequence of rounds and needs to be allocated immediately and irrevocably. Our goal is to distribute these resources to maximize fairness and efficiency. Achieving any non-trivial guarantees in an adversarial setting is impossible. However, we show that normalizing the agent values, a very common assumption in fair division, allows us to escape this impossibility. Our main result is an online algorithm for the case of two agents that ensures the outcome is fair while guaranteeing 91.6% of the optimal social welfare. We also show that this is near-optimal: there is no fair algorithm that guarantees more than 93.3% of the optimal social welfare.

Metrics

10 Record Views
9 citations in Web of Science
14 citations in Scopus

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
Web of Science research areas
Computer Science, Artificial Intelligence
Computer Science, Interdisciplinary Applications
Education, Scientific Disciplines
Logo image