Strategyproof Mechanisms for Friends and Enemies Games
Authors: Michele Flammini, Bojana Kodric, Giovanna Varricchio1950-1957
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate strategyproof mechanisms for Friends and Enemies Games... We provide strategyproof mechanisms for both settings. More precisely, for FA we first present a deterministic napproximation mechanism, and then show that a much better result can be accomplished by resorting to randomization. Namely, we provide a randomized mechanism whose expected approximation ratio is 4, and arbitrarily close to 4 with high probability. For EA, we give a simple (1 + 2)napproximation mechanism, and show that its performance is asymptotically tight by proving that it is NP-hard to approximate the optimal solution within O(n1 ε) for any fixed ε > 0. |
| Researcher Affiliation | Academia | Michele Flammini, Bojana Kodric, Giovanna Varricchio Gran Sasso Science Institute, L Aquila, Italy {michele.flammini, bojana.kodric, giovanna.varricchio}@gssi.it |
| Pseudocode | Yes | Mechanism M4. Given an EA preference profile d, M4 1. enumerates the agents in N from 1 up to n; 2. sets C = ; 3. for i = 1 up to n if there exists j > i in the neighborhood of i in G d not matched yet, then C = C {i, j}, otherwise, C = C {i}; 4. returns C. |
| Open Source Code | No | The paper does not provide any explicit statements or links indicating that the source code for the methodology is openly available. |
| Open Datasets | No | The paper focuses on theoretical mechanisms and their approximation ratios, and does not involve experimental training on datasets. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical mechanisms and their analysis, and does not involve experimental procedures that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies or versions. |
| Experiment Setup | No | The paper is theoretical and does not include details on experimental setup or parameters. |