Toby Walsh

IJCAI Conference 2025 Conference Paper

Distance Preservation Games

• Haris Aziz
• Hau Chan
• Patrick Lederer
• Shivika Narang
• Toby Walsh

We introduce and analyze distance preservation games (DPGs). In DPGs, agents express ideal distances to other agents and need to choose locations in the unit interval while preserving their ideal distances as closely as possible. We analyze the existence and computation of location profiles that are jump stable (i. e. , no agent can benefit by moving to another location) or welfare optimal for DPGs, respectively. Specifically, we prove that there are DPGs without jump stable location profiles and identify important cases where such outcomes always exist and can be computed efficiently. Similarly, we show that finding welfare optimal location profiles is NP-complete and present approximation algorithms for finding solutions with social welfare close to optimal. Finally, we prove that DPGs have a price of anarchy of at most 2.

IJCAI Conference 2025 Conference Paper

Equitable Mechanism Design for Facility Location

• Toby Walsh

We consider strategy proof mechanisms for facility location which maximize equitability between agents. As is common in the literature, we measure equitability with the Gini index. We first prove a simple but fundamental impossibility result that no strategy proof mechanism can bound the approximation ratio of the optimal Gini index of utilities for one or more facilities. We propose instead computing approximation ratios of the complemented Gini index of utilities, and consider how well both deterministic and randomized mechanisms approximate this. In addition, as Nash welfare is often put forwards as an equitable compromise between egalitarain and utilitarian outcomes, we consider how well mechanisms approximate the Nash welfare.

AAMAS Conference 2025 Conference Paper

Group Fairness in Multi-period Mobile Facility Location Problems

• Haris Aziz
• Hau Chan
• Xingchen Sha
• Toby Walsh
• Lirong Xia

We study the group-fair multi-period mobile facility location problems, where agents from different groups are located on a real line and arrive in different periods. Our goal is to locate 𝑘 mobile facilities at each period to serve the arriving agents in order to minimize the maximum total group-fair cost and the maximum average group-fair cost objectives that measure the costs or distances of groups of agents to their corresponding facilities across all periods. We first consider the problems from the algorithmic perspective for both group-fair cost objectives. We then consider the problems from the mechanism design perspective, where the agents’ locations and arrival periods are private. For both objectives, we design deterministic strategyproof mechanisms to elicit the agents’ locations and arrival periods truthfully while optimizing the group-fair cost objectives and show that our mechanisms have almost tight bounds on the approximation ratios for certain periods and settings. Finally, we discuss the extensions of our results to the online setting where agent arrival information is only known at each period.

AAMAS Conference 2025 Conference Paper

Shifting Power: Leveraging LLMs to Simulate Human Aversion in ABMs of Bilateral Financial Exchanges, A bond market study

• Alicia Vidler
• Toby Walsh

Bilateral markets, such as those for government bonds, involve decentralized and opaque transactions between market makers (MMs) and clients, posing significant challenges for traditional modeling approaches. To address these complexities, we introduce TRIBE an agent-based model (ABM) augmented with a large language model (LLM) to simulate human-like decision-making in trading environments. TRIBE leverages publicly available data and stylized facts to capture realistic trading dynamics, integrating human biases like risk aversion and ambiguity sensitivity into the decision-making processes of agents. Our research yields three key contributions: first, we demonstrate that integrating LLMs into ABMs, to enhance client agency, is feasible and enriches the simulation of agent behaviors in complex markets; second, we find that even slight trade aversion encoded within the LLM leads to a complete cessation of trading activity, highlighting the sensitivity of market dynamics to agents’ risk profiles; third, we show that incorporating human-like variability shifts power dynamics towards clients and can disproportionately affect the entire system, often resulting in systemic agent collapse across simulations. These findings underscore the emergent properties that arise when introducing stochastic, human-like decision processes, revealing new system behaviors that enhance the realism and complexity of artificial trading societies.

ECAI Conference 2024 Conference Paper

Approximate Mechanism Design for Facility Location with Multiple Objectives

• Toby Walsh

We identify strategy proof mechanisms for facility location that simultaneously approximate well both the maximum distance from the nearest facility and the minimum utility of any agent. Somewhat surprisingly, while the deterministic MEDIAN and the randomized ENDORAV mechanisms perform optimally with respect to approximating the maximum distance, neither perform optimally with respect to approximating the minimum utility. With deterministic mechanisms for locating a single facility, we prove that the MIDORNEAREST mechanism is optimal with respect to approximating both the maximum distance and the minimum utility. By comparison, the MEDIAN mechanism has an unbounded approximation ratio for approximating the minimum utility. With randomized mechanisms for locating a single facility, we construct the first mechanism that is optimal with respect to approximating the minimum utility. For deterministic and randomized mechanisms locating two or more facilities, we identify strategy proof mechanisms that are within a constant factor of optimal with respect to both objectives.

AIJ Journal 2024 Journal Article

Corrigendum to “Learning constraints through partial queries” [Artificial Intelligence 319 (2023) 103896]

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

AAAI Conference 2024 Conference Paper

Fair Lotteries for Participatory Budgeting

• Haris Aziz
• Xinhang Lu
• Mashbat Suzuki
• Jeremy Vollen
• Toby Walsh

In pursuit of participatory budgeting (PB) outcomes with broader fairness guarantees, we initiate the study of lotteries over discrete PB outcomes. As the projects have heterogeneous costs, the amount spent may not be equal ex ante and ex post. To address this, we develop a technique to bound the amount by which the ex-post spend differs from the ex-ante spend---the property is termed budget balanced up to one project (BB1). With respect to fairness, we take a best-of-both-worlds perspective, seeking outcomes that are both ex-ante and ex-post fair. Towards this goal, we initiate a study of ex-ante fairness properties in PB, including Individual Fair Share (IFS), Unanimous Fair Share (UFS) and their stronger variants, as well as Group Fair Share (GFS). We show several incompatibility results between these ex-ante fairness notions and existing ex-post concepts based on justified representation. One of our main contributions is a randomized algorithm which simultaneously satisfies ex-ante Strong UFS, ex-post full justified representation (FJR) and ex-post BB1 for PB with binary utilities.

AIJ Journal 2024 Journal Article

Manipulation and peer mechanisms: A survey

• Matthew Olckers
• Toby Walsh

In peer mechanisms, the competitors for a prize also determine who wins. Each competitor may be asked to rank, grade, or nominate peers for the prize. Since the prize can be valuable, such as financial aid, course grades, or an award at a conference, competitors may be tempted to manipulate the mechanism. We survey approaches to prevent or discourage the manipulation of peer mechanisms. We conclude our survey by identifying several important research challenges.

IJCAI Conference 2024 Conference Paper

Mechanisms That Play a Game, Not Toss a Coin

• Toby Walsh

Randomized mechanisms can have good normative properties compared to their deterministic counter-parts. However, randomized mechanisms are problematic in several ways such as in their verifiability. We propose here to de-randomize such mechanisms by having agents play a game instead of tossing a coin. The game is designed so agents play randomly, and this play injects “randomness” into the mechanism. Surprisingly this de-randomization retains many of the good normative properties of the original randomized mechanism but gives a mechanism that is deterministic and easy, for instance, to audit. We consider three general purpose methods to de-randomize mechanisms, and apply these to six different domains: voting, facility location, task allocation, school choice, peer selection, and resource allocation. We propose a number of novel de-randomized mechanisms for these six domains with good normative properties (such as equilibria in which agents sincerely report preferences over the original problem). In one domain, we additionally show that a new and desirable normative property emerges as a result of de-randomization. property emerges as a result of de-randomization.

ECAI Conference 2024 Conference Paper

Mitigating Bias: Model Pruning for Enhanced Model Fairness and Efficiency

• Harsh Kasyap
• Ugur-Ilker Atmaca
• Michela Iezzi
• Toby Walsh
• Carsten Maple

Machine learning models have been instrumental in making decisions across domains, like mortgage lending and risk assessment in finance. However, these models have been found susceptible to biases, causing unfair decisions for a specific group of individuals. Such bias is generally based on some protected (or sensitive) attributes, such as age, sex, or race, and is still prevalent due to historical context or algorithmic bias. There have been several efforts to ensure equal opportunities for each individual/group, based on creditworthiness, rather than any social bias. Several pre-, in- and post-processing bias mitigation techniques have been proposed. However, these techniques perform data transformation or design new constraint/cost functions, which are task-specific, to achieve a fair prediction. Such techniques even require further access to the complete training/testing data. This paper proposes a novel post-processing bias mitigation technique that employs a model interpretation strategy to find the responsible model weights causing the bias. Pruning only a few model weights exhibits group fairness in model predictions while maintaining competitive accuracy levels, thus aligning with the goals of fairness and efficiency in decision-making. The proposed scheme requires access to only a few data samples representing the protected attributes, without exposing the complete training data. Through extensive experiments with multiple census datasets/methods, we demonstrate the efficacy of our approach, achieving up to a significant 50% reduction in bias while preserving the overall accuracy.

JAIR Journal 2024 Journal Article

Mixed Fair Division: A Survey

• Shengxin Liu
• Xinhang Lu
• Mashbat Suzuki
• Toby Walsh

Fair division considers the allocation of scarce resources among agents in such a way that every agent gets a fair share. It is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions and future directions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (mixed goods), and (iii) indivisible goods with subsidy which can be viewed like a divisible good.

AAAI Conference 2024 Conference Paper

Mixed Fair Division: A Survey

• Shengxin Liu
• Xinhang Lu
• Mashbat Suzuki
• Toby Walsh

The fair allocation of resources to agents is a fundamental problem in society and has received significant attention and rapid developments from the game theory and artificial intelligence communities in recent years. The majority of the fair division literature can be divided along at least two orthogonal directions: goods versus chores, and divisible versus indivisible resources. In this survey, besides describing the state of the art, we outline a number of interesting open questions in three mixed fair division settings: (i) indivisible goods and chores, (ii) divisible and indivisible goods (i.e., mixed goods), and (iii) fair division of indivisible goods with subsidy.

AAMAS Conference 2024 Conference Paper

Proportional Fairness in Obnoxious Facility Location

• Alexander Lam
• Haris Aziz
• Bo Li
• Fahimeh Ramezani
• Toby Walsh

We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, we show that our proportional fairness axioms are incompatible with strategyproofness, and prove asymptotically tight 𝑒𝑝𝑠𝑖𝑙𝑜𝑛-price of anarchy and stability bounds for proportionally fair welfare-optimal mechanisms. In the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare. Finally, we prove existence results for two extensions to our model.

AAAI Conference 2023 Conference Paper

Fairness Concepts for Indivisible Items with Externalities

• Haris Aziz
• Warut Suksompong
• Zhaohong Sun
• Toby Walsh

We study a fair allocation problem of indivisible items under additive externalities in which each agent also receives utility from items that are assigned to other agents. This allows us to capture scenarios in which agents benefit from or compete against one another. We extend the well-studied properties of envy-freeness up to one item (EF1) and envy-freeness up to any item (EFX) to this setting, and we propose a new fairness concept called general fair share (GFS), which applies to a more general public decision making model. We undertake a detailed study and present algorithms for finding fair allocations.

AIJ Journal 2023 Journal Article

Learning constraints through partial queries

• Christian Bessiere
• Clément Carbonnel
• Anton Dries
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper

Learning constraint networks is known to require a number of membership queries exponential in the number of variables. In this paper, we learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm, called QuAcq2, that, given a negative example, elucidates a constraint of the target network in a number of queries logarithmic in the size of the example. The whole constraint network can then be learned with a polynomial number of partial queries. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. We provide a version of QuAcq2 with a cutoff mechanism that controls the time to generate a query. Our experiments illustrate the good behavior of QuAcq2 in practice, especially in the case where QuAcq2 is executed to learn the missing constraints in a partially filled constraint model. Our experiments also show that QuAcq2 requires significantly fewer queries to learn a network than its predecessor QuAcq1.

AAMAS Conference 2023 Conference Paper

Proportional Fairness in Obnoxious Facility Location

• Haris Aziz
• Alexander Lam
• Bo Li
• Fahimeh Ramezani
• Toby Walsh

We consider the obnoxious facility location problem (in which agents prefer the facility location to be far from them) and propose a hierarchy of distance-based proportional fairness concepts for the problem. These fairness axioms ensure that groups of agents at the same location are guaranteed to be a distance from the facility proportional to their group size. We consider deterministic and randomized mechanisms, and compute tight bounds on the price of proportional fairness. In the deterministic setting, not only are our proportional fairness axioms incompatible with strategyproofness, the Nash equilibria may not guarantee welfare within a constant factor of the optimal welfare. On the other hand, in the randomized setting, we identify proportionally fair and strategyproof mechanisms that give an expected welfare within a constant factor of the optimal welfare.

