Search

When designing a public transportation network in a country, one may want to minimise the sum of travel duration of all inhabitants. This corresponds to a purely utilitarian view and does not involve any fairness consideration, as the resulting network will typically benefit the capital city and/or large central cities while leaving some peripheral cities behind. On the other hand, a more egalitarian view will allow some people to travel between peripheral cities without having to go through a central city. We define a model, propose algorithms for computing solution networks, and report on experiments based on real data., Comment: 32 pages, 18 figures

We show how hidden interesting subelections can be discovered in ordinal elections. An interesting subelection consists of a reasonably large set of voters and a reasonably large set of candidates such that the former have a consistent opinion about the latter. Consistency may take various forms but we focus on three: Identity (all selected voters rank all selected candidates the same way), antagonism (half of the selected voters rank candidates in some order and the other half in the reverse order), and clones (all selected voters rank all selected candidates contiguously in the original election). We first study the computation of such hidden subelections. Second, we analyze synthetic and real-life data, and find that identifying hidden consistent subelections allows us to uncover some relevant concepts., Comment: Accepted for publication at AAMAS 2024

Reasoning about unpredicted change consists in explaining observations by events; we propose here an approach for explaining time-stamped observations by surprises, which are simple events consisting in the change of the truth value of a fluent. A framework for dealing with surprises is defined. Minimal sets of surprises are provided together with time intervals where each surprise has occurred, and they are characterized from a model-based diagnosis point of view. Then, a probabilistic approach of surprise minimisation is proposed.

The purpose of this book is to provide an overview of AI research, ranging from basic work to interfaces and applications, with as much emphasis on results as on current issues. It is aimed at an audience of master students and Ph.D. students, and can be of interest as well for researchers and engineers who want to know more about AI. The book is split into three volumes.

When allocating indivisible items to agents, it is known that the only strategyproof mechanisms that satisfy a set of rather mild conditions are constrained serial dictatorships: given a fixed order over agents, at each step the designated agent chooses a given number of items (depending on her position in the sequence). With these rules, also known as non-interleaving picking sequences, agents who come earlier in the sequence have a larger choice of items. However, this advantage can be compensated by a higher number of items received by those who come later. How to balance priority in the sequence and number of items received is a nontrivial question. We use a previous model, parameterized by a mapping from ranks to scores, a social welfare functional, and a distribution over preference profiles. For several meaningful choices of parameters, we show that the optimal sequence can be computed in polynomial time. Last, we give a simple procedure for eliciting scoring vectors and we study the impact of the assignment from agents to positions on the ex-post social welfare.

Digital technologies can augment civic participation by facilitating the expression of detailed political preferences. Yet, digital participation efforts often rely on methods optimized for elections involving a few candidates. Here we present data collected in an online experiment where participants built personalized government programs by combining policies proposed by the candidates of the 2022 French and Brazilian presidential elections. We use this data to explore aggregates complementing those used in social choice theory, finding that a metric of divisiveness, which is uncorrelated with traditional aggregation functions, can identify polarizing proposals. These metrics provide a score for the divisiveness of each proposal that can be estimated in the absence of data on the demographic characteristics of participants and that explains the issues that divide a population. These findings suggest divisiveness metrics can be useful complements to traditional aggregation functions in direct forms of digital participation., Comment: 29 pages main manuscript with 5 figures. 55 pages of supplementary material

Voting by sequential elimination is a low-communication voting protocol: voters play in sequence and eliminate one or more of the remaining candidates, until only one remains. While the fairness and efficiency of such protocols have been explored, the impact of strategic behaviour has not been addressed. We model voting by sequential elimination as a game. Given a fixed elimination sequence, we show that the outcome is the same in all subgame-perfect Nash equilibria of the corresponding game, and is polynomial-time computable. We measure the loss of social welfare due to strategic behaviour, with respect to the outcome under sincere behaviour, and with respect to the outcome maximizing social welfare. We give tight bounds for worst-case ratios, and show using experiments that the average impact of manipulation can be much lower than in the worst case.

We define a family of runoff rules that work as follows: voters cast approval ballots over candidates; two finalists are selected; and the winner is decided by majority. With approval-type ballots, there are various ways to select the finalists. We leverage known approval-based committee rules and study the obtained runoff rules from an axiomatic point of view. Then we analyze the outcome of these rules on single-peaked profiles, and on real data.

