Online Elicitation of Necessarily Optimal Matchings
Authors: Jannik Peters5164-5172
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we study the problem of eliciting preferences of agents in the house allocation model... Most importantly, we answer an open question and give an online algorithm for eliciting an NRM matching in the next-best query model which is 3/2-competitive... we extend this field of research by introducing two new natural models of elicitation and by studying both the complexity of determining whether a necessarily optimal matching exists in them, and by giving online algorithms for these models. and Table 1: Overview over the lower (LB) and upper bounds (UB) on the possible competitiveness of online algorithms derived for eliciting Pareto optimal and rank-maximal matchings in the different query models. |
| Researcher Affiliation | Academia | Jannik Peters Research Group Efficient Algorithms, TU Berlin, Germany jannik.peters@tu-berlin.de |
| Pseudocode | Yes | Algorithm 1: Elicitation algorithm for Pareto optimal matchings in the hybrid query model and Algorithm 2: Elicitation algorithm for rank-maximal matchings in the next-best model |
| Open Source Code | No | The paper does not provide any statement or link regarding the public release of source code for the described methodologies. |
| Open Datasets | No | The paper is theoretical and does not use or refer to any specific publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data, therefore no training/test/validation splits are discussed. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithms and complexity analysis, not on implementation details. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and presents algorithms and their complexity without conducting empirical experiments, thus no experimental setup details like hyperparameters or training configurations are provided. |