Complexity of Strategic Behavior in Multi-Winner Elections

Journal of Artificial Intelligence Research

Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems, under different formulations of the strategic agent’s goal.


On the Use of Automatically Acquired Examples for All-Nouns Word Sense Disambiguation

Journal of Artificial Intelligence Research

This article focuses on Word Sense Disambiguation (WSD), which is a Natural Language Processing task that is thought to be important for many Language Technology applications, such as Information Retrieval, Information Extraction, or Machine Translation. One of the main issues preventing the deployment of WSD technology is the lack of training examples for Machine Learning systems, also known as the Knowledge Acquisition Bottleneck. A method which has been shown to work for small samples of words is the automatic acquisition of examples. We have previously shown that one of the most promising example acquisition methods scales up and produces a freely available database of 150 million examples from Web snippets for all polysemous nouns in WordNet. This paper focuses on the issues that arise when using those examples, all alone or in addition to manually tagged examples, to train a supervised WSD system for all nouns. The extensive evaluation on both lexical-sample and all-words Senseval benchmarks shows that we are able to improve over commonly used baselines and to achieve top-rank performance. The good use of the prior distributions from the senses proved to be a crucial factor.


ICE: An Expressive Iterative Combinatorial Exchange

Journal of Artificial Intelligence Research

We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies.


Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach

Journal of Artificial Intelligence Research

Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns.


Adversarial Modeling Using Granular Computing

AAAI Conferences

We look at the problem of adverarial decision making. Our objectivel here is to try to replace the infinite regress inherent in adversarial making decisions problems with the use of knowledge about the adversary. We use granular computing and particularly the Dempster-Shafer belief structure to represent this knowledge. This allows us to turn the problem of adverarial decision making into a problem decision-making.under


A Simulation Model of Cultural Consensus and Persistent Conflict

AAAI Conferences

In this study we develop a highly simplified simulation of diffusion through a structured society. By testing diffusion of a single arbitrary trait through different social network structures we show that the type of social network can significantly extend the time required for a population to reach consensus. This is especially true of small-world networks where conflict may persist far longer than in other network structures. In addition, we demonstrate that with simple dynamic linking rules, a network may evolve in such a way that consensus is inhibited altogether and ideological diversity becomes entrenched. To assess simulation results and inform future versions of the model we describe results from a real-world case study in which networked actors experience persistent conflict. While results of the case study align with simulation output, they also reveal areas for substantial improvement to the model.


The Identification of Sequential Patterns Preceding the Occurrence of Political Events of Interest

AAAI Conferences

In this paper we present an approach to identifying patterns of behavior preceding political instability events in countries from sampled factor data. This process is based on the concept of state-space back-chaining. A list of sampled, quantized factor data sampled over a range of discrete times define a "state-space" of a country, and the list of quantized factor data associated with a country at a particular instance in time defines a state. The state of a country changes over time and instances of two countries changing in the same manner define a pattern. At some country states political instability events of interest (such as the onset of regime change, insurgency, ethnic violence, etc) may be observed to occur. We discuss a method to identify the set of factors which define a state space and pattern for combinations of selected political instability events of interest such as rebellion, insurgency, civil war, etc. This approach can be used to identify the observable behaviors before the occurrence of events of interest. The backwards chaining methodology is implemented in the Java programming language and run over a set of factor data. We present a pattern for domestic political crisis found using this method.


Bayesian Modeling using Belief Networks of Perceived Threat Levels Affected by Stratagemical Behavior Patterns

AAAI Conferences

During a counterinsurgency campaign, there are six main sociocultural factors affecting the host nation's (HN) populace's opinion of military operational effects. These factors were used as multiple indicators of overall perceived levels of a group's threat or fear (PLT) under a variety of scenarios and conditions. Belief Networks were used to model and compute a group's PLT factor and its corresponding classification level of threat or fear.


Stochastic Opponent Modeling Agents: A Case Study with Hamas

AAAI Conferences

In this paper, we describe a case study that shows how SOMA was used to model the behavior of the terrorist organization, Hamas. Our team, consisting of a mix of computer scientists, policy experts, and political scientists, were able to understand new facts about Hamas of which even seasoned Hamas experts may not have been aware. This paper briefly overviews SOMA rules, explains how several thousand SOMA rules for Hamas were automatically derived, and then describes a few key findings about Hamas, enabled by this framework.


SCIPR: A Computational Model to Simulate Cultural Identities for Predicting Reactions to Events

AAAI Conferences

Today's military missions are not against other nationstates. Rather, they are against irregular forces engaged in terrorist or insurgent activities. A large part of waging successful counterinsurgency campaigns involves reducing or eliminating local support for the insurgents by convincing people that it is in not in their interest to support or join an insurgency. The Simulation of Cultural Identities for Prediction of Reactions (SCIPR) tool is designed to help military planners answer the question: "How will a particular course of action (COA) or sequence of events affect the attitudes or actions of a particular population?" At the core of SCIPR is an agent based model where agents, in response to events, change their affiliations and their attitudes based on the principles of social identity theory (Tajfel, 1978) and Social Influence Theory (Tajfel & Turner, 1979).