Assume $k$ candidates need to be selected. The candidates appear over time. Each time one appears, it must be immediately selected or rejected -- a decision that is made by a group of individuals through voting. Assume the voters use approval ballots, i.e., for each candidate they only specify whether they consider it acceptable or not. This setting can be seen as a voting variant of choosing $k$ secretaries. Our contribution is twofold. (1) We assess to what extent the committees that are computed online can proportionally represent the voters. (2) If a prior probability over candidate approvals is available, we show how to compute committees with maximal expected score., Comment: To appear at IJCAI 2022

Epistemic voting interprets votes as noisy signals about a ground truth. We consider contexts where the truth consists of a set of objective winners, knowing a lower and upper bound on its cardinality. A prototypical problem for this setting is the aggre-gation of multi-label annotations with prior knowledge on the size of the ground truth. We posit noisemodels, for which we define rules that output an optimal set of winners. We report on experiments on multi-label annotations (which we collected).

Epistemic social choice aims at unveiling a hidden ground truth given votes, which are interpreted as noisy signals about it. We consider here a simple setting where votes consist of approval ballots: each voter approves a set of alternatives which they believe can possibly be the ground truth. Based on the intuitive idea that more reliable votes contain fewer alternatives, we define several noise models that are approval voting variants of the Mallows model. The likelihood-maximizing alternative is then characterized as the winner of a weighted approval rule, where the weight of a ballot decreases with its cardinality. We have conducted an experiment on three image annotation datasets; they conclude that rules based on our noise model outperform standard approval voting; the best performance is obtained by a variant of the Condorcet noise model., Comment: Accepted in the 36th AAAI Conference on Artificial Intelligence (AAAI 2022)

Many important collective decision-making problems can be seen as multi-agent versions of discrete optimisation problems. Participatory budgeting, for instance, is the collective version of the knapsack problem; other examples include collective scheduling, and collective spanning trees. Rather than developing a specific model, as well as specific algorithmic techniques, for each of these problems, we propose to represent and solve them in the unifying framework of judgment aggregation with weighted issues. We provide a modular definition of collective discrete optimisation (CDO) rules based on coupling a set scoring function with an operator, and we show how they generalise several existing procedures developed for specific CDO problems. We also give an implementation based on integer linear programming (ILP) and test it on the problem of collective spanning trees.

Citizens' assemblies need to represent subpopulations according to their proportions in the general population. These large committees are often constructed in an online fashion by contacting people, asking for the demographic features of the volunteers, and deciding to include them or not. This raises a trade-off between the number of people contacted (and the incurring cost) and the representativeness of the committee. We study three methods, theoretically and experimentally: a greedy algorithm that includes volunteers as long as proportionality is not violated; a non-adaptive method that includes a volunteer with a probability depending only on their features, assuming that the joint feature distribution in the volunteer pool is known; and a reinforcement learning based approach when this distribution is not known a priori but learnt online., Comment: Proceedings of IJCAI 2021

Classical voting rules assume that ballots are complete preference orders over candidates. However, when the number of candidates is large enough, it is too costly to ask the voters to rank all candidates. We suggest to fix a rank k, to ask all voters to specify their best k candidates, and then to consider "top-k approximations" of rules, which take only into account the top-k candidates of each ballot. We consider two measures of the quality of the approximation: the probability of selecting the same winner as the original rule, and the score ratio. We do a worst-case study (for the latter measure only), and for both measures, an average-case study and a study from real data sets., Comment: 17 pages, 7 figures

Selecting a set of alternatives based on the preferences of agents is an important problem in committee selection and beyond. Among the various criteria put forth for the desirability of a committee, Pareto optimality is a minimal and important requirement. As asking agents to specify their preferences over exponentially many subsets of alternatives is practically infeasible, we assume that each agent specifies a weak order on single alternatives, from which a preference relation over subsets is derived using some preference extension. We consider five prominent extensions (responsive, downward lexicographic, upward lexicographic, best, and worst). For each of them, we consider the corresponding Pareto optimality notion, and we study the complexity of computing and verifying Pareto optimal outcomes. We also consider strategic issues: for four of the set extensions, we present a linear-time, Pareto optimal and strategyproof algorithm that even works for weak preferences.

Several tasks in artificial intelligence require to be able to find models about knowledge dynamics. They include belief revision, fusion and belief merging, and abduction. In this paper we exploit the algebraic framework of mathematical morphology in the context of propositional logic, and define operations such as dilation or erosion of a set of formulas. We derive concrete operators, based on a semantic approach, that have an intuitive interpretation and that are formally well behaved, to perform revision, fusion and abduction. Computation and tractability are addressed, and simple examples illustrate the typical results that can be obtained.

