Approximate Strategyproof Mechanisms for the Additively Separable Group Activity Selection Problem
Authors: Michele Flammini, Giovanna Varricchio
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We investigate strategyproof mechanisms in the Group Activity Selection Problem with the additively separable property. Namely, agents have distinct preferences for each activity and individual weights for the other agents. We evaluate our mechanisms in terms of their approximation ratio with respect to the maximum utilitarian social welfare. We first show that, for arbitrary nonnegative preferences, no deterministic mechanism can achieve a bounded approximation ratio. Thus, we provide a randomized k-approximate mechanism, where k is the number of activities, and a corresponding 2 2 k+1 lower bound. Furthermore, we propose a tight (2 1 k)-approximate randomized mechanism when activities are copyable. We then turn our attention to instances where preferences can only be unitary, that is 0 or 1. In this case, we provide a k-approximate deterministic mechanism, which we show to be the best possible one within the class of strategyproof and anonymous mechanisms. We also provide a general lower bound of Ω k when anonymity is no longer a constraint. Finally, we focus on unitary preferences and weights, and prove that, while any mechanism returning the optimum is not strategyproof, there exists a 2-approximate deterministic mechanism. (Abstract) |
| Researcher Affiliation | Academia | Michele Flammini1 , Giovanna Varricchio2 1Gran Sasso Science Institute, L Aquila, Italy 2Goethe University Frankfurt, Frankfurt am Main, Germany michele.flammini@gssi.it, varricchio@em.uni-frankfurt.de |
| Pseudocode | No | The paper describes mechanisms (e.g., 'Mechanism M1. It selects uniformly at random one activity and then assigns all the agents to it.'), but it does so in prose, not in a structured pseudocode or algorithm block format. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | No | The paper is theoretical and does not use datasets in the empirical sense. It discusses 'instances' for theoretical analysis but not publicly available datasets for training models. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not include details on experimental setup such as hyperparameters or training configurations. |