Conference proceeding
Fair and Efficient Memory Sharing: Confronting Free Riders
THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, v 33(1), pp 1965-1972
17 Jul 2019
Abstract
A cache memory unit needs to be shared among n strategic agents. Each agent has different preferences over the files to be brought into memory. The goal is to design a mechanism that elicits these preferences in a truthful manner and outputs a fair and efficient memory allocation. A trivially truthful and fair solution would isolate each agent to a 1/n fraction of the memory. However, this could be very inefficient if the agents have similar preferences and, thus, there is room for cooperation. On the other hand, if the agents are not isolated, unless the mechanism is carefully designed, they have incentives to misreport their preferences and free ride on the files that others bring into memory. In this paper we explore the power and limitations of truthful mechanisms in this setting. We demonstrate that mechanisms blocking agents from accessing parts of the memory can achieve improved efficiency guarantees, despite the inherent inefficiencies of blocking.
Metrics
Details
- Title
- Fair and Efficient Memory Sharing: Confronting Free Riders
- Creators
- Eric J. Friedman - University of California, BerkeleyVasilis Gkatzelis - Drexel UniversityChristos-Alexandros Psomas - Carnegie Mellon Univ, Pittsburgh, PA 15213 USAScott Shenker - University of California, BerkeleyAAAI
- Publication Details
- THIRTY-THIRD AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE / THIRTY-FIRST INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE CONFERENCE / NINTH AAAI SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, v 33(1), pp 1965-1972
- Series
- AAAI Conference on Artificial Intelligence
- Publisher
- Assoc Advancement Artificial Intelligence
- Number of pages
- 8
- Grant note
- CCF-1755955; CCF-1216073; CNS-1161813; CNS-1704941 / National Science Foundation; National Science Foundation (NSF)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Computer Science
- Web of Science ID
- WOS:000485292601119
- Scopus ID
- 2-s2.0-85069054224
- Other Identifier
- 991021868727704721
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, Theory & Methods
- Engineering, Electrical & Electronic