Fair and Efficient Memory Sharing: Confronting Free Riders
Authors: Eric J. Friedman, Vasilis Gkatzelis, Christos-Alexandros Psomas, Scott Shenker1965-1972
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. Our Results We study the extent to which we can optimize the efficiency of memory sharing mechanisms that are guaranteed to be truthful and fair. As a crucial tool in creating the right incentives for the users, we consider two types of blocking, which we refer to as uniform and non-uniform... For instances with two users we show that uniform-blocking mechanisms cannot provide non-trivial efficiency guarantees, but using nonuniform blocking can surpass this obstacle. Specifically, we provide a nonuniform-blocking mechanism that is 83%-efficient, which is close to optimal. For instances with multiple users we show that uniform-blocking mechanisms fail to achieve any constant approximation of efficiency. However, once again, we provide a nonuniform-blocking mechanism that performs much better; surprisingly, this mechanism can guarantee a 1 1 e 63% approximation of efficiency for all instances, even with an arbitrary number of users. |
| Researcher Affiliation | Academia | Eric J. Friedman ICSI and UC Berkeley Vasilis Gkatzelis Drexel University Christos-Alexandros Psomas Carnegie Mellon University Scott Shenker ICSI and UC Berkeley |
| Pseudocode | Yes | Algorithm 2: * Buy-In mechanism for v1, v2 1. Algorithm 3: Buy-In mechanism for max{v1, v2} > 1. Algorithm 4: The Opt-Out mechanism. |
| Open Source Code | No | The paper does not mention or provide any links to open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. It focuses on mechanism design and theoretical analysis. |
| Dataset Splits | No | The paper is theoretical and does not involve data splits for validation or other experimental purposes. It provides proofs and theoretical guarantees. |
| Hardware Specification | No | The paper is theoretical and focuses on mechanism design and mathematical proofs. It does not describe any experimental setup involving specific hardware. |
| Software Dependencies | No | The paper is theoretical and does not describe any implementation details that would require specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and focuses on mechanism design and mathematical analysis. It does not describe any empirical experiment setup with hyperparameters or system-level settings. |