In computational social choice, one important problem is to take the votes of a subelectorate (subset of the voters), and summarize them using a small number of bits. This needs to be done in such a way that, if all that we know is the summary, as well as the votes of voters outside the subelectorate, we can conclude which of the m alternatives wins. This corresponds to the notion of compilation complexity, the minimum number of bits required to summarize the votes for a particular rule, which was introduced by Chevaleyre et al. [IJCAI-09]. We study three different types of compilation complexity. The first, studied by Chevaleyre et al., depends on the size of the subelectorate but not on the size of the complement (the voters outside the subelectorate). The second depends on the size of the complement but not on the size of the subelectorate. The third depends on both. We first investigate the relations among the three types of compilation complexity. Then, we give upper and lower bounds on all three types of compilation complexity for the most prominent voting rules. We show that for l -approval (when l ≤ m /2), Borda, and Bucklin, the bounds for all three types are asymptotically tight, up to a multiplicative constant; for l-approval (when l > m /2), plurality with runoff, all Condorcet consistent rules that are based on unweighted majority graphs (including Copeland and voting trees), and all Condorcet consistent rules that are based on the order of pairwise elections (including ranked pairs and maximin), the bounds for all three types are asymptotically tight up to a multiplicative constant when the sizes of the subelectorate and its complement are both larger than m 1+ε for some ε > 0.

We consider settings in which voters vote in sequence, each voter knows the votes of the earlier voters and the preferences of the later voters, and voters are strategic. This can be modeled as an extensive-form game of perfect information, which we call a Stackelberg voting game. We first propose a dynamic-programming algorithm for finding the backward-induction outcome for any Stackelberg voting game when the rule is anonymous; this algorithm is efficient if the number of alternatives is no more than a constant. We show how to use compilation functions to further reduce the time and space requirements. Our main theoretical results are paradoxes for the backward-induction outcomes of Stackelberg voting games. We show that for any n ≥ 5 and any voting rule that satisfies nonimposition and with a low domination index, there exists a profile consisting of n voters, such that the backward-induction outcome is ranked somewhere in the bottom two positions in almost every voter’s preferences. Moreover, this outcome loses all but one of its pairwise elections. Furthermore, we show that many common voting rules have a very low (= 1) domination index, including all majority-consistent voting rules. For the plurality and nomination rules, we show even stronger paradoxes. Finally, using our dynamic-programming algorithm, we run simulations to compare the backward-induction outcome of the Stackelberg voting game to the winner when voters vote truthfully, for the plurality and veto rules. Surprisingly, our experimental results suggest that on average, more voters prefer the backward-induction outcome.

In many multiagent settings, a decision must be made based on the preferences of multiple agents, and agents may lie about their preferences if this is to their benefit. In mechanism design, the goal is to design procedures (mechanisms) for making the decision that work in spite of such strategic behavior, usually by making untruthful behavior suboptimal. In automated mechanism design, the idea is to computationally search through the space of feasible mechanisms, rather than to design them analytically by hand. Unfortunately, the most straightforward approach to automated mechanism design does not scale to large instances, because it requires searching over a very large space of possible functions. In this paper, we describe an approach to automated mechanism design that is computationally feasible. Instead of optimizing over all feasible mechanisms, we carefully choose a parameterized subfamily of mechanisms. Then we optimize over mechanisms within this family, and analyze whether and to what extent the resulting mechanism is suboptimal outside the subfamily. We demonstrate the usefulness of our approach with two case studies.

When agents have conflicting preferences over a set of alternatives and they want to make a joint decision, a natural way to do so is by voting. How to design and analyze desirable voting rules has been studied by economists for centuries. In recent decades, technological advances, especially those in internet economy, have introduced many new applications for voting theory. For example, we can rate movies based on people’s preferences, as done on many movie recommendation sites. However, in such new applications, we always encounter a large number of alternatives or an overwhelming amount of information, which makes computation in voting process a big challenge. Such challenges have led to a burgeoning area—computational social choice, aiming to address problems in computational aspects of preference representation and aggregation in a multi-agent scenario. The high-level goal of my research is to better understand and prevent the agents’ (strategic) behavior in voting systems, as well as to design computationally efficient ways for agents to present their preferences and make a joint decision.

This paper describes an online resource designed to aid in the creation of educational robotics programs where teams of mentors work with middle and high school students. This resource, The RoboCupJunior Primer, is based on five years of undergraduate mentoring experience in a local public school. The primary goals of the primer are threefold: first, to expose interested parties to the resources necessary for the creation of a RoboCup team; second, to provide a location for students to communicate with members of other teams and demonstrate specific examples of success; and third, to house an archive of lesson plans as well as tips for creating interesting and efficient lessons.

We present a novel approach for estimating the intrinsic dimensionality of certain point clouds: we assume that the points are sampled from a manifold M of dimension k , with k << D, and corrupted by D -dimensional noise. When M is linear, one may analyze this situation by SVD: with no noise one would obtain a rank k matrix, and noise may be treated as a perturbation of the covariance matrix. When M is a nonlinear manifold, global SVD may dramatically overestimate the intrinsic dimensionality. We introduce a multiscale version SVD and discuss how one can extract estimators for the intrinsic dimensionality that are highly robust to noise, while require a smaller sample size than current estimators.

Understanding the computational complexity of manipulation in elections is arguably the most central agenda in Computational Social Choice. One of the influential variations of the the problem involves a coalition of manipulators trying to make a favorite candidate win the election. Although the complexity of the problem is well-studied under the assumption that the voters are weighted, there were very few successful attempts to abandon this strong assumption. In this paper, we study the complexity of the unweighted coalitional manipulation problem (UCM) under several prominent voting rules. Our main result is that UCM is NP-complete under the maximin rule; this resolves an enigmatic open question. We then show that UCM is NP-complete under the ranked pairs rule, even with respect to a single manipulator. Furthermore, we provide an extreme hardness-of-approximation result for an optimization version of UCM under ranked pairs. Finally, we show that UCM under the Bucklin rule is in P.

AAAI 2008 Workshop Reports

AAAI was pleased to present the AAAI-08 Workshop Program, held Sunday and Monday, July 13–14, in Chicago, Illinois, USA. The program included the following 15 workshops: Advancements in POMDP Solvers; AI Education Workshop Colloquium; Coordination, Organizations, Institutions, and Norms in Agent Systems, Enhanced Messaging; Human Implications of Human-Robot Interaction; Intelligent Techniques for Web Personalization and Recommender Systems; Metareasoning: Thinking about Thinking; Multidisciplinary Workshop on Advances in Preference Handling; Search in Artificial Intelligence and Robotics; Spatial and Temporal Reasoning; Trading Agent Design and Analysis; Transfer Learning for Complex Tasks; What Went Wrong and Why: Lessons from AI Research and Applications; and Wikipedia and Artificial Intelligence: An Evolving Synergy.