Online (Budgeted) Social Choice
Authors: Joel Oren, Brendan Lucier
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that no algorithm (even randomized) can achieve an approximation factor better than O( log log m log m ). In contrast, if the agents arrive in random order, we present a (1 1 e o(1))approximate algorithm, matching a lower bound for the offline problem. |
| Researcher Affiliation | Collaboration | Joel Oren University of Toronto, Canada oren@cs.toronto.edu Brendan Lucier Microsoft Research, New England,USA brlucier@microsoft.com |
| Pseudocode | Yes | Algorithm 1: Online Candidate Selection Algorithm Input: Candidate set A, parameters k and n, online sequence of preference profiles 1 Let t n2/3(log n + k log m); 2 Observe the first t agents, T = {σ(1), . . . , σ(t)}; 3 S Greedy(T, k); 4 Choose all candidates in S and let the process run to completion; |
| Open Source Code | No | The paper does not mention or provide any links to open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not describe the use of any publicly available or open datasets for training or evaluation. |
| Dataset Splits | No | The paper is theoretical and does not specify any training/validation/test splits, as it does not involve empirical data. |
| Hardware Specification | No | The paper does not specify any hardware used for experiments. |
| Software Dependencies | No | The paper does not specify any software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide details about hyperparameters or system-level training settings, as it does not involve empirical experiments. |