NeurIPS Conference 2022 Conference Paper

Random Rank: The One and Only Strategyproof and Proportionally Fair Randomized Facility Location Mechanism

• Haris Aziz
• Alexander Lam
• Mashbat Suzuki
• Toby Walsh

Proportionality is an attractive fairness concept that has been applied to a range of problems including the facility location problem, a classic problem in social choice. In our work, we propose a concept called Strong Proportionality, which ensures that when there are two groups of agents at different locations, both groups incur the same total cost. We show that although Strong Proportionality is a well-motivated and basic axiom, there is no deterministic strategyproof mechanism satisfying the property. We then identify a randomized mechanism called Random Rank (which uniformly selects a number $k$ between $1$ to $n$ and locates the facility at the $k$'th highest agent location) which satisfies Strong Proportionality in expectation. Our main theorem characterizes Random Rank as the unique mechanism that achieves universal truthfulness, universal anonymity, and Strong Proportionality in expectation among all randomized mechanisms. Finally, we show via the AverageOrRandomRank mechanism that even stronger ex-post fairness guarantees can be achieved by weakening universal truthfulness to strategyproofness in expectation.

IJCAI Conference 2022 Conference Paper

Strategy Proof Mechanisms for Facility Location with Capacity Limits

• Toby Walsh

An important feature of many real world facility location problems are capacity limits on the number of agents served by each facility. We provide a comprehensive picture of strategy proof mechanisms for facility location problems with capacity constraints that are anonymous and Pareto optimal. First, we prove a strong characterization theorem. For locating two identical facilities with capacity limits and no spare capacity, the INNERPOINT mechanism is the unique strategy proof mechanism that is both anonymous and Pareto optimal. Second, when there is spare capacity, we identify a more general class of strategy proof mechanisms that interpolates smoothly between INNERPOINT and ENDPOINT which are anonymous and Pareto optimal. Third, with two facilities of different capacities, we prove a strong impossibility theorem that no mechanism can be both anonymous and Pareto optimal except when the capacities differ by just a single agent. Fourth, with three or more facilities we prove a second impossibility theorem that no mechanism can be both anonymous and Pareto optimal even when facilities have equal capacity. Our characterization and impossibility results are all minimal as multiple mechanisms exist if we drop one property.

JAAMAS Journal 2021 Journal Article

Fair allocation of indivisible goods and chores

• Haris Aziz
• Ioannis Caragiannis
• Toby Walsh

Abstract We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” that yield positive utility for the agents. There is also some work in which the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario in which an agent may have positive or negative utility for each item. This framework captures, e. g. , fair task assignment, where agents can experience both positive and negative utility for each task. We demonstrate that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations that satisfy certain fairness and efficiency properties and examine the complexity of computing such allocations.

IJCAI Conference 2021 Conference Paper

Fair Pairwise Exchange among Groups

• Zhaohong Sun
• Taiki Todo
• Toby Walsh

We study the pairwise organ exchange problem among groups motivated by real-world applications and consider two types of group formulations. Each group represents either a certain type of patient-donor pairs who are compatible with the same set of organs, or a set of patient-donor pairs who reside in the same region. We address a natural research question, which asks how to match a maximum number of pairwise compatible patient-donor pairs in a fair and individually rational way. We first propose a natural fairness concept that is applicable to both types of group formulations and design a polynomial-time algorithm that checks whether a matching exists that satisfies optimality, individual rationality, and fairness. We also present several running time upper bounds for computing such matchings for different graph structures.

AAAI Conference 2020 Conference Paper

Facility Location Problem with Capacity Constraints: Algorithmic and Mechanism Design Perspectives

• Haris Aziz
• Hau Chan
• Barton Lee
• Bo Li
• Toby Walsh

We consider the facility location problem in the onedimensional setting where each facility can serve a limited number of agents from the algorithmic and mechanism design perspectives. From the algorithmic perspective, we prove that the corresponding optimization problem, where the goal is to locate facilities to minimize either the total cost to all agents or the maximum cost of any agent is NP-hard. However, we show that the problem is fixed-parameter tractable, and the optimal solution can be computed in polynomial time whenever the number of facilities is bounded, or when all facilities have identical capacities. We then consider the problem from a mechanism design perspective where the agents are strategic and need not reveal their true locations. We show that several natural mechanisms studied in the uncapacitated setting either lose strategyproofness or a bound on the solution quality for the total or maximum cost objective. We then propose new mechanisms that are strategyproof and achieve approximation guarantees that almost match the lower bounds.

IJCAI Conference 2020 Conference Paper

Fair Division: The Computer Scientist’s Perspective

• Toby Walsh

I survey recent progress on a classic and challenging problem in social choice: the fair division of indivisible items. I discuss how a computational perspective has provided interesting insights into and understanding of how to divide items fairly and efficiently. This has involved bringing to bear tools such as those used in knowledge representation, computational complexity, approximation methods, game theory, online analysis and communication complexity.

ICLR Conference 2020 Conference Paper

In Search for a SAT-friendly Binarized Neural Network Architecture

• Nina Narodytska
• Hongce Zhang
• Aarti Gupta
• Toby Walsh

Analyzing the behavior of neural networks is one of the most pressing challenges in deep learning. Binarized Neural Networks are an important class of networks that allow equivalent representation in Boolean logic and can be analyzed formally with logic-based reasoning tools like SAT solvers. Such tools can be used to answer existential and probabilistic queries about the network, perform explanation generation, etc. However, the main bottleneck for all methods is their ability to reason about large BNNs efficiently. In this work, we analyze architectural design choices of BNNs and discuss how they affect the performance of logic-based reasoners. We propose changes to the BNN architecture and the training procedure to get a simpler network for SAT solvers without sacrificing accuracy on the primary task. Our experimental results demonstrate that our approach scales to larger deep neural networks compared to existing work for existential and probabilistic queries, leading to significant speed ups on all tested datasets.

AAAI Conference 2020 Conference Paper

Online Fair Division: A Survey

• Martin Aleksandrov
• Toby Walsh

We survey a burgeoning and promising new research area that considers the online nature of many practical fair division problems. We identify wide variety of such online fair division problems, as well as discuss new mechanisms and normative properties that apply to this online setting. The online nature of such fair division problems provides both opportunities and challenges such as the possibility to develop new online mechanisms as well as the difficulty of dealing with an uncertain future.

IJCAI Conference 2019 Conference Paper

Fair Allocation of Indivisible Goods and Chores

• Haris Aziz
• Ioannis Caragiannis
• Ayumi Igarashi
• Toby Walsh

We consider the problem of fairly dividing a set of items. Much of the fair division literature assumes that the items are ``goods'' i. e. , they yield positive utility for the agents. There is also some work where the items are ``chores'' that yield negative utility for the agents. In this paper, we consider a more general scenario where an agent may have negative or positive utility for each item. This framework captures, e. g. , fair task assignment, where agents can have both positive and negative utilities for each task. We show that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations satisfying certain fairness and efficiency properties and further study the complexity of computing such allocations.

IJCAI Conference 2019 Conference Paper

Fair Online Allocation of Perishable Goods and its Application to Electric Vehicle Charging

• Enrico H. Gerding
• Alvaro Perez-Diaz
• Haris Aziz
• Serge Gaspers
• Antonia Marcu
• Nicholas Mattei
• Toby Walsh

We consider mechanisms for the online allocation of perishable resources such as energy or computational power. A main application is electric vehicle charging where agents arrive and leave over time. Unlike previous work, we consider mechanisms without money, and a range of objectives including fairness and efficiency. In doing so, we extend the concept of envy-freeness to online settings. Furthermore, we explore the trade-offs between different objectives and analyse their theoretical properties both in online and offline settings. We then introduce novel online scheduling algorithms and compare them in terms of both their theoretical properties and empirical performance.

AAMAS Conference 2019 Conference Paper

From Matching with Diversity Constraints to Matching with Regional Quotas

• Haris Aziz
• Serge Gaspers
• Zhaohong Sun
• Toby Walsh

In the past few years, several new matching models have been proposed and studied that take into account complex distributional constraints. Relevant lines of work include (1) school choice with diversity constraints where students have (possibly overlapping) types and (2) hospital-doctor matching where various regional quotas are imposed. In this paper, we present a polynomial-time reduction to transform an instance of (1) to an instance of (2) and we show how the feasibility and stability of corresponding matchings are preserved under the reduction. Our reduction provides a formal connection between two important strands of work on matching with distributional constraints. We then apply the reduction in two ways. Firstly, we show that it is NP-complete to check whether a feasible and stable outcome for (1) exists. Due to our reduction, these NP-completeness results carry over to setting (2). In view of this, we help unify some of the results that have been presented in the literature. Secondly, if we have positive results for (2), then we have corresponding results for (1). One key conclusion of our results is that further developments on axiomatic and algorithmic aspects of hospital-doctor matching with regional quotas will result in corresponding results for school choice with diversity constraints.

AIJ Journal 2019 Journal Article

Strategyproof peer selection using randomization, partitioning, and apportionment

• Haris Aziz
• Omer Lev
• Nicholas Mattei
• Jeffrey S. Rosenschein
• Toby Walsh

Peer reviews, evaluations, and selections are a fundamental aspect of modern science. Funding bodies the world over employ experts to review and select the best proposals from those submitted for funding. The problem of peer selection, however, is much more general: a professional society may want to give a subset of its members awards based on the opinions of all members; an instructor for a Massive Open Online Course (MOOC) or an online course may want to crowdsource grading; or a marketing company may select ideas from group brainstorming sessions based on peer evaluation. We make three fundamental contributions to the study of peer selection, a specific type of group decision-making problem, studied in computer science, economics, and political science. First, we propose a novel mechanism that is strategyproof, i. e. , agents cannot benefit by reporting insincere valuations. Second, we demonstrate the effectiveness of our mechanism by a comprehensive simulation-based comparison with a suite of mechanisms found in the literature. Finally, our mechanism employs a randomized rounding technique that is of independent interest, as it solves the apportionment problem that arises in various settings where discrete resources such as parliamentary representation slots need to be divided proportionally.

AIJ Journal 2018 Journal Article

Fixing balanced knockout and double elimination tournaments

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.

AAAI Conference 2018 Conference Paper

The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goods

• Jing Wu Lian
• Nicholas Mattei
• Renee Noble
• Toby Walsh

We propose a novel mechanism for solving the assignment problem when we have a two sided matching problem with preferences from one side (the agents/reviewers) over the other side (the objects/papers) and both sides have capacity constraints. The assignment problem is a fundamental in both computer science and economics with application in many areas including task and resource allocation. Drawing inspiration from work in multi-criteria decision making and social choice theory we use order weighted averages (OWAs), a parameterized class of mean aggregators, to propose a novel and flexible class of algorithms for the assignment problem. We show an algorithm for finding an Σ-OWA assignment in polynomial time, in contrast to the NP-hardness of finding an egalitarian assignment. We demonstrate through empirical experiments that using Σ-OWA assignments can lead to high quality and more fair assignments.

AAAI Conference 2018 Conference Paper

Verifying Properties of Binarized Deep Neural Networks

• Nina Narodytska
• Shiva Kasiviswanathan
• Leonid Ryzhyk
• Mooly Sagiv
• Toby Walsh

Understanding properties of deep neural networks is an important challenge in deep learning. In this paper, we take a step in this direction by proposing a rigorous way of verifying properties of a popular class of neural networks, Binarized Neural Networks, using the well-developed means of Boolean satisfiability. Our main contribution is a construction that creates a representation of a binarized neural network as a Boolean formula. Our encoding is the first exact Boolean representation of a deep neural network. Using this encoding, we leverage the power of modern SAT solvers along with a proposed counterexample-guided search procedure to verify various properties of these networks. A particular focus will be on the critical property of robustness to adversarial perturbations. For this property, our experimental results demonstrate that our approach scales to medium-size deep neural networks used in image classification tasks. To the best of our knowledge, this is the first work on verifying properties of deep neural networks using an exact Boolean encoding of the network.

AAAI Conference 2017 Conference Paper

Algorithms for Max-Min Share Fair Allocation of Indivisible Chores

• Haris Aziz
• Gerhard Rauchecker
• Guido Schryen
• Toby Walsh

We consider Max-min Share (MmS) fair allocations of indivisible chores (items with negative utilities). We show that allocation of chores and classical allocation of goods (items with positive utilities) have some fundamental connections but also differences which prevent a straightforward application of algorithms for goods in the chores setting and viceversa. We prove that an MmS allocation does not need to exist for chores and computing an MmS allocation - if it exists - is strongly NP-hard. In view of these non-existence and complexity results, we present a polynomial-time 2approximation algorithm for MmS fairness for chores. We then introduce a new fairness concept called optimal MmS that represents the best possible allocation in terms of MmS that is guaranteed to exist. We use connections to parallel machine scheduling to give (1) a polynomial-time approximation scheme for computing an optimal MmS allocation when the number of agents is fixed and (2) an effective and efficient heuristic with an ex-post worst-case analysis.

IJCAI Conference 2017 Conference Paper

Mechanisms for Online Organ Matching

• Nicholas Mattei
• Abdallah Saffidine
• Toby Walsh

Matching donations from deceased patients to patients on the waiting list account for over 85\% of all kidney transplants performed in Australia. We propose a simple mechanisms to perform this matching and compare this new mechanism with the more complex algorithm currently under consideration by the Organ and Tissue Authority in Australia. We perform a number of experiments using real world data provided by the Organ and Tissue Authority of Australia. We find that our simple mechanism is more efficient and fairer in practice compared to the other mechanism currently under consideration.

JAIR Journal 2017 Journal Article

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. They work in multiple stages where the result of each stage may influence the result of the next stage. Both procedures proceed according to a given linear order of the alternatives, an agenda. We obtain the following results for both voting procedures: On the one hand, deciding whether one can make a specific alternative win by reporting insincere preferences by the fewest number of voters, the Manipulation problem, or whether there is a suitable ordering of the agenda, the Agenda Control problem, takes polynomial time. On the other hand, our experimental studies with real-world data indicate that most preference profiles cannot be manipulated by only few voters and a successful agenda control is typically impossible. If the voters' preferences are incomplete, then deciding whether an alternative can possibly win is NP-hard for both procedures. Whilst deciding whether an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive procedure.

IJCAI Conference 2017 Conference Paper

Pure Nash Equilibria in Online Fair Division

• Martin Aleksandrov
• Toby Walsh

We consider a fair division setting in which items arrive one by one and are allocated to agents via two existing mechanisms: LIKE and BALANCED LIKE. The LIKE mechanism is strategy-proof whereas the BALANCED LIKE mechanism is not. Whilst LIKE is strategy-proof, we show that it is not group strategy-proof. Indeed, our first main result is that no online mechanism is group strategy-proof. We then focus on pure Nash equilibria of these two mechanisms. Our second main result is that computing a pure Nash equilibrium is tractable for LIKE and intractable for BALANCED LIKE. Our third main result is that there could be multiple such profiles and counting them is also intractable even when we restrict our attention to equilibria with a specific property (e. g. envy-freeness, Pareto efficiency).

JAIR Journal 2016 Journal Article

A Study of Proxies for Shapley Allocations of Transport Costs

• Haris Aziz
• Casey Cahan
• Charles Gretton
• Philip Kilby
• Nicholas Mattei
• Toby Walsh

We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.

IJCAI Conference 2016 Conference Paper

Control of Fair Division

• Haris Aziz
• Ildik
• oacute; Schlotter
• Toby Walsh

We initiate the study of control actions in fair division problems where a benevolent or malicious central organizer changes the structure of the fair division problem for self-interest or to benefit one, some or all agents. One motivation for such control is to improve fairness by minimally changing the problem. As a case study, we consider the problem of adding or deleting a small number of items to improve fairness. For two agents, we present polynomial-time algorithms for adding or deleting the minimum number of items to achieve ordinal envy-freeness. For three agents, we show that both problems, as well as the more basic problem of checking whether an envy-free allocation exists, are NP-complete. This closes a problem open for over five years. Our framework leads to a number of interesting directions in the area of fair division.

AIJ Journal 2016 Journal Article

H-index manipulation by merging articles: Models, theory, and experiments

• René van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author's profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles; this may affect the H-index. We analyze the (parameterized) computational complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatibility graph whose edges correspond to plausible merges. Moreover, we consider several different measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles (that is, for compatibility graphs that are cliques), then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only if one merges articles with highly dissimilar titles.

ECAI Conference 2016 Conference Paper

h-Index Manipulation by Undoing Merges

• René van Bevern
• Christian Komusiewicz
• Hendrik Molter
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

The h-index is an important bibliographic measure used to assess the performance of researchers. Van Bevern et al. [Artif. Intel. , to appear] showed that, despite computational worst-case hardness results, substantial manipulation of the h-index of Google Scholar author profiles is possible by merging articles. Complementing this work, we study the opposite operation, the splitting of articles, which is arguably the more natural operation for manipulation and which is also allowed within Google Scholar. We present numerous results on computational complexity (from linear-time algorithms to parameterized computational hardness results) and empirically indicate that at least small improvements of the h-index by splitting merged articles are easily achievable.

IJCAI Conference 2016 Conference Paper

Interdependent Scheduling Games

• Andres Abeliuk
• Haris Aziz
• Gerardo Berbeglia
• Serge Gaspers
• Petr Kalina
• Nicholas Mattei
• Dominik Peters
• Paul Stursberg

We propose a model of interdependent scheduling games in which each player controls a set of services that they schedule independently. A player is free to schedule his own services at any time; however, each of these services only begins to accrue reward for the player when all predecessor services, which may or may not be controlled by the same player, have been activated. This model, where players have interdependent services, is motivated by the problems faced in planning and coordinating large-scale infrastructures, e. g. , restoring electricity and gas to residents after a natural disaster or providing medical care in a crisis when different agencies are responsible for the delivery of staff, equipment, and medicine. We undertake a game-theoretic analysis of this setting and in particular consider the issues of welfare maximization, computing best responses, Nash dynamics, and existence and computation of Nash equilibria.

IJCAI Conference 2016 Conference Paper

Ranking Constraints

• Christian Bessiere
• Emmanuel Hebrard
• George Katsirelos
• Zeynep Kiziltan
• Toby Walsh

We need to reason about rankings of objects in a wide variety of domains including information retrieval, sports tournaments, bibliometrics, and statistics. We propose a global constraint therefore for modeling rankings. One important application for rankings is in reasoning about the correlation or uncorrelation between two sequences. For example, we might wish to have consecutive delivery schedules correlated to make it easier for clients and employees, or uncorrelated to avoid predictability and complacence. We therefore also consider global correlation constraints between rankings. For both ranking and correlation constraints, we propose efficient filtering algorithms and decompositions, and report experimental results demonstrating the promise of our proposed approach.

AAAI Conference 2016 Conference Paper

Strategic Behaviour When Allocating Indivisible Goods

• Toby Walsh

We survey some recent research regarding strategic behaviour in resource allocation problems, focusing on the fair division of indivisible goods. We consider a number of computational questions like how a single strategic agent misreports their preferences to ensure a particular outcome, and how agents compute a Nash equilibrium when they all act strategically. We also identify a number of future directions like dealing with non-additive utilities, and partial or probabilistic information about the preferences of other agents.

AAAI Conference 2016 Conference Paper

Strategyproof Peer Selection: Mechanisms, Analyses, and Experiments

• Haris Aziz
• Omer Lev
• Nicholas Mattei
• Jeffrey Rosenschein
• Toby Walsh

We study an important crowdsourcing setting where agents evaluate one another and, based on these evaluations, a subset of agents are selected. This setting is ubiquitous when peer review is used for distributing awards in a team, allocating funding to scientists, and selecting publications for conferences. The fundamental challenge when applying crowdsourcing in these settings is that agents may misreport their reviews of others to increase their chances of being selected. We propose a new strategyproof (impartial) mechanism called Dollar Partition that satisfies desirable axiomatic properties. We then show, using a detailed experiment with parameter values derived from target real world domains, that our mechanism performs better on average, and in the worst case, than other strategyproof mechanisms in the literature.

ECAI Conference 2016 Conference Paper

Welfare of Sequential Allocation Mechanisms for Indivisible Goods

• Haris Aziz 0001
• Thomas Kalinowski
• Toby Walsh
• Lirong Xia

Sequential allocation is a simple and attractive mechanism for the allocation of indivisible goods used in a number of real world settings. In sequential allocation, agents pick items according to a policy, the order in which agents take turns. Sequential allocation will return an allocation which is Pareto efficient - no agent can do better without others doing worse. However, sequential allocation may not return the outcome that optimizes the social welfare. We consider therefore the relationship between the welfare and the efficiency of the allocations returned by sequential allocation mechanisms. We then study some simple computational questions about what welfare is possible or necessary depending on the choice of policy. Over half the problems we study turn out to be tractable, and we give polynomial time algorithms to compute them. We also consider a novel control problem in which the Chair chooses a policy to improve social welfare. Again, many of the control problems we study turn out to be tractable, and our results give polynomial time algorithms. In this case, tractability is a good thing so that the Chair can improve the social welfare of the allocation.

AAAI Conference 2015 Conference Paper

Challenges in Resource and Cost Allocation

• Toby Walsh

Many models and mechanisms in resource and cost allocation have been developed that are simple and abstract. By means of two case studies, I argue that it is now timely to consider richer models for the fair division of resources and for the allocation of costs. Such models should have features like asynchronicity which reflect more of the true complexity of many fair division and cost allocation problems met in the real world. I suggest that computation can be used in such models to increase both efficiency and fairness of the allocations. As a result, we may be able to do more with fewer resources and greater fairness.

IJCAI Conference 2015 Conference Paper

Equilibria Under the Probabilistic Serial Rule

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

The probabilistic serial (PS) rule is a prominent randomized rule for assigning indivisible goods to agents. Although it is well known for its good fairness and welfare properties, it is not strategyproof. In view of this, we address several fundamental questions regarding equilibria under PS. Firstly, we show that Nash deviations under the PS rule can cycle. Despite the possibilities of cycles, we prove that a pure Nash equilibrium is guaranteed to exist under the PS rule. We then show that verifying whether a given profile is a pure Nash equilibrium is coNP-complete, and computing a pure Nash equilibrium is NP-hard. For two agents, we present a linear-time algorithm to compute a pure Nash equilibrium which yields the same assignment as the truthful profile. Finally, we conduct experiments to evaluate the quality of the equilibria that exist under the PS rule, finding that the vast majority of pure Nash equilibria yield social welfare that is at least that of the truthful profile.

AIJ Journal 2015 Journal Article

Fair assignment of indivisible objects under ordinal preferences

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Toby Walsh

We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied for these fairness notions. We also characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.

IJCAI Conference 2015 Conference Paper

H-Index Manipulation by Merging Articles: Models, Theory, and Experiments

• Ren
• eacute; van Bevern
• Christian Komusiewicz
• Rolf Niedermeier
• Manuel Sorge
• Toby Walsh

An author’s profile on Google Scholar consists of indexed articles and associated data, such as the number of citations and the H-index. The author is allowed to merge articles, which may affect the H-index. We analyze the parameterized complexity of maximizing the H-index using article merges. Herein, to model realistic manipulation scenarios, we define a compatability graph whose edges correspond to plausible merges. Moreover, we consider multiple possible measures for computing the citation count of a merged article. For the measure used by Google Scholar, we give an algorithm that maximizes the H-index in linear time if the compatibility graph has constant-size connected components. In contrast, if we allow to merge arbitrary articles, then already increasing the H-index by one is NP-hard. Experiments on Google Scholar profiles of AI researchers show that the H-index can be manipulated substantially only by merging articles with highly dissimilar titles, which would be easy to discover.

AAAI Conference 2015 Conference Paper

Justified Representation in Approval-Based Committee Voting

• Haris Aziz
• Markus Brill
• Vincent Conitzer
• Edith Elkind
• Rupert Freeman
• Toby Walsh

We consider approval-based committee voting, i. e. , the setting where each voter approves a subset of candidates, and these votes are then used to select a fixed-size set of winners (committee). We propose a natural axiom for this setting, which we call justified representation (JR). This axiom requires that if a large enough group of voters exhibits agreement by supporting the same candidate, then at least one voter in this group has an approved candidate in the winning committee. We show that for every list of ballots it is possible to select a committee that provides JR. We then check if this axiom is fulfilled by well-known approval-based voting rules. We show that the answer is negative for most of the rules we consider, with notable exceptions of PAV (Proportional Approval Voting), an extreme version of RAV (Reweighted Approval Voting), and, for a restricted preference domain, MAV (Minimax Approval Voting). We then introduce a stronger version of the JR axiom, which we call extended justified representation (EJR), and show that PAV satisfies EJR, while other rules do not. We also consider several other questions related to JR and EJR, including the relationship between JR/EJR and unanimity, and the complexity of the associated algorithmic problems.

IJCAI Conference 2015 Conference Paper

Online Fair Division: Analysing a Food Bank Problem

• Martin Damyanov Aleksandrov
• Haris Aziz
• Serge Gaspers
• Toby Walsh

We study an online model of fair division designed to capture features of a real world charity problem. We consider two simple mechanisms for this model in which agents simply declare what items they like. We analyse axiomatic properties of these mechanisms such as strategy-proofness and envy freeness. Finally, we perform a competitive analysis and compute the price of anarchy.

IJCAI Conference 2015 Conference Paper

Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

• Robert Bredereck
• Jiehua Chen
• Rolf Niedermeier
• Toby Walsh

We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or agenda controls is tractable for both procedures, our real-world experimental results indicate that most elections cannot be manipulated by a few voters and agenda control is typically impossible. If the voter preferences are incomplete, then finding possible winners is NP-hard for both procedures. Whereas finding necessary winners is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

IJCAI Conference 2015 Conference Paper

Possible and Necessary Allocations via Sequential Mechanisms

• Haris Aziz
• Toby Walsh
• Lirong Xia

A simple mechanism for allocating indivisible resources is sequential allocation in which agents take turns to pick items. We focus on possible and necessary allocation problems, checking whether allocations of a given form occur in some or all mechanisms for several commonly used classes of sequential allocation mechanisms. In particular, we consider whether a given agent receives a given item, a set of items, or a subset of items for natural classes of sequential allocation mechanisms: balanced, recursively balanced, balanced alternation, and strict alternation. We present characterizations of the allocations that result respectively from the classes, which extend the well-known characterization by Brams and King [2005] for policies without restrictions. In addition, we examine the computational complexity of possible and necessary allocation problems for these classes.

IJCAI Conference 2015 Conference Paper

Reasoning about Connectivity Constraints

• Christian Bessiere
• Emmanuel Hebrard
• George Katsirelos
• Toby Walsh

Many problems in computational sustainability involve constraints on connectivity. When designing a new wildlife corridor, we need it to be geographically connected. When planning the harvest of a forest, we need new areas to harvest to be connected to areas that have already been harvested so we can access them easily. And when town planning, we need to connect new homes to the existing utility infrastructure. To reason about connectivity, we propose a new family of global connectivity constraints. We identify when these constraints can be propagated tractably, and give some efficient, typically linear time propagators for when this is the case. We report results on several benchmark problems which demonstrate the efficiency of our propagation algorithms and the promise offered by reasoning globally about connectivity.

AIJ Journal 2014 Journal Article

Complexity of and algorithms for the manipulation of Borda, Nanson's and Baldwin's voting rules

• Jessica Davies
• George Katsirelos
• Nina Narodytska
• Toby Walsh
• Lirong Xia

We investigate manipulation of the Borda voting rule, as well as two elimination style voting rules, Nanson's and Baldwin's voting rules, which are based on Borda voting. We argue that these rules have a number of desirable computational properties. For unweighted Borda voting, we prove that it is NP-hard for a coalition of two manipulators to compute a manipulation. This resolves a long-standing open problem in the computational complexity of manipulating common voting rules. We prove that manipulation of Baldwin's and Nanson's rules is computationally more difficult than manipulation of Borda, as it is NP-hard for a single manipulator to compute a manipulation. In addition, for Baldwin's and Nanson's rules with weighted votes, we prove that it is NP-hard for a coalition of manipulators to compute a manipulation with a small number of candidates. Because of these NP-hardness results, we compute manipulations using heuristic algorithms that attempt to minimise the number of manipulators. We propose several new heuristic methods. Experiments show that these methods significantly outperform the previously best known heuristic method for the Borda rule. Our results suggest that, whilst computing a manipulation of the Borda rule is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice. In contrast to the Borda rule, our experiments with Baldwin's and Nanson's rules demonstrate that both of them are often more difficult to manipulate in practice. These results suggest that elimination style voting rules deserve further study.

AAAI Conference 2014 Conference Paper

Fixing a Balanced Knockout Tournament

• Haris Aziz
• Serge Gaspers
• Simon Mackenzie
• Nicholas Mattei
• Paul Stursberg
• Toby Walsh

Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner.

ECAI Conference 2014 Conference Paper

How Hard Is It to Control an Election by Breaking Ties?

• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

We study the computational complexity of controlling the result of an election by breaking ties strategically. This problem is equivalent to the problem of deciding the winner of an election under parallel universes tie-breaking. When the chair of the election is only asked to break ties to choose between one of the co-winners, the problem is trivially easy. However, in multi-round elections, we prove that it can be NP-hard for the chair to compute how to break ties to ensure a given result. Additionally, we show that the form of the tie-breaking function can increase the opportunities for control.

ECAI Conference 2014 Conference Paper

The Computational Impact of Partial Votes on Strategic Voting

• Nina Narodytska
• Toby Walsh

In many real world elections, agents are not required to rank all candidates. We study three of the most common methods used to modify voting rules to deal with such partial votes. These methods modify scoring rules (like the Borda count), elimination style rules (like single transferable vote) and rules based on the tournament graph (like Copeland) respectively. We argue that with an elimination style voting rule like single transferable vote, partial voting does not change the situations where strategic voting is possible. However, with scoring rules and rules based on the tournament graph, partial voting can increase the situations where strategic voting is possible. As a consequence, the computational complexity of computing a strategic vote can change. For example, with Borda count, the complexity of computing a strategic vote can decrease or stay the same depending on how we score partial votes.

ECAI Conference 2014 Conference Paper

The PeerRank Method for Peer Assessment

• Toby Walsh

We propose the PeerRank method for peer assessment. This constructs a grade for an agent based on the grades proposed by the agents evaluating the agent. Since the grade of an agent is a measure of their ability to grade correctly, the PeerRank method weights grades by the grades of the grading agent. The PeerRank method also provides an incentive for agents to grade correctly. As the grades of an agent depend on the grades of the grading agents, and as these grades themselves depend on the grades of other agents, we define the PeerRank method by a fixed point equation similar to the PageRank method for ranking web-pages. We identify some formal properties of the PeerRank method (for example, it satisfies axioms of unanimity, no dummy, no discrimination and symmetry), discuss some examples, compare with related work and evaluate the performance on some synthetic data. Our results show considerable promise, reducing the error in grade predictions by a factor of 2 or more in many cases over the natural baseline of averaging peer grades.

IJCAI Conference 2013 Conference Paper

A Social Welfare Optimal Sequential Allocation Procedure

• Thomas Kalinowski
• Nina Narodytska
• Toby Walsh

We consider a simple sequential allocation procedure for sharing indivisible items between agents in which agents take turns to pick items. Supposing additive utilities and independence between the agents, we show that the expected utility of each agent is computable in polynomial time. Using this result, we prove that the expected utilitarian social welfare is maximized when agents take alternate turns. We also argue that this mechanism remains optimal when agents behave strategically.

IJCAI Conference 2013 Conference Paper

Constraint Acquisition via Partial Queries

• Christian Bessiere
• Remi Coletta
• Emmanuel Hebrard
• George Katsirelos
• Nadjib Lazaar
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We learn constraint networks by asking the user partial queries. That is, we ask the user to classify assignments to subsets of the variables as positive or negative. We provide an algorithm that, given a negative example, focuses onto a constraint of the target network in a number of queries logarithmic in the size of the example. We give information theoretic lower bounds for learning some simple classes of constraint networks and show that our generic algorithm is optimal in some cases. Finally we evaluate our algorithm on some benchmarks.

IJCAI Conference 2013 Conference Paper

Detecting and Exploiting Subproblem Tractability

• Christian Bessiere
• Clement Carbonnel
• Emmanuel Hebrard
• George Katsirelos
• Toby Walsh

Constraint satisfaction problems may be nearly tractable. For instance, most of the relations in a problem might belong to a tractable language. We introduce a method to take advantage of this fact by computing a backdoor to this tractable language. The method can be applied to many tractable classes for which the membership test is itself tractable. We introduce therefore two polynomial membership testing algorithms, to check if a language is closed under a majority or conservative Mal’tsev polymorphism, respectively. Then we show that computing a minimal backdoor for such classes is fixed parameter tractable (FPT) if the tractable subset of relations is given, and W[2]complete otherwise. Finally, we report experimental results on the XCSP benchmark set. We identified a few promising problem classes where problems were nearly closed under a majority polymorphism and small backdoors could be computed.

IJCAI Conference 2013 Conference Paper

On the Complexity of Global Scheduling Constraints under Structural Restrictions

• Geoffrey Chu
• Serge Gaspers
• Nina Narodytska
• Andreas Schutt
• Toby Walsh

This paper investigates the manpower allocation problem with time windows and job-teaming constraints (MAPTWTC), a practical scheduling and routing problem that tries to synchronize workers’ schedules to complete all tasks. We first provide an integer programming model for the problem and discuss its properties. Next, we show that tree data structure can be used to represent the MAPTWTC solutions, and its optimal solution can be obtained from one of trees by solving a minimum cost flow model for each worker type. Consequently, we develop for the problem a novel tabu search algorithm employing search operators based on the tree data structure. Finally, we prove the effectiveness of the tabu search algorithm by computational experiments on two sets of instances.

IJCAI Conference 2013 Conference Paper

On the Complexity of Global Scheduling Constraints under Structural Restrictions

• Geoffrey Chu
• Serge Gaspers
• Nina Narodytska
• Andreas Schutt
• Toby Walsh

We investigate the computational complexity of two global constraints, CUMULATIVE and INTERDISTANCE. These are key constraints in modeling and solving scheduling problems. Enforcing domain consistency on both is NP-hard. However, restricted versions of these constraints are often sufficient in practice. Some examples include scheduling problems with a large number of similar tasks, or tasks sparsely distributed over time. Another example is runway sequencing problems in air-traffic control, where landing periods have a regular pattern. Such cases can be characterized in terms of structural restrictions on the constraints. We identify a number of such structural restrictions and investigate how they impact the computational complexity of propagating these global constraints. In particular, we prove that such restrictions often make propagation tractable.

AAMAS Conference 2013 Conference Paper

Possible and Necessary Winner Problem in Social Polls

• Serge Gaspers
• Victor Naroditskiy
• Nina Narodytska
• Toby Walsh

Social networks are increasingly being used to conduct polls. We introduce a simple model of such social polling. We suppose agents vote sequentially, but the order in which agents choose to vote is not necessarily fixed. We also suppose that an agent’s vote is influenced by the votes of their friends who have already voted. Despite its simplicity, this model provides useful insights into a number of areas including social polling, sequential voting, and manipulation. We prove that the number of candidates and the network structure affect the computational complexity of computing which candidate necessarily or possibly can win in such a social poll. For social networks with bounded treewidth and a bounded number of candidates, we provide polynomial algorithms for both problems. In other cases, we prove that computing which candidates necessarily or possibly win are computationally intractable.

AAAI Conference 2013 Conference Paper

Strategic Behavior when Allocating Indivisible Goods Sequentially

• Thomas Kalinowski
• Nina Narodytska
• Toby Walsh
• Lirong Xia

We study a simple sequential allocation mechanism for allocating indivisible goods between agents in which agents take turns to pick items. We focus on agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing the subgame perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.

IJCAI Conference 2013 Conference Paper

Three Generalizations of the FOCUS Constraint

• Nina Narodytska
• Thierry Petit
• Mohamed Siala
• Toby Walsh

The FOCUS constraint expresses the notion that solutions are concentrated. In practice, this constraint suffers from the rigidity of its semantics. To tackle this issue, we propose three generalizations of the FOCUS constraint. We provide for each one a complete filtering algorithm as well as discussing decompositions.

AAAI Conference 2013 Conference Paper

Ties Matter: Complexity of Manipulation when Tie-Breaking with a Random Vote

• Haris Aziz
• Serge Gaspers
• Nicholas Mattei
• Nina Narodytska
• Toby Walsh

We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose candidate uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for a candidate to be the unique winner, or to be among the set of co-winners.

ECAI Conference 2012 Conference Paper

Combining Voting Rules Together

• Nina Narodytska
• Toby Walsh
• Lirong Xia

We propose a simple method for combining together voting rules that performs a run-off between the different winners of each voting rule. We prove that this combinator has several good properties. For instance, even if just one of the base voting rules has a desirable property like Condorcet consistency, the combination inherits this property. On the other hand, some important properties can be lost by the introduction of a run-off, including monotonicity and consistency. In addition, we prove that combining voting rules together in this way can make finding a manipulation more computationally difficult.

AAAI Conference 2012 Conference Paper

Eliminating the Weakest Link: Making Manipulation Intractable?

• Jessica Davies
• Nina Narodytska
• Toby Walsh

Successive elimination of candidates is often a route to making manipulation intractable to compute. We prove that eliminating candidates does not necessarily increase the computational complexity of manipulation. However, for many voting rules used in practice, the computational complexity increases. For example, it is already known that it is NP-hard to compute how a single voter can manipulate the result of single transferable voting(the elimination version of plurality voting). We show here that it is NP-hard to compute how a single voter can manipulate the result of the elimination version of veto voting, of the closely related Coombs’ rule, and of the elimination versions of a general class of scoring rules.

AAMAS Conference 2012 Conference Paper

Lot-based Voting Rules

• Toby Walsh
• Lirong Xia

The Internet Engineering Task Force develops and promotes Internet standards like TCP/IP. The chair of the Task Force is chosen by an election which starts with a set of voters being selected at random from the electorate of volunteers. Selecting decision makers by lottery like this has a long and venerable history, having been used in Athenian democracy over two millennia ago, as well as for over 500 years from the 13th Century to elect the Doge of Venice. In this paper, we consider using such lotteries in multi-agent decision making. We study a family of voting rules called lot-based voting rules. Such rules have two steps: in the first step, $k$ votes are selected by a lottery, then in the second round (the runoff), a voting rule is applied to select the winner based on these $k$ votes. We study some normative properties of such lot-based rules. We also investigate the computational complexity of computing the winner with weighted and unweighted votes, and of computing manipulations. We show that for most lot-based voting rules winner determination and manipulation are computationally hard. Our results suggest that this general technique (using lotteries to selecting some voters randomly) may help to prevent strategic behavior of the voters from a computational point of view.

AAAI Conference 2012 Conference Paper

Symmetry Breaking Constraints: Recent Results

• Toby Walsh

Symmetry is an important problem in many combinatorial problems. One way of dealing with symmetry is to add constraints that eliminate symmetric solutions. We survey recent results in this area, focusing especially on two common and useful cases: symmetry breaking constraints for row and column symmetry, and symmetry breaking constraints for eliminating value symmetry.

AAAI Conference 2011 Conference Paper

A Comparison of Lex Bounds for Multiset Variables in Constraint Programming

• Yat Law
• Jimmy Lee
• May Hiu Woo
• Toby Walsh

Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the length-lex (LL) representation successfully provides information about the length (cardinality) and position in the lexicographic ordering. For multiset variables, where elements can be repeated, we consider richer representations that take into account additional information. We study eight different representations in which we maintain bounds according to one of the eight different orderings: length- (co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety- (co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. These representations integrate together information about the cardinality, variety (number of distinct elements in the multiset), and position in some total ordering. Theoretical and empirical comparisons of expressiveness and compactness of the eight representations suggest that length-variety-(co)lex (LVL/LVC) and variety-length-(co)lex (VLL/VLC) usually give tighter bounds after constraint propagation. We implement the eight representations and evaluate them against the subset bounds representation with cardinality and variety reasoning. Results demonstrate that they offer significantly better pruning and runtime.

AAAI Conference 2011 Conference Paper

Complexity of and Algorithms for Borda Manipulation

• Jessica Davies
• George Katsirelos
• Nina Narodytska
• Toby Walsh

We prove that it is NP-hard for a coalition of two manipulators to compute how to manipulate the Borda voting rule. This resolves one of the last open problems in the computational complexity of manipulating common voting rules. Because of this NP-hardness, we treat computing a manipulation as an approximation problem where we try to minimize the number of manipulators. Based on ideas from bin packing and multiprocessor scheduling, we propose two new approximation methods to compute manipulations of the Borda rule. Experiments show that these methods significantly outperform the previous best known approximation method. We are able to find optimal manipulations in almost all the randomly generated elections tested. Our results suggest that, whilst computing a manipulation of the Borda rule by a coalition is NP-hard, computational complexity may provide only a weak barrier against manipulation in practice.

AAAI Conference 2011 Conference Paper

Conflict-Driven Constraint Answer Set Solving with Lazy Nogood Generation

• Christian Drescher
• Toby Walsh

We present a new approach to enhancing answer set programming (ASP) with constraint programming (CP) techniques based on conflict-driven learning and lazy nogood generation.

AAAI Conference 2011 Conference Paper

Dominating Manipulations in Voting with Partial Information

• Vincent Conitzer
• Toby Walsh
• Lirong Xia

We consider manipulation problems when the manipulator only has partial information about the votes of the nonmanipulators. Such partial information is described by an information set, which is the set of profiles of the nonmanipulators that are indistinguishable to the manipulator. Given such an information set, a dominating manipulation is a non-truthful vote that the manipulator can cast which makes the winner at least as preferable (and sometimes more preferable) as the winner when the manipulator votes truthfully. When the manipulator has full information, computing whether or not there exists a dominating manipulation is in P for many common voting rules (by known results). We show that when the manipulator has no information, there is no dominating manipulation for many common voting rules. When the manipulator’s information is represented by partial orders and only a small portion of the preferences are unknown, computing a dominating manipulation is NP-hard for many common voting rules. Our results thus throw light on whether we can prevent strategic behavior by limiting information about the votes of other voters.

AAAI Conference 2011 Conference Paper

Manipulation of Nanson’s and Baldwin’s Rules

• Nina Narodytska
• Toby Walsh
• Lirong Xia

Nanson’s and Baldwin’s voting rules select a winner by successively eliminating candidates with low Borda scores. We show that these rules have a number of desirable computational properties. In particular, with unweighted votes, it is NP-hard to manipulate either rule with one manipulator, whilst with weighted votes, it is NP-hard to manipulate either rule with a small number of candidates and a coalition of manipulators. As only a couple of other voting rules are known to be NP-hard to manipulate with a single manipulator, Nanson’s and Baldwin’s rules appear to be particularly resistant to manipulation from a theoretical perspective. We also propose a number of approximation methods for manipulating these two rules. Experiments demonstrate that both rules are often difficult to manipulate in practice. These results suggest that elimination style voting rules deserve further study.

AAMAS Conference 2011 Conference Paper

Possible And Necessary Winners In Voting Trees: Majority Graphs Vs. Profiles

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

Given the preferences of several agents over a common set of candidates, voting trees can be used to select a candidate (the winner) by a sequence of pairwise competitions modelled by a binary tree (the agenda). The majority graph compactly represents the preferences of the agents and provides enough information to compute the winner. When some preferences are missing, there are various notions of winners, such as the possible winners (that is, winners in at least one completion) or the necessary winners (that is, winners in all completions). In this generalized scenario, we show that using the majority graph to compute winners is not correct, since it may declare as winners candidates that are not so. Nonetheless, the majority graph can be used to compute efficiently an upper or lower approximation of the correct set of winners.

AAMAS Conference 2011 Conference Paper

Procedural Fairness in Stable Marriage Problems

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. It has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. Given a stable marriage problem, it is possible to find a male-optimal (resp. , female-optimal) stable marriage in polynomial time. However, it is sometimes desirable to find stable marriages without favoring one group at the expenses of the other one. To achieve this goal, we consider a local search approach to find stable marriages with the aim of exploiting the nondeterminism of local search to give a fair procedure. We test our algorithm on classes of stable marriage problems, showing both its efficiency and its sampling capability over the set of all stable marriages, and we compare it to a Markov chain approach.

AAAI Conference 2011 Conference Paper

The Next Best Solution

• Ronen Brafman
• Enrico Pilotto
• Francesca Rossi
• Domenico Salvagnin
• Kristen Venable
• Toby Walsh

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

IJCAI Conference 2011 Conference Paper

Translation-Based Constraint Answer Set Solving

• Christian Drescher
• Toby Walsh

We solve constraint satisfaction problems through translation to answer set programming (ASP). Our reformulations have the property that unit-propagation in the ASP solver achieves well defined local consistency properties like arc, bound and range consistency. Experiments demonstrate the computational value of this approach.

TARK Conference 2011 Conference Paper

Weights in stable marriage problems increase manipulation opportunities

• Maria Silvia Pini
• Francesca Rossi 0001
• Kristen Brent Venable
• Toby Walsh

The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or more generally to any two-sided market. In the classical stable marriage problem, both men and women express a strict preference order over the members of the other sex, in a qualitative way. Here we consider stable marriage problems with weighted preferences: each man (resp. , woman) provides a score for each woman (resp. , man). In this context, we consider the manipulability properties of the procedures that return stable marriages. While we know that all procedures are manipulable by modifying the preference lists or by truncating them, here we consider if manipulation can occur also by just modifying the weights while preserving the ordering and avoiding truncation. It turns out that, by adding weights, we indeed increase the possibility of manipulating and this cannot be avoided by any reasonable restriction on the weights.

JAAMAS Journal 2011 Journal Article

Winner determination in voting trees with incomplete preferences and weighted votes

• Jérôme Lang
• Maria Silvia Pini
• Toby Walsh

Abstract In multiagent settings where agents have different preferences, preference aggregation can be an important issue. Voting is a general method to aggregate preferences. We consider the use of voting tree rules to aggregate agents’ preferences. In a voting tree, decisions are taken by performing a sequence of pairwise comparisons in a binary tree where each comparison is a majority vote among the agents. Incompleteness in the agents’ preferences is common in many real-life settings due to privacy issues or an ongoing elicitation process. We study how to determine the winners when preferences may be incomplete, not only for voting tree rules (where the tree is assumed to be fixed), but also for the Schwartz rule (in which the winners are the candidates winning for at least one voting tree). In addition, we study how to determine the winners when only balanced trees are allowed. In each setting, we address the complexity of computing necessary (respectively, possible) winners, which are those candidates winning for all completions (respectively, at least one completion) of the incomplete profile. We show that many such winner determination problems are computationally intractable when the votes are weighted. However, in some cases, the exact complexity remains unknown. Since it is generally computationally difficult to find the exact set of winners for voting trees and the Schwartz rule, we propose several heuristics that find in polynomial time a superset of the possible winners and a subset of the necessary winners which are based on the completions of the (incomplete) majority graph built from the incomplete profiles.

ECAI Conference 2010 Conference Paper

An Empirical Study of the Manipulability of Single Transferable Voting

• Toby Walsh

Voting is a simple mechanism to combine together the preferences of multiple agents. Agents may try to manipulate the result of voting by mis-reporting their preferences. One barrier that might exist to such manipulation is computational complexity. In particular, it has been shown that it is NP-hard to compute how to manipulate a number of different voting rules. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. In this paper, we study empirically the manipulability of single transferable voting (STV) to determine if computational complexity is really a barrier to manipulation. STV was one of the first voting rules shown to be NP-hard. It also appears one of the harder voting rules to manipulate. We sample a number of distributions of votes including uniform and real world elections. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible.

AIJ Journal 2010 Journal Article

Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

We consider soft constraint problems where some of the preferences may be unspecified. This models, for example, settings where agents are distributed and have privacy issues, or where there is an ongoing preference elicitation process. In this context, we study how to find an optimal solution without having to wait for all the preferences. In particular, we define algorithms, that interleave search and preference elicitation, to find a solution which is necessarily optimal, that is, optimal no matter what the missing data will be, with the aim to ask the user to reveal as few preferences as possible. We define a combined solving and preference elicitation scheme with a large number of different instantiations, each corresponding to a concrete algorithm, which we compare experimentally. We compute both the number of elicited preferences and the user effort, which may be larger, as it contains all the preference values the user has to compute to be able to respond to the elicitation requests. While the number of elicited preferences is important when the concern is to communicate as little information as possible, the user effort measures also the hidden work the user has to do to be able to communicate the elicited preferences. Our experimental results on classical, fuzzy, weighted and temporal incomplete CSPs show that some of our algorithms are very good at finding a necessarily optimal solution while asking the user for only a very small fraction of the missing preferences. The user effort is also very small for the best algorithms.

KR Conference 2010 Conference Paper

Finding the next solution in constraint- and preference-based knowledge representation formalisms

• Ronen Brafman
• Francesca Rossi
• Domenico Salvagnin
• Kristen Brent Venable
• Toby Walsh

In constraint or preference reasoning, a typical task is to compute a solution, or an optimal solution. However, when one has already a solution, it may be important to produce the next solution following the given one in a linearization of the solution ordering where more preferred solutions are ordered first. In this paper, we study the computational complexity of finding the next solution in some common preference-based representation formalisms. We show that this problem is hard in general CSPs, but it can be easy in tree-shaped CSPs and tree-shaped fuzzy CSPs. However, it is difficult in weighted CSPs, even if we restrict the shape of the constraint graph. We also consider CP-nets, showing that the problem is easy in acyclic CP-nets, as well as in constrained acyclic CP-nets where the (soft) constraints are tree-shaped and topologically compatible with the CP-net.

ECAI Conference 2010 Conference Paper

Local search algorithms on the Stable Marriage Problem: Experimental Studies

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi 0001
• Kristen Brent Venable
• Toby Walsh

The stable marriage problem (SM) has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. In the classical formulation, n men and n women express their preferences over the members of the other sex. Solving an SM means finding a stable marriage: a matching of men to women with no blocking pair. A blocking pair consists of a man and a woman who are not married to each other but both prefer each other to their partners. It is possible to find a male-optimal (resp. , female-optimal) stable marriage in polynomial time. However, it is sometimes desirable to find stable marriages without favoring a group at the expenses of the other one. In this paper we present a local search approach to find stable marriages. Our experiments show that the number of steps grows as little as O(nlog(n)). We also show empirically that the proposed algorithm samples very well the set of all stable marriages of a given SM, thus providing a fair and efficient approach to generate stable marriages.

AAMAS Conference 2010 Conference Paper

Male optimality and uniqueness in stable marriage problems with partial orders

• Mirco Gelain
• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

In this paper, we study the concepts of male optimality anduniqueness of stable marriages for partially ordered preferences. We give an algorithm to find a stable marriage that ismale optimal, and a sufficient condition on the preferences, which guarantees the uniqueness of stable marriages.

JAAMAS Journal 2010 Journal Article

Manipulation complexity and gender neutrality in stable marriage procedures

• Maria Silvia Pini
• Francesca Rossi
• Toby Walsh

Abstract The stable marriage problem is a well-known problem of matching men to women so that no man and woman who are not married to each other both prefer each other. Such a problem has a wide variety of practical applications, ranging from matching resident doctors, to hospitals to matching students to schools. A well-known algorithm to solve this problem is the Gale–Shapley algorithm, which runs in quadratic time in the number of men/women. It has been proven that stable marriage procedures can always be manipulated. Whilst the Gale–Shapley algorithm is computationally easy to manipulate, we prove that there exist stable marriage procedures which are NP-hard to manipulate. We also consider the relationship between voting theory and stable marriage procedures, showing that voting rules which are NP-hard to manipulate can be used to define stable marriage procedures which are themselves NP-hard to manipulate. Finally, we consider the issue that stable marriage procedures like Gale–Shapley favour one gender over the other, and we show how to use voting rules to make any stable marriage procedure gender neutral.

AAAI Conference 2010 Conference Paper

Propagating Conjunctions of AllDifferent Constraints

• Christian Bessiere
• George Katsirelos
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We study propagation algorithms for the conjunction of two ALLDIFFERENT constraints. Solutions of an ALLDIFFERENT constraint can be seen as perfect matchings on the variable/value bipartite graph. Therefore, we investigate the problem of finding simultaneous bipartite matchings. We present an extension of the famous Hall theorem which characterizes when simultaneous bipartite matchings exists. Unfortunately, finding such matchings is NP-hard in general. However, we prove a surprising result that finding a simultaneous matching on a convex bipartite graph takes just polynomial time. Based on this theoretical result, we provide the first polynomial time bound consistency algorithm for the conjunction of two ALLDIFFERENT constraints. We identify a pathological problem on which this propagator is exponentially faster compared to existing propagators. Our experiments show that this new propagator can offer significant benefits over existing methods.

ECAI Conference 2010 Conference Paper

Symmetries of Symmetry Breaking Constraints

• George Katsirelos
• Toby Walsh

Symmetry is an important feature of many constraint programs. We show that any problem symmetry acting on a set of symmetry breaking constraints can be used to break symmetry. Different symmetries pick out different solutions in each symmetry class. This simple but powerful idea can be used in a number of different ways. We describe one application within model restarts, a search technique designed to reduce the conflict between symmetry breaking and the branching heuristic. In model restarts, we restart search periodically with a random symmetry of the symmetry breaking constraints. Experimental results show that this symmetry breaking technique is effective in practice on some standard benchmark problems.

AAAI Conference 2010 Conference Paper

Symmetry in Solutions

• Marijn Heule
• Toby Walsh

We define the concept of an internal symmetry. This is a symmety within a solution of a constraint satisfaction problem. We compare this to solution symmetry, which is a mapping between different solutions of the same problem. We argue that we may be able to exploit both types of symmetry when finding solutions. We illustrate the potential of exploiting internal symmetries on two benchmark domains: Van der Waerden numbers and graceful graphs. By identifying internal symmetries we are able to extend the state of the art in both cases.

IJCAI Conference 2009 Conference Paper

• Christian Bessiere
• George Katsirelos
• Nina Narodytska
• Claude-Guy Quimper
• Toby Walsh

We show that some common and important global constraints like ALL-DIFFERENT and GCC can be decomposed into simple arithmetic constraints on which we achieve bound or range consistency, and in some cases even greater pruning. These decompositions can be easily added to new solvers. They also provide other constraints with access to the state of the propagator by sharing of variables. Such sharing can be used to improve propagation between constraints. We report experiments with our decomposition in a pseudo-Boolean solver.

IJCAI Conference 2009 Conference Paper

• Toby Walsh

Voting is a simple mechanism to aggregate the preferences of agents. Many voting rules have been shown to be NP-hard to manipulate. However, a number of recent theoretical results suggest that this complexity may only be in the worst-case since manipulation is often easy in practice. In this paper, we show that empirical studies are useful in improving our understanding of this issue. We demonstrate that there is a smooth transition in the probability that a coalition can elect a desired candidate using the veto rule as the size of the manipulating coalition increases. We show that a rescaled probability curve displays a simple and universal form independent of the size of the problem. We argue that manipulation of the veto rule is asymptotically easy for many independent and identically distributed votes even when the coalition of manipulators is critical in size. Based on this argument, we identify a situation in which manipulation is computationally hard. This is when votes are highly correlated and the election is “hung”. We show, however, that even a single uncorrelated voter is enough to make manipulation easy again.

IJCAI Conference 2009 Conference Paper

• Christian Bessiere
• George Katsirelos
• Nina Narodytska
• Toby Walsh

We show that tools from circuit complexity can be used to study decompositions of global constraints. In particular, we study decompositions of global constraints into conjunctive normal form with the property that unit propagation on the decomposition enforces the same level of consistency as a specialized propagation algorithm. We prove that a constraint propagator has a a polynomial size decomposition if and only if it can be computed by a polynomial size monotone Boolean circuit. Lower bounds on the size of monotone Boolean circuits thus translate to lower bounds on the size of decompositions of global constraints. For instance, we prove that there is no polynomial sized decomposition of the domain consistency propagator for the ALLDIFFERENT constraint.

AIJ Journal 2009 Journal Article

Filtering algorithms for the multiset ordering constraint

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Constraint programming (CP) has been used with great success to tackle a wide variety of constraint satisfaction problems which are computationally intractable in general. Global constraints are one of the important factors behind the success of CP. In this paper, we study a new global constraint, the multiset ordering constraint, which is shown to be useful in symmetry breaking and searching for leximin optimal solutions in CP. We propose efficient and effective filtering algorithms for propagating this global constraint. We show that the algorithms maintain generalised arc-consistency and we discuss possible extensions. We also consider alternative propagation methods based on existing constraints in CP toolkits. Our experimental results on a number of benchmark problems demonstrate that propagating the multiset ordering constraint via a dedicated algorithm can be very beneficial.

AAMAS Conference 2009 Conference Paper

Manipulation and Gender Neutrality in Stable Marriage Procedures

• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

AIJ Journal 2009 Journal Article

Range and Roots: Two common patterns for specifying and propagating counting and occurrence constraints

• Christian Bessiere
• Emmanuel Hebrard
• Brahim Hnich
• Zeynep Kiziltan
• Toby Walsh

We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. We design specialised propagation algorithms for these two patterns. Counting and occurrence constraints specified using these patterns thus directly inherit a propagation algorithm. To illustrate the capabilities of the Range and Roots constraints, we specify a number of global constraints taken from the literature. Preliminary experiments demonstrate that propagating counting and occurrence constraints using these two patterns leads to a small loss in performance when compared to specialised global constraints and is competitive with alternative decompositions using elementary constraints.

SAT Conference 2009 Conference Paper

Restart Strategy Selection Using Machine Learning Techniques

• Shai Haim
• Toby Walsh

Abstract Restart strategies are an important factor in the performance of conflict-driven Davis Putnam style SAT solvers. Selecting a good restart strategy for a problem instance can enhance the performance of a solver. Inspired by recent success applying machine learning techniques to predict the runtime of SAT solvers, we present a method which uses machine learning to boost solver performance through a smart selection of the restart strategy. Based on easy to compute features, we train both a satisfiability classifier and runtime models. We use these models to choose between restart strategies. We present experimental results comparing this technique with the most commonly used restart strategies. Our results demonstrate that machine learning is effective in improving solver performance.

AAAI Conference 2008 Conference Paper

Breaking Value Symmetry

• Toby Walsh

Symmetry is an important factor in solving many constraint satisfaction problems. One common type of symmetry is when we have symmetric values. In a recent series of papers, we have studied methods to break value symmetries (Walsh 2006a; 2007). Our results identify computational limits on eliminating value symmetry. For instance, we prove that pruning all symmetric values is NP-hard in general. Nevertheless, experiments show that much value symmetry can be broken in practice. These results may be useful to researchers in planning, scheduling and other areas as value symmetry occurs in many different domains.

AAMAS Conference 2008 Conference Paper

Complexity of Terminating Preference Elicitation

• Toby Walsh

Complexity theory is a useful tool to study computational issues surrounding the elicitation of preferences, as well as the strategic manipulation of elections aggregating together preferences of multiple agents. We study here the complexity of determining when we can terminate eliciting preferences, and prove that the complexity depends on the elicitation strategy. We show, for instance, that it may be better from a computational perspective to elicit all preferences from one agent at a time than to elicit individual preferences from multiple agents. We also study the connection between the strategic manipulation of an election and preference elicitation. We show that what we can manipulate affects the computational complexity of manipulation. In particular, we prove that there are voting rules which are easy to manipulate if we can change all of an agent’s vote, but computationally intractable if we can change only some of their preferences. This suggests that, as with preference elicitation, a fine-grained view of manipulation may be informative. Finally, we study the connection between predicting the winner of an election and preference elicitation. Based on this connection, we identify a voting rule where it is computationally difficult to decide the probability of a candidate winning given a probability distribution over the votes.

KR Conference 2008 Conference Paper

Dealing with Incomplete Agents' Preferences and an Uncertain Agenda in Group Decision Making via Sequential Majority Voting

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

AIJ Journal 2008 Journal Article

Domain filtering consistencies for non-binary constraints

• Christian Bessiere
• Kostas Stergiou
• Toby Walsh

In non-binary constraint satisfaction problems, the study of local consistencies that only prune values from domains has so far been largely limited to generalized arc consistency or weaker local consistency properties. This is in contrast with binary constraints where numerous such domain filtering consistencies have been proposed. In this paper we present a detailed theoretical, algorithmic and empirical study of domain filtering consistencies for non-binary problems. We study three domain filtering consistencies that are inspired by corresponding variable based domain filtering consistencies for binary problems. These consistencies are stronger than generalized arc consistency, but weaker than pairwise consistency, which is a strong consistency that removes tuples from constraint relations. Among other theoretical results, and contrary to expectations, we prove that these new consistencies do not reduce to the variable based definitions of their counterparts on binary constraints. We propose a number of algorithms to achieve the three consistencies. One of these algorithms has a time complexity comparable to that for generalized arc consistency despite performing more pruning. Experiments demonstrate that our new consistencies are promising as they can be more efficient than generalized arc consistency on certain non-binary problems.

SAT Conference 2008 Conference Paper

Online Estimation of SAT Solving Runtime

• Shai Haim
• Toby Walsh

Abstract We present an online method for estimating the cost of solving SAT problems. Modern SAT solvers present several challenges to estimate search cost including non-chronological backtracking, learning and restarts. Our method uses a linear model trained on data gathered at the start of search. We show the effectiveness of this method using random and structured problems. We demonstrate that predictions made in early restarts can be used to improve later predictions. We also show that we can use such cost estimations to select a solver from a portfolio.

ECAI Conference 2008 Conference Paper

SLIDE: A Useful Special Case of the CARDPATH Constraint

• Christian Bessière
• Emmanuel Hebrard
• Brahim Hnich
• Zeynep Kiziltan
• Toby Walsh

We study the CARDPATH constraint. This ensures a given constraint holds a number of times down a sequence of variables. We show that SLIDE, a special case of CARDPATH where the slid constraint must hold always, can be used to encode a wide range of sliding sequence constraints including CARDPATH itself. We consider how to propagate SLIDE and provide a complete propagator for CARDPATH. Since propagation is NP-hard in general, we identify special cases where propagation takes polynomial time. Our experiments demonstrate that using SLIDE to encode global constraints can be as efficient and effective as specialised propagators.

IJCAI Conference 2007 Conference Paper

• Maria Silvia Pini
• Francesca Rossi
• Kristen Brent Venable
• Toby Walsh

We consider how to combine the preferences of multiple agents despite the presence of incompleteness and incomparability in their preference orderings. An agent's preference ordering may be incomplete because, for example, there is an ongoing preference elicitation process. It may also contain incomparability as this is useful, for example, in multi-criteria scenarios. We focus on the problem of computing the possible and necessary winners, that is, those outcomes which can be or always are the most preferred for the agents. Possible and necessary winners are useful in many scenarios including preference elicitation. First we show that computing the sets of possible and necessary winners is in general a difficult problem as is providing a good approximation of such sets. Then we identify general properties of the preference aggregation function which are sufficient for such sets to be computed in polynomial time. Finally, we show how possible and necessary winners can be used to focus preference elicitation.

IJCAI Conference 2007 Conference Paper

• Emmanuel Hebrard
• Barry O'Sullivan
• Toby Walsh

Users can often naturally express their preferences in terms of ideal or non-ideal solutions. We show how to reason about logical combinations of distance constraints on ideals and non-ideals using a novel global constraint. We evaluate our approach on both randomly generated and real-world configuration problem instances.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang
• Maria Silvia Pini
• Francesca Rossi
• K. Brent Venable
• Toby Walsh

Preferences can be aggregated using voting rules. We consider here the family of rules which perform a sequence of pairwise majority comparisons between two candidates. The winner thus depends on the chosen sequence of comparisons, which can be represented by a binary tree. We address the difficulty of computing candidates that win for some trees, and then introduce and study the notion of fair winner, i. e. candidates who win in a balanced tree. We then consider the situation where we lack complete informations about preferences, and determine the computational complexity of computing winners in this case.

IJCAI Conference 2007 Conference Paper

• Nina Narodytska
• Toby Walsh

To facilitate interactive design, the solutions to configuration problems can be compiled into a decision diagram. We develop three heuristics for reducing the time and space required to do this. These heuristics are based on the distinctive clustered and hierarchical structure of the constraint graphs of configuration problems. The first heuristic attempts to limit the growth in the size of the decision diagram by providing an order in which constraints are added to the decision diagram. The second heuristic provides an initial order for the variables within the decision diagram. Finally, the third heuristic groups variables together so that they can be reordered by a dynamic variable reordering procedure used during the construction of the decision diagram. These heuristics provide one to two orders magnitude improvement in the time to compile a wide range of configuration.

IS Journal 2007 Journal Article

Configuration

• Carsten Sinz
• Albert Haag
• Nina Narodytska
• Toby Walsh
• Esther Gelle
• Mihaela Sabin
• Ulrich Junker
• Barry O'Sullivan

Over the years, a whole sector of AI dealing with configuration problems has emerged, and since 1996, an annual configuration workshop has been held in affiliation with a major AI conference. This installment of Trends & Controversies presents essays from the configuration workshop held in August 2006 as part of ECAI in Riva del Garda, Italy.

ECAI Conference 2006 Conference Paper

Computing Possible and Necessary Winners from Incomplete Partially-Ordered Preferences

• Maria Silvia Pini
• Francesca Rossi 0001
• Kristen Brent Venable
• Toby Walsh

ECAI Conference 2006 Conference Paper

Inverse Consistencies for Non-Binary Constraints

• Kostas Stergiou 0001
• Toby Walsh

We present a detailed study of two inverse consistencies for non-binary constraints: relational path inverse consistency (rel PIC) and pairwise inverse consistency (PWIC). These are stronger than generalized arc consistency (GAC), even though they also only prune domain values. We propose algorithms to achieve rel PIC and PWIC, that have a time complexity better than the previous generic algorithm for inverse consistencies. One of our algorithms for PWIC has a complexity comparable to that for GAC despite doing more pruning. Our experiments demonstrate that inverse consistencies can be more efficient than GAC on a range of non-binary problems.

AIJ Journal 2006 Journal Article

Propagation algorithms for lexicographic ordering constraints

• Alan M. Frisch
• Brahim Hnich
• Zeynep Kiziltan
• Ian Miguel
• Toby Walsh

Finite-domain constraint programming has been used with great success to tackle a wide variety of combinatorial problems in industry and academia. To apply finite-domain constraint programming to a problem, it is modelled by a set of constraints on a set of decision variables. A common modelling pattern is the use of matrices of decision variables. The rows and/or columns of these matrices are often symmetric, leading to redundancy in a systematic search for solutions. An effective method of breaking this symmetry is to constrain the assignments of the affected rows and columns to be ordered lexicographically. This paper develops an incremental propagation algorithm, GACLexLeq, that establishes generalised arc consistency on this constraint in O ( n ) operations, where n is the length of the vectors. Furthermore, this paper shows that decomposing GACLexLeq into primitive constraints available in current finite-domain constraint toolkits reduces the strength or increases the cost of constraint propagation. Also presented are extensions and modifications to the algorithm to handle strict lexicographic ordering, detection of entailment, and vectors of unequal length. Experimental results on a number of domains demonstrate the value of GACLexLeq.

AAMAS Conference 2006 Conference Paper

Strategic voting when aggregating partially ordered preferences

• Francesca Rossi
• Maria Silvia Pini
• Kristen Brent Venable
• Toby Walsh

ECAI Conference 2006 Conference Paper

Symmetry Breaking Using Value Precedence

• Toby Walsh

We present a comprehensive study of the use of value precedence constraints to break value symmetry. We first give a simple encoding of value precedence into ternary constraints that is both efficient and effective at breaking symmetry. We then extend value precedence to deal with a number of generalizations like wreath value and partial interchangeability. We also show that value precedence is closely related to lexicographical ordering. Finally, we consider the interaction between value precedence and symmetry breaking constraints for variable symmetries.

TARK Conference 2005 Conference Paper

Aggregating partially ordered preferences: impossibility and possibility results

• Maria Silvia Pini
• Francesca Rossi 0001
• Kristen Brent Venable
• Toby Walsh

ECAI Conference 2004 Conference Paper

Robust Solutions for Constraint Satisfaction and Optimization

• Emmanuel Hebrard
• Brahim Hnich
• Toby Walsh

SAT Conference 2004 Conference Paper

Solving Non-clausal Formulas with DPLL search

• Christian Thiffault
• Fahiem Bacchus
• Toby Walsh

SAT Conference 2003 Conference Paper

Local Consistencies in SAT

• Christian Bessière
• Emmanuel Hebrard
• Toby Walsh

Abstract We introduce some new mappings of constraint satisfaction problems into propositional satisfiability. These encodings generalize most of the existing encodings. Unit propagation on those encodings is the same as establishing relational k -arc consistency on the original problem. They can also be used to establish (i, j)-consistency on binary constraints. Experiments show that these encodings are an effective method for enforcing such consistencies, that can lead to a reduction in runtimes at the phase transition in most cases. Compared to the more traditional (direct) encoding, the search tree can be greatly pruned.

IJCAI Conference 2003 Conference Paper

Multiset Ordering Constraints

• Alan Frisch
• Ian Miguel
• Zeynep Kiziltan
• Brahim Hnich
• Toby Walsh

We identify a new and important global (or nonbinary) constraint which ensures that the values taken by two vectors of variables, when viewed as multisets, are ordered. This constraint is useful for a number of different applications including breaking symmetry and fuzzy constraint satisfaction. We propose and implement a linear time algorithm for enforcing generalised arc-consistency on such a multiset ordering constraint. Experimental results show considerable promise.

IJCAI Conference 2003 Conference Paper

Scenario-based Stochastic Constraint Programming

• Suresh Manandhar
• Armagan Tarim
• Toby Walsh

To model combinatorial decision problems involving uncertainty and probability, we extend the stochastic constraint programming framework proposed in iWalsh, 2002] along a number of important dimensions (e. g. to multiple chance constraints and to a range of new objectives). We also provide a new (but equivalent) semantics based on scenarios. Using this semantics, we can compile stochastic constraint programs down into conventional (nonstochastic) constraint programs. This allows us to exploit the full power of existing constraint solvers. We have implemented this framework for decision making under uncertainty in stochastic OPL, a language which is based on the OPL constraint modelling language [Hentenryck et a/. , 1999]. To illustrate the potential of this framework, we model a wide range of problems in areas as diverse as finance, agriculture and production.

AIJ Journal 2002 Journal Article

Binary vs. non-binary constraints☆☆This paper includes results that first appeared in [1,4,23]. This research has been supported in part by the Canadian Government through their NSERC and IRIS programs, and by the EPSRC Advanced Research Fellowship program.

• Fahiem Bacchus
• Xinguang Chen
• Peter van Beek
• Toby Walsh

There are two well known transformations from non-binary constraints to binary constraints applicable to constraint satisfaction problems (CSPs) with finite domains: the dual transformation and the hidden (variable) transformation. We perform a detailed formal comparison of these two transformations. Our comparison focuses on two backtracking algorithms that maintain a local consistency property at each node in their search tree: the forward checking and maintaining arc consistency algorithms. We first compare local consistency techniques such as arc consistency in terms of their inferential power when they are applied to the original (non-binary) formulation and to each of its binary transformations. For example, we prove that enforcing arc consistency on the original formulation is equivalent to enforcing it on the hidden transformation. We then extend these results to the two backtracking algorithms. We are able to give either a theoretical bound on how much one formulation is better than another, or examples that show such a bound does not exist. For example, we prove that the performance of the forward checking algorithm applied to the hidden transformation of a problem is within a polynomial bound of the performance of the same algorithm applied to the dual transformation of the problem. Our results can be used to help decide if applying one of these transformations to all (or part) of a constraint satisfaction model would be beneficial.

ECAI Conference 2002 Conference Paper

Stochastic Constraint Programming

• Toby Walsh

AAAI Conference 2002 Conference Paper

The Interface between P and NP: COL, XOR, NAE, 1-in-k, and Horn SAT

• Toby Walsh

We study in detail the interface between P and NP by means of five new problem classes. Like the well known 2+p-SAT problem, these new problems smoothly interpolate between P and NP by mixing together a polynomial and a NP-complete problem. In many cases, the polynomial subproblem can dominate the problem’s satisfiability and the search complexity. However, this is not always the case, and understanding why remains a very interesting open question. We identify phase transition behavior in each of these problem classes. Surprisingly we observe transitions with both smooth and sharp regions. Finally we show how these problem classes can help to understand algorithm behavior by considering search trajectories through the phase space.

LPAR Conference 2001 Conference Paper

Permutation Problems and Channelling Constraints

• Toby Walsh

Abstract When writing a constraint program, we have to decide what to make the decision variable, and how to represent the constraints on these variables. In many cases, there is considerable choice for the decision variables. For example, with permutation problems, we can choose between a primal and a dual representation. In the dual representation, dual variables stand for the primal values, whilst dual values stand for the primal variables. By means of channelling constraints, a combined model can have both primal and dual variables. In this paper, we perform an extensive theoretical and empirical study of these different models. Our results will aid constraint programmers to choose a model for a permutation problem. They also illustrate a general methodology for comparing different constraint models.

ICML Conference 2000 Conference Paper

Automatic Identification of Mathematical Concepts

• Simon Colton
• Alan Bundy
• Toby Walsh

AIJ Journal 2000 Journal Article

Decomposable constraints☆☆Supported by EPSRC award GR/L/24014. The authors wish to thank other members of the APES research group.

• Ian Gent
• Kostas Stergiou
• Toby Walsh

Many constraint satisfaction problems can be naturally and efficiently modelled using non-binary constraints like the “all-different” and “global cardinality” constraints. Certain classes of these non-binary constraints are “network decomposable” as they can be represented by binary constraints on the same set of variables. We compare theoretically the levels of consistency which are achieved on non-binary constraints to those achieved on their binary decomposition. We present many results about the level of consistency achieved by the forward checking algorithm and its various generalizations to non-binary constraints. We also compare the level of consistency achieved by arc-consistency and its generalization to non-binary constraints, and identify special cases of non-binary decomposable constraints where weaker or stronger conditions, than in the general case, hold. We also analyze the cost, in consistency checks, required to achieve certain levels of consistency, and we present experimental results on benchmark domains that demonstrate the practical usefulness of our theoretical analysis.

IJCAI Conference 1999 Conference Paper

Automatic Concept Formation in Pure Mathematics

• Simon Colton
• Alan Bundy
• Toby Walsh

The HR program forms concepts and makes conjectures in domains of pure mathematics and uses theorem prover OTTER and model generator MACE to prove or disprove the conjectures. HR measures properties of concepts and assesses the theorems and proofs involving them to estimate the interestingness of each concept and employ a best first search. This approach has led HR to the discovery of interesting new mathematics and enables it to build theories from just the axioms of finite algebras.

AAAI Conference 1999 Conference Paper

Beyond NP: The QSAT Phase Transition

• Ian P. Gent
• Toby Walsh
• University of Strathclyde

Weshowthat phase transition behavior similar to that observed in NP-completeproblems like random3-SAT occurs further up the polynomialhierarchy in problems like random 2-QSAT. The differences between QSAT and SAT in phase transition behavior that Cadoli et al report are largely dueto the presenceof trivially unsatisfiable problems. Oncethey are removed, wesee behavior more familiar from SAT and other NP-complete domains. There are, however, somedifferences. Problemswith short clauses showa large gap betweenworst case behavior and median, and the easy-hard-easy pattern is restricted to higherpercentiles of search cost. Wecomputethe "constralnedness" of k-QSAT problems for anyk, anduse this to predict the location of phase transitions. Weconjecture that these predictions are less accurate than in NP-completeproblems because of the super-exponential size of the state space, and of the weaknessof first moment methodsin complexity classes aboveNP. Finally, wepredict that similar phase transition behavior will occur in other PSPAeEcomplete problemslike planning and gameplaying.

AAAI Conference 1999 Conference Paper

Encodings of Non-Binary Constraint Satisfaction Problems

• Kostas Stergiou
• Toby Walsh
• University of Strathclyde

We perform a detailed theoretical and empirical comparison of the dual and hidden variable encodings of non-binary constraint satisfaction problems. We identify a simple relationship between the two encodings by showing how we can translate between the two by composing or decomposing relations. This translation suggeststhat we will tend to achieve more pruning in the dual than in the hidden variable encoding. We prove that achieving arc-consistency on the dual encoding is strictly stronger than achieving arc-consistency on the hidden variable, and this itself is equivalent to achieving generalized arc-consistency on the original (non-binary) problem. We also prove that, as a consequence of the unusual topology of the constraint graph in the hidden variable encoding, inverse consistencies like neighborhood inverse consistency and path inverse consistency collapse down onto arc-consistency. Finally, we propose the “double encoding”, which combines together both the dual and the hidden variable encodings.

AAAI Conference 1999 Conference Paper

Morphing: Combining Structure and Randomness

• Ian P. Gent
• University of Strathclyde; Holger H. Hoos
• University of British Columbia; Patrick Prosser
• Toby Walsh
• University of Strathclyde

We introduce a mechanism called “morphing” for introducing structure or randomness into a wide variety of problems. We illustrate the usefulness of morphing by performing several different experimental studies. These studies identify the impact of a “small-world” topology on the cost of coloring graphs, of asymmetry on the cost of finding the optimal TSP tour, and of the dimensionality of space on the cost of finding the optimal TSP tour. We predict that morphing will find many other uses.

AIJ Journal 1999 Journal Article

Paul R. Cohen's Empirical Methods for Artificial Intelligence

• Ian P. Gent
• Toby Walsh

IJCAI Conference 1999 Conference Paper

Search in a Small World

• Toby Walsh

In a graph with a "small world" topology, nodes are highly clustered yet the path length between them is small. Such a topology can make search problems very difficult since local decisions quickly propagate globally. We show that graphs associated with many different search problems have a small world topology, and that the cost of solving such search problems can have a heavy-tailed distribution. The strategy of randomization and restarts appears to eliminate these heavy tails. A novel restart schedule in which the cutoff bound is increased geometrically appears particularly effective.

IJCAI Conference 1999 Conference Paper

The Difference All-Difference Makes

• Kostas Stergiou
• Toby Walsh

We perform a comprehensive theoretical and experimental analysis of the use of all-different constraints. We prove that generalized arc-consistency on such constraints lies between neighborhood inverse consistency and, under a simple restriction, path inverse consistency on the binary representation of the problem. By generalizing the arguments of Kondrak and van Beek, we prove that a search algorithm that maintains generalized arc-consistency on all-different constraints dominates a search algorithm that maintains arc-consistency on the binary representation. Our experiments show the practical value of achieving these high levels of consistency. For example, we can solve almost all benchmark quasigroup completion problems up to order 25 with just a few branches of search. These results demonstrate the benefits of using non-binary constraints like all-different to identify structure in problems.

ECAI Conference 1998 Conference Paper

Interleaved and Discrepancy Based Search

• Pedro Meseguer
• Toby Walsh

AAAI Conference 1998 Conference Paper

The Constrainedness Knife-Edge

• Toby Walsh

A general rule of thumbis to tackle the hardest part of a search problem first. Manyheuristics therefore try to branch on the most constrained variable. To test their effectiveness at this, we measure the constrainedness of a problem during search. Werun experiments in several different domains, using both random and non-random problems. In each case, we observe a constrainedness "knlfe-edge" in whichcritically constrained problems tend to remain critically constrained. Weshowthat this knife-edge is predicted by a theoretical lower-boundcalculation. Wealso observe a very simple scaling with problem size for various properties measuredduring search including the ratio of clauses to variables, and the averageclause size. Finally, weuse this picture of search to propose somebranching heuristics for propositionalsatisfiability. The Constrainedness Knife-Edge Toby Walsh APES Group Department of Computer Science University of Strathclyde Glasgow, Scotland tw©cs, strath, ac. uk deepens, over-constrained problemstend to become more constrained, but critically constrained problems from the region inbetween tend to remain critically constrained. We also observe a simple scaling with problem size for various properties measured during search including the ratio of clauses to variables. The existence of a constrainedness knife-edge helps to explain the hardness of problems from the phase transition. It also suggests some new branching heuristics for satisfiability. Similar microscopic studies that look closely inside search may be useful in other domains.

IJCAI Conference 1997 Conference Paper

Depth-bounded Discrepancy Search

• Toby Walsh

Many search trees are impractically large to explore exhaustively. Recently, techniques like limited discrepancy search have been proposed for improving the chance of finding a goal in a limited amount of search. Depth-bounded discrepancy search offers such a hope. The motivation behind depth-bounded discrepancy search is that branching heuristics are more likely to be wrong at the top of the tree than at the bottom. We therefore combine one of the best features of limited discrepancy search - the ability to undo early mistakes - with the completeness of iterative deepening search. We show theoretically and experimentally that this novel combination outperforms existing techniques.

IJCAI Conference 1997 Conference Paper

From Approximate to Optimal Solutions: Constructing Pruning and Propagation Rules

• Ian P. Gent
• Toby Walsh

At the heart of many optimization procedures are powerful pruning and propagation rules. This paper presents a case study in the construction of such rules. We develop a new algorithm, Complete Decreasing Best Fit, that finds the optimal packing of objects into bins. The algorithm use a branching rule based on the well known Decreasing Best Fit approximation algorithm. In addition, it includes a powerful pruning rule derived from a bound on the solution to the remaining subproblem. The bound is constructed by using modular arithmetic to decompose the numerical constraints. We show that the pruning rule adds essentially a constant factor overhead to runtime, whilst reducing search significantly. On the hardest problems, runtime can be reduced by an order of magnitude. Finally we demonstrate how propagation rules can be built by adding lookahead to pruning rules. This general approach - optimization procedures built from branching rules based on good approximation algorithms, and pruning and propagation rules derived from bounds on the remaining subproblem - may be effective on other NP-complete problems.

ECAI Conference 1996 Conference Paper

Phase Transitions and Annealed Theories: Number Partitioning as a Case Study

• Ian P. Gent
• Toby Walsh

AIJ Journal 1996 Journal Article

The satisfiability constraint gap

• Ian P. Gent
• Toby Walsh

We describe an experimental investigation of the satisfiability phase transition for several different classes of randomly generated problems. We show that the “conventional” picture of easy-hard-easy problem difficulty is inadequate. In particular, there is a region of very variable problem difficulty where problems are typically underconstrained and satisfiable. Within this region, problems can be orders of magnitude harder than problems in the middle of the satisfiability phase transition. These extraordinarily hard problems appear to be associated with a “constraint gap”. That is, a region where search is a maximum as the amount of constraint propagation is a minimum. We show that the position and shape of this constraint gap change little with problem size. Unlike hard problems in the middle of the satisfiability phase transition, hard problems in the variable region are not critically constrained between satisfiability and unsatisfiability. Indeed, hard problems in the variable region often contain a small and unique minimal unsatisfiable subset or reduce at an early stage in search to a hard unsatisfiable subproblem with a small and unique minimal unsatisfiable subset. The difficulty in solving such problems is thus in identifying the minimal unsatisfiable subset from the many irrelevant clauses. The existence of a constraint gap greatly hinders our ability to find such minimal unsatisfiable subsets. However, it remains open whether these problems remain hard for more intelligent backtracking procedures. We conjecture that these results will generalize both to other SAT problem classes, and to the phase transitions of other NP-hard problems.

AIJ Journal 1996 Journal Article

The TSP phase transition

• Ian P. Gent
• Toby Walsh

The traveling salesman problem is one of the most famous combinatorial problems. We identify a natural parameter for the two-dimensional Euclidean traveling salesman problem. We show that for random problems there is a rapid transition between soluble and insoluble instances of the decision problem at a critical value of this parameter. Hard instances of the traveling salesman problem are associated with this transition. Similar results are seen both with randomly generated problems and benchmark problems using geographical data. Surprisingly, finite-size scaling methods developed in statistical mechanics describe the behaviour around the critical value in random problems. Such phase transition phenomena appear to be ubiquitous. Indeed, we have yet to find an NP-complete problem which lacks a similar phase transition.

ECAI Conference 1994 Conference Paper

Coloured Rippling: An Extension of a Theorem Proving Heuristic

• Tetsuya Yoshida
• Alan Bundy
• Ian Green
• Toby Walsh
• David A. Basin

AIJ Journal 1994 Journal Article

Easy problems are sometimes hard

• Ian P. Gent
• Toby Walsh

We present a detailed experimental investigation of the easy-hard-easy phase transition for randomly generated instances of satisfiability problems. Problems in the hard part of the phase transition have been extensively used for benchmarking satisfiability algorithms. This study demonstrates that problem classes and regions of the phase transition previously thought to be easy can sometimes be orders of magnitude more difficult than the worst problems in problem classes and regions of the phase transition considered hard. These difficult problems are either hard unsatisfiable problems or are satisfiable problems which give a hard unsatisfiable subproblem following a wrong split. Whilst these hard unsatisfiable problems may have short proofs, these appear to be difficult to find, and other proofs are long and hard.

ECAI Conference 1994 Conference Paper

The SAT Phase Transition

• Ian P. Gent
• Toby Walsh

IJCAI Conference 1993 Conference Paper

Difference Unification

• David A. Basin
• Toby Walsh

AIJ Journal 1992 Journal Article

A theory of abstraction

• Fausto Giunchiglia
• Toby Walsh

Informally, abstraction can be described as the process of mapping a representation of a problem onto a new representation. The aim of this paper is to propose the beginnings of a theory of reasoning with abstraction which captures and generalizes most previous work in the area. The theory allows us to study the properties of abstraction mappings and provides the foundations for the mechanization of abstraction inside an abstract proof checker.

ECAI Conference 1992 Conference Paper

Tree Subsumption: Reasoning with Outlines

• Fausto Giunchiglia
• Toby Walsh

IJCAI Conference 1989 Conference Paper

Abstract Theorem Proving

• Fausto Giunchiglia
• Toby Walsh