Tool Auctions
Authors: Janosch Döcker, Britta Dorn, Ulle Endriss, Ronald de Haan, Sebastian Schneckenburger
AAAI 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We then study the computational complexity of tool auctions in detail, using methods from both classical and parameterized complexity theory. The core of this paper is devoted to testing this intuition. We provide a detailed complexity analysis of both the feasibility and the winner determination problem for tool auctions. While solving tool auctions, just like most other kinds of combinatorial auctions, is intractable in general, we are able to identify several special cases of practical interest where designing efficient algorithms is possible. In particular, we show that several relevant decision problems are either polynomial-time solvable or fixed-parameter-tractable. |
| Researcher Affiliation | Academia | Janosch D ocker University of T ubingen Germany Britta Dorn University of T ubingen Germany Ulle Endriss ILLC, University of Amsterdam The Netherlands Ronald de Haan ILLC, University of Amsterdam The Netherlands Sebastian Schneckenburger University of T ubingen Germany |
| Pseudocode | No | Algorithms are described in prose, e.g., 'We describe a greedy algorithm to construct Σ.' (Proof of Proposition 1), but no formal pseudocode blocks or 'Algorithm X' figures are present. |
| Open Source Code | No | The paper is theoretical and does not mention releasing any source code for the described methodology. |
| Open Datasets | No | This is a theoretical paper that does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper that does not discuss dataset splits (train/validation/test) as no empirical evaluation is performed. |
| Hardware Specification | No | This is a theoretical paper and does not mention any specific hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not mention any software dependencies with version numbers for replication. |
| Experiment Setup | No | This is a theoretical paper and does not contain experimental setup details like hyperparameters or training configurations. |