Preference Elicitation for Single Crossing Domain
Authors: Palash Dey, Neeldhara Misra
IJCAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The main contribution of our work is to provide polynomial time algorithms with low query complexity for preference elicitation in all the above cases. Further, we show that the query complexities of our algorithms are optimal up to constant factors for all but one of the above cases. We also prove lower bounds on the query complexity of preference elicitation for the domain of single crossing profiles; these bounds match the upper bounds up to constant factors (for a large number of voters) for all the six scenarios above except the case when we know a single crossing ordering of the voters and we have a random access to the voters; in this case, the upper and lower bounds match up to a factor of O(m). |
| Researcher Affiliation | Academia | Palash Dey Indian Institute of Science, Bangalore palash@csa.iisc.ernet.in Neeldhara Misra Indian Institute of Technology, Gandhinagar mail@neeldhara.com |
| Pseudocode | Yes | Algorithm 1 Elicit(C , R , ) Input: A set of candidates C = {ci i [m]}, an ordering R = c1 cm of C , a voter Output: Preference ordering of voter on C; Algorithm 2 Preference Elicit( ) Input: Sn Output: Profile of all the voters; Algorithm 3 Same(R , ) Input: R = c1 c2 cm L(C), [n] Output: TRUE if the preference of the th voter is R ; FALSE oth- erwise; Algorithm 4 Preference Elicit Unknown SCOrdering( ) Input: Sn Output: Profile of all the voters |
| Open Source Code | No | The paper does not provide any statement about making its source code publicly available or a link to a code repository. |
| Open Datasets | No | This paper is theoretical and does not involve experiments with datasets. |
| Dataset Splits | No | This paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | This paper is theoretical and does not describe experimental hardware specifications. |
| Software Dependencies | No | This paper is theoretical and does not describe specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |