It is well known that cheating occurs in sports. In cup competitions, a common type of sports competition, one method of cheating is in manipulating the seeding to unfairly advantage a particular team. Previous empirical and theoretical studies of seeding manipulation have focused on competitions with unrestricted seeding. However, real cup competitions often place restrictions on seedings to ensure fairness, wide geographic interest, and so on. In this paper, we perform an extensive empirical study of seeding manipulation under comprehensive and realistic sets of restrictions. A generalized random model of competition problems is proposed. This model creates a realistic range of problem instances that are used to identify the sets of seeding restrictions that are hard to manipulate in practice. We end with a discussion of the implications of this work and recommendations for organizing competitions so as to prevent or reduce the opportunities for manipulating the seeding.

Binary aggregation studies problems in which individuals express yes/no choices over a number of possibly correlated issues, and these individual choices need to be aggregated into a collective choice. We show how several classical frameworks of Social Choice Theory, particularly preference and judgment aggregation, can be viewed as binary aggregation problems by designing an appropriate set of integrity constraints for each specific setting. We explore the generality of this framework, showing that it makes available useful techniques both to prove theoretical results, such as a new impossibility theorem in preference aggregation, and to analyse practical problems, such as the characterisation of safe agendas in judgment aggregation in a syntactic way. The framework also allows us to formulate a general definition of paradox that is independent of the domain under consideration, which gives rise to the study of the class of aggregation procedures of generalised dictatorships.

We consider scenarios where several agents must aggregate their preferences over a large set of candidates with a combinatorial structure. That is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider a sequential procedure that chooses one candidate by asking the agents to vote on one variable at a time. While some properties of this procedure have been already studied, here we focus on independence of irrelevant alternatives, non-dictatorship, and strategy-proofness. Also, we perform an experimental study that shows that the proposed sequential procedure yields a considerable saving in time with respect to a non-sequential approach, while the winners satisfy the agents just as well, independently of the variable ordering and of the presence of coalitions of agents.

We consider a framework for preference aggregation on multiple binary issues, where agents' preferences are represented by (possibly cyclic) CP-nets. We focus on the majority aggregation of the individual CP-nets, which is the CP-net where the direction of each edge of the hypercube is decided according to the majority rule. First we focus on hypercube Condorcet winners (HCWs); in particular, we show that, assuming a uniform distribution for the CP-nets, the probability that there exists at least one HCW is at least 1-1/e, and the expected number of HCWs is 1. Our experimental results confirm these results. We also show experimental results under the Impartial Culture assumption. We then generalize a few tournament solutions to select winners from (weighted) majoritarian CP-nets, namely Copeland, maximin, and Kemeny. For each of these, we address some social choice theoretic and computational issues.

A common problem for companies with strong business growth is that it is hard to find enough experienced staff to support expansion needs. This article is a case study of how one of the largest travel agencies in Hong Kong alleviated this problem by using AI to support decision-making and problem-solving so that their planners and controllers can work more effectively and efficiently to sustain business growth while maintaining consistent quality of service. AI is used in a mission critical fleet management system (FMS) that supports the scheduling and management of a fleet of luxury limousines for business travelers. The AI problem was modeled as a constraint satisfaction problem (CSP).

A common problem for companies with strong business growth is that it is hard to find enough experienced staff to support expansion needs. This problem is particular pronounced for operations planners and controllers who must be very highly knowledgeable and experienced with the business domain. This article is a case study of how one of the largest travel agencies in Hong Kong alleviated this problem by using AI to support decision-making and problem-solving so that their planners and controllers can work more effectively and efficiently to sustain business growth while maintaining consistent quality of service. AI is used in a mission critical fleet management system (FMS) that supports the scheduling and management of a fleet of luxury limousines for business travelers. The AI problem was modeled as a constraint satisfaction problem (CSP). The use of AI enabled the travel agency to sign up additional hotel partners, handle more orders and expand their fleet with their existing team of planners and controllers. Using modern web 2.0 architecture and proven AI technology, we were able to achieve low-risk implementation and deployment success with concrete and measurable business benefits.

Constraint propagation is one of the basic forms of inference in many logic-based reasoning systems. In this paper, we investigate constraint propagation for first-order logic (FO), a suitable language to express a wide variety of constraints. We present an algorithm with polynomial-time data complexity for constraint propagation in the context of an FO theory and a finite structure. We show that constraint propagation in this manner can be represented by a datalog program and that the algorithm can be executed symbolically, i.e., independently of a structure. Next, we extend the algorithm to FO(ID), the extension of FO with inductive definitions. Finally, we discuss several applications.

Machine learning is an established method of selecting algorithms to solve hard search problems. Despite this, to date no systematic comparison and evaluation of the different techniques has been performed and the performance of existing systems has not been critically compared to other approaches. We compare machine learning techniques for algorithm selection on real-world data sets of hard search problems. In addition to well-established approaches, for the first time we also apply statistical relational learning to this problem. We demonstrate that most machine learning techniques and existing systems perform less well than one might expect. To guide practitioners, we close by giving clear recommendations as to which machine learning techniques are likely to perform well based on our experiments.

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates some measure of desirability with each possible combination of values for those variables. However, the crucial question of the computational complexity of finding the optimal solution to a collection of soft constraints has so far received very little attention. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as 'as near as possible' or 'as soon as possible after', as well as crisp constraints such as 'greater than'. Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft binary constraint which is not in the class gives rise to a class of problems which is NP-hard.

Information about user preferences plays a key role in automated decision making. In many domains it is desirable to assess such preferences in a qualitative rather than quantitative way. In this paper, we propose a qualitative graphical representation of preferences that reflects conditional dependence and independence of preference statements under a ceteris paribus (all else being equal) interpretation. Such a representation is often compact and arguably quite natural in many circumstances. We provide a formal semantics for this model, and describe how the structure of the network can be exploited in several inference tasks, such as determining whether one outcome dominates (is preferred to) another, ordering a set outcomes according to the preference relation, and constructing the best outcome subject to available evidence.