Truthful Aggregation of Budget Proposals with Proportionality Guarantees
Authors: Ioannis Caragiannis, George Christodoulou, Nicos Protopapas4917-4924
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main objective is to design truthful mechanisms with small α-approximation. We are able to provide effectively optimal mechanisms for the case of two and three projects. ... The analysis of this mechanism is substantially more involved than the case of two projects and en route to proving the approximation guarantee we characterize the instances bearing the maximum ℓ1-loss, for any moving phantom mechanism. We complement our results by showing matching impossibility results: First, we show that there exists no αapproximate moving phantom mechanism for any α < 1 1/m. ... The Non-Linear Program is presented in Figure 2. ... We solve these programs using the Gurobi Solver (Gurobi Optimization, LLC 2021). |
| Researcher Affiliation | Academia | Ioannis Caragiannis1, George Christodoulou2, Nicos Protopapas3 1 Aarhus University 2 Aristotle University of Thessaloniki 3 University of Liverpool |
| Pseudocode | No | The paper describes algorithms verbally and mathematically but does not include any formal pseudocode blocks or algorithm listings. |
| Open Source Code | No | The paper does not provide any links to open-source code or explicitly state that code for the described methodology is released. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and optimization problems. It does not involve training models on empirical datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, thus no validation splits are discussed. |
| Hardware Specification | No | The paper mentions using 'Gurobi Solver' for optimization but does not specify any hardware details like GPU/CPU models, memory, or cloud resources. |
| Software Dependencies | No | The paper mentions 'Gurobi Solver' but does not provide a specific version number. It also cites 'Liberti 2008' for the 'spatial Branch and Bound Method' but this is a reference, not a software dependency with a version. |
| Experiment Setup | Yes | To compute the maximum value of the NLP in Figure 2, we break this program in simpler programs, based on 3 conditions; first, depending on whether t < 1/2 or not, second, according to the signs of the vj xj terms on the objective function (in order to remove the absolute values), and finally, according to the types of the phantoms enclosing the medians. ... We solve these programs using the Gurobi Solver (Gurobi Optimization, LLC 2021). The solver uses the spatial Branch and Bound Method (see (Liberti 2008)), which returns a global maximum, if the program is feasible. The solver returns solutions with 10 5 error tolerance. |