AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Online (Budgeted) Social Choice
Joel Oren, Brendan Lucier

Last modified: 2014-06-21


We consider a classic social choice problem in an online setting. In each round, a decision maker observes a single agent's preferences overa set of $m$ candidates, and must choose whether to irrevocably add a candidate to a selection set of limited cardinality $k$. Each agent's (positional) score depends on the candidates in the set when he arrives, and the decision-maker's goal is to maximize average (over all agents) score. We prove that no algorithm (even randomized) can achieve an approximationfactor better than $O(\frac{\log\log m}{\log m})$. In contrast, if the agents arrive in random order, we present a $(1 - \frac{1}{e} - o(1))$-approximatealgorithm, matching a lower bound for the off-line problem.We show that improved performance is possible for natural input distributionsor scoring rules. Finally, if the algorithm is permitted to revoke decisions at a fixedcost, we apply regret-minimization techniques to achieve approximation $1 - \frac{1}{e} - o(1)$ even for arbitrary inputs.


online algorithms;competitive analysis;multi-winner social choice

Full Text: PDF