Online (Budgeted) Social Choice


  • Joel Oren University of Toronto
  • Brendan Lucier Microsoft Research, New England



online algorithms, competitive analysis, multi-winner social choice


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.




How to Cite

Oren, J., & Lucier, B. (2014). Online (Budgeted) Social Choice. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



AAAI Technical Track: Multiagent Systems