This volume consists of papers presented at the Sixteenth Conference on Theoretical Aspects of Rationality and Knowledge (TARK) held at the University of Liverpool, UK, from July 24 to 26, 2017. TARK conferences bring together researchers from a wide variety of fields, including Computer Science (especially, Artificial Intelligence, Cryptography, Distributed Computing), Economics (especially, Decision Theory, Game Theory, Social Choice Theory), Linguistics, Philosophy (especially, Philosophical Logic), and Cognitive Psychology, in order to further understand the issues involving reasoning about rationality and knowledge.

One of the better studied properties for operators in judgment aggregation is independence, which essentially dictates that the collective judgment on one issue should not depend on the individual judgments given on some other issue(s) in the same agenda. Independence, although considered a desirable property, is too strong, because together with mild additional conditions it implies dictatorship. We propose here a weakening of independence, named agenda separability: a judgment aggregation rule satisfies it if, whenever the agenda is composed of several independent sub-agendas, the resulting collective judgment sets can be computed separately for each sub-agenda and then put together. We show that this property is discriminant, in the sense that among judgment aggregation rules so far studied in the literature, some satisfy it and some do not. We briefly discuss the implications of agenda separability on the computation of judgment aggregation rules.

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. While finding an arbitrary Pareto optimal allocation is generally easy, checking whether a particular allocation is Pareto optimal can be much more difficult. This problem is equivalent to checking that the allocated objects cannot be reallocated in such a way that at least one agent prefers her new share to his old one, and no agent prefers her old share to her new one. We consider the problem for two related types of preference relations over sets of objects. In the first part of the paper we focus on the setting in which agents express additive cardinal utilities over objects. We present computational hardness results as well as polynomial-time algorithms for testing Pareto optimality under different restrictions such as two utility values or lexicographic utilities. In the second part of the paper we assume that agents express only their (ordinal) preferences over single objects, and that their preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.

Sequential allocation is a simple allocation mechanism in which agents are given pre-specified turns and each agents gets the most preferred item that is still available. It has long been known that sequential allocation is not strategyproof. Bouveret and Lang (2014) presented a polynomial-time algorithm to compute a best response of an agent with respect to additively separable utilities and claimed that (1) their algorithm correctly finds a best response, and (2) each best response results in the same allocation for the manipulator. We show that both claims are false via an example. We then show that in fact the problem of computing a best response is NP-complete. On the other hand, the insights and results of Bouveret and Lang (2014) for the case of two agents still hold.

We study hedonic games with dichotomous preferences. Hedonic games are cooperative games in which players desire to form coalitions, but only care about the makeup of the coalitions of which they are members; they are indifferent about the makeup of other coalitions. The assumption of dichotomous preferences means that, additionally, each player's preference relation partitions the set of coalitions of which that player is a member into just two equivalence classes: satisfactory and unsatisfactory. A player is indifferent between satisfactory coalitions, and is indifferent between unsatisfactory coalitions, but strictly prefers any satisfactory coalition over any unsatisfactory coalition. We develop a succinct representation for such games, in which each player's preference relation is represented by a propositional formula. We show how solution concepts for hedonic games with dichotomous preferences are characterised by propositional formulas., Comment: This paper was orally presented at the Eleventh Conference on Logic and the Foundations of Game and Decision Theory (LOFT 2014) in Bergen, Norway, July 27-30, 2014

We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. Examples of applications include choosing members of a representative committee, where candidates are described by attributes such as sex, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computation complexity.

The literature on judgment aggregation is moving from studying impossibility results regarding aggregation rules towards studying specific judgment aggregation rules. Here we give a structured list of most rules that have been proposed and studied recently in the literature, together with various properties of such rules. We first focus on the majority-preservation property, which generalizes Condorcet-consistency, and identify which of the rules satisfy it. We study the inclusion relationships that hold between the rules. Finally, we consider two forms of unanimity, monotonicity, homogeneity, and reinforcement, and we identify which of the rules satisfy these properties.

We consider the following problem: There is a set of items (e.g., movies) and a group of agents (e.g., passengers on a plane); each agent has some intrinsic utility for each of the items. Our goal is to pick a set of $K$ items that maximize the total derived utility of all the agents (i.e., in our example we are to pick $K$ movies that we put on the plane's entertainment system). However, the actual utility that an agent derives from a given item is only a fraction of its intrinsic one, and this fraction depends on how the agent ranks the item among the chosen, available, ones. We provide a formal specification of the model and provide concrete examples and settings where it is applicable. We show that the problem is hard in general, but we show a number of tractability results for its natural special cases.

We consider a setting where one has to organize one or several group activities for a set of agents. Each agent will participate in at most one activity, and her preferences over activities depend on the number of participants in the activity. The goal is to assign agents to activities based on their preferences. We put forward a general model for this setting, which is a natural generalization of anonymous hedonic games. We then focus on a special case of our model, where agents' preferences are binary, i.e., each agent classifies all pairs of the form "(activity, group size)" into ones that are acceptable and ones that are not. We formulate several solution concepts for this scenario, and study them from the computational point of view, providing hardness results for the general case as well as efficient algorithms for settings where agents' preferences satisfy certain natural constraints., Comment: 13 pages, presented at WINE-2012 and COMSOC-2012

We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.

We propose a general framework for strategic voting when a voter may lack knowledge about other votes or about other voters' knowledge about her own vote. In this setting we define notions of manipulation and equilibrium. We also model action changing knowledge about votes, such as a voter revealing its preference or as a central authority performing a voting poll. Some forms of manipulation are preserved under such updates and others not. Another form of knowledge dynamics is the effect of a voter declaring its vote. We envisage Stackelberg games for uncertain profiles. The purpose of this investigation is to provide the epistemic background for the analysis and design of voting rules that incorporate uncertainty., Comment: 10 pages, Poster presentation at TARK 2013 (arXiv:1310.6382) http://www.tark.org

Knowledge-based programs (KBPs) are high-level protocols describing the course of action an agent should perform as a function of its knowledge. The use of KBPs for expressing action policies in AI planning has been surprisingly overlooked. Given that to each KBP corresponds an equivalent plan and vice versa, KBPs are typically more succinct than standard plans, but imply more on-line computation time. Here we make this argument formal, and prove that there exists an exponential succinctness gap between knowledge-based programs and standard plans. Then we address the complexity of plan existence. Some results trivially follow from results already known from the literature on planning under incomplete knowledge, but many were unknown so far., Comment: 10 pages, Contributed talk at TARK 2013 (arXiv:1310.6382) http://www.tark.org

We consider a voting setting where candidates have preferences about the outcome of the election and are free to join or leave the election. The corresponding candidacy game, where candidates choose strategically to participate or not, has been studied %initially by Dutta et al., who showed that no non-dictatorial voting procedure satisfying unanimity is candidacy-strategyproof, that is, is such that the joint action where all candidates enter the election is always a pure strategy Nash equilibrium. Dutta et al. also showed that for some voting tree procedures, there are candidacy games with no pure Nash equilibria, and that for the rule that outputs the sophisticated winner of voting by successive elimination, all games have a pure Nash equilibrium. No results were known about other voting rules. Here we prove several such results. For four candidates, the message is, roughly, that most scoring rules (with the exception of Borda) do not guarantee the existence of a pure Nash equilibrium but that Condorcet-consistent rules, for an odd number of voters, do. For five candidates, most rules we study no longer have this guarantee. Finally, we identify one prominent rule that guarantees the existence of a pure Nash equilibrium for any number of candidates (and for an odd number of voters): the Copeland rule. We also show that under mild assumptions on the voting rule, the existence of strong equilibria cannot be guaranteed.

In this paper an approach to automated deduction under uncertainty,based on possibilistic logic, is proposed ; for that purpose we deal with clauses weighted by a degree which is a lower bound of a necessity or a possibility measure, according to the nature of the uncertainty. Two resolution rules are used for coping with the different situations, and the refutation method can be generalized. Besides the lower bounds are allowed to be functions of variables involved in the clause, which gives hypothetical reasoning capabilities. The relation between our approach and the idea of minimizing abnormality is briefly discussed. In case where only lower bounds of necessity measures are involved, a semantics is proposed, in which the completeness of the extended resolution principle is proved. Moreover deduction from a partially inconsistent knowledge base can be managed in this approach and displays some form of non-monotonicity., Comment: Appears in Proceedings of the Fifth Conference on Uncertainty in Artificial Intelligence (UAI1989)

A semantics is given to possibilistic logic, a logic that handles weighted classical logic formulae, and where weights are interpreted as lower bounds on degrees of certainty or possibility, in the sense of Zadeh's possibility theory. The proposed semantics is based on fuzzy sets of interpretations. It is tolerant to partial inconsistency. Satisfiability is extended from interpretations to fuzzy sets of interpretations, each fuzzy set representing a possibility distribution describing what is known about the state of the world. A possibilistic knowledge base is then viewed as a set of possibility distributions that satisfy it. The refutation method of automated deduction in possibilistic logic, based on previously introduced generalized resolution principle is proved to be sound and complete with respect to the proposed semantics, including the case of partial inconsistency., Comment: Appears in Proceedings of the Seventh Conference on Uncertainty in Artificial Intelligence (UAI1991)

A key issue in the handling of temporal data is the treatment of persistence; in most approaches it consists in inferring defeasible confusions by extrapolating from the actual knowledge of the history of the world; we propose here a gradual modelling of persistence, following the idea that persistence is decreasing (the further we are from the last time point where a fluent is known to be true, the less certainly true the fluent is); it is based on possibility theory, which has strong relations with other well-known ordering-based approaches to nonmonotonic reasoning. We compare our approach with Dean and Kanazawa's probabilistic projection. We give a formal modelling of the decreasing persistence problem. Lastly, we show how to infer nonmonotonic conclusions using the principle of decreasing persistence., Comment: Appears in Proceedings of the Ninth Conference on Uncertainty in Artificial Intelligence (UAI1993)

We propose an integration of possibility theory into non-classical logics. We obtain many formal results that generalize the case where possibility and necessity functions are based on classical logic. We show how useful such an approach is by applying it to reasoning under uncertain and inconsistent information., Comment: Appears in Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994)

We view the syntax-based approaches to default reasoning as a model-based diagnosis problem, where each source giving a piece of information is considered as a component. It is formalized in the ATMS framework (each source corresponds to an assumption). We assume then that all sources are independent and "fail" with a very small probability. This leads to a probability assignment on the set of candidates, or equivalently on the set of consistent environments. This probability assignment induces a Dempster-Shafer belief function which measures the probability that a proposition can be deduced from the evidence. This belief function can be used in several different ways to define a non-monotonic consequence relation. We study and compare these consequence relations. The -case of prioritized knowledge bases is briefly considered., Comment: Appears in Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994)

Penalty logic, introduced by Pinkas, associates to each formula of a knowledge base the price to pay if this formula is violated. Penalties may be used as a criterion for selecting preferred consistent subsets in an inconsistent knowledge base, thus inducing a non-monotonic inference relation. A precise formalization and the main properties of penalty logic and of its associated non-monotonic inference relation are given in the first part. We also show that penalty logic and Dempster-Shafer theory are related, especially in the infinitesimal case., Comment: Appears in Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence (UAI1994)

The Constraint Satisfaction Problem (CSP) framework offers a simple and sound basis for representing and solving simple decision problems, without uncertainty. This paper is devoted to an extension of the CSP framework enabling us to deal with some decisions problems under uncertainty. This extension relies on a differentiation between the agent-controllable decision variables and the uncontrollable parameters whose values depend on the occurrence of uncertain events. The uncertainty on the values of the parameters is assumed to be given under the form of a probability distribution. Two algorithms are given, for computing respectively decisions solving the problem with a maximal probability, and conditional decisions mapping the largest possible amount of possible cases to actual decisions., Comment: Appears in Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence (UAI1995)

This article deals with plausible reasoning from incomplete knowledge about large-scale spatial properties. The availableinformation, consisting of a set of pointwise observations,is extrapolated to neighbour points. We make use of belief functions to represent the influence of the knowledge at a given point to another point; the quantitative strength of this influence decreases when the distance between both points increases. These influences arethen aggregated using a variant of Dempster's rule of combination which takes into account the relative dependence between observations., Comment: Appears in Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence (UAI2001)

In voting contexts, some new candidates may show up in the course of the process. In this case, we may want to determine which of the initial candidates are possible winners, given that a fixed number $k$ of new candidates will be added. We give a computational study of this problem, focusing on scoring rules, and we provide a formal comparison with related problems such as control via adding candidates or cloning., Comment: 34 pages

In multiagent settings where the agents have different preferences, preference aggregation is a central issue. Voting is a general method for preference aggregation, but seminal results have shown that all general voting protocols are manipulable. One could try to avoid manipulation by using voting protocols where determining a beneficial manipulation is hard computationally. The complexity of manipulating realistic elections where the number of candidates is a small constant was recently studied (Conitzer 2002), but the emphasis was on the question of whether or not a protocol becomes hard to manipulate for some constant number of candidates. That work, in many cases, left open the question: How many candidates are needed to make elections hard to manipulate? This is a crucial question when comparing the relative manipulability of different voting protocols. In this paper we answer that question for the voting protocols of the earlier study: plurality, Borda, STV, Copeland, maximin, regular cup, and randomized cup. We also answer that question for two voting protocols for which no results on the complexity of manipulation have been derived before: veto and plurality with runoff. It turns out that the voting protocols under study become hard to manipulate at 3 candidates, 4 candidates, 7 candidates, or never.