Jérôme Lang

AAMAS Conference 2026 Conference Paper

Computational Social Choice: Research & Development

• Dorothea Baumeister
• Ratip Emin Berker
• Niclas Boehmer
• Sylvain Bouveret
• Andreas Darmann
• Piotr Faliszewski
• Martin Lackner
• Jérôme Lang

Computational social choice (COMSOC) studies principled ways to aggregate conflicting individual preferences into collective decisions. In this paper, we call for an increased effort towards Computational Social Choice: Research & Development (COMSOC-R&D), a problem-driven research agenda that explicitly aims to design, implement, and test collective decision-making systems in the real world. We articulate the defining features of COMSOC-R&D, argue for its value, and discuss various roadblocks and possible solutions.

JAAMAS Journal 2026 Journal Article

Utilitarian Desires

• Jérôme Lang
• Leendert van der Torre
• Emil Weydert

Abstract Autonomous agents reason frequently about preferences such as desires and goals. In this paper we propose a logic of desires with a utilitarian semantics, in which we study nonmonotonic reasoning about desires and preferences based on the idea that desires can be understood in terms of utility losses (penalties for violations) and utility gains (rewards for fulfillments). Our logic allows for a systematic study and classification of desires, for example by distinguishing subtly different ways to add up these utility losses and gains. We propose an explicit construction of the agent's preference relation from a set of desires together with different kinds of knowledge. A set of desires extended with knowledge induces a set of ‘distinguished’ utility functions by adding up the utility losses and gains of the individual desires, and these distinguished utility functions induce the preference relation.

IJCAI Conference 2025 Conference Paper

Constrained Serial Dictatorships Can Be Fair

• Sylvain Bouveret
• Hugo Gilbert
• Jérôme Lang
• Guillaume Méroué

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). 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 exactly in polynomial time or approximated using sampling. Our results hold for several probabilistic models on preference profiles, with an emphasis on the Plackett-Luce model. We conclude with experimental results showing how the optimal sequence is impacted by various parameters.

AAMAS Conference 2024 Conference Paper

Discovering Consistent Subelections

• Łukasz Janeczko
• Jérôme Lang
• Grzegorz Lisowski
• Stanisław Szufa

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.

AAAI Conference 2024 Conference Paper

Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion

• Théo Delemazure
• Jérôme Lang
• Grzegorz Pierczyński

We give a quantitative analysis of the independence of irrelevant alternatives (IIA) axiom. IIA says that the society's preference between x and y should depend only on individual preferences between x and y: we show that, in several contexts, if the individuals express their preferences about additional (``irrelevant'') alternatives, this information helps to estimate better which of x and y has higher social welfare. Our contribution is threefold: (1) we provide a new tool to measure the impact of IIA on social welfare (pairwise distortion), based on the well-established notion of voting distortion, (2) we study the average impact of IIA in both general and metric settings, with experiments on synthetic and real data and (3) we study the worst-case impact of IIA in the 1D-Euclidean metric space.

ECAI Conference 2023 Conference Paper

Fair Rent Division on a Budget Revisited

• Stéphane Airiau
• Hugo Gilbert
• Umberto Grandi
• Jérôme Lang
• Anaëlle Wilczynski

Rent division consists in simultaneously computing an allocation of rooms to agents and a payment, starting from an individual valuation of each room by each agent. When agents have budget limits, it is known that envy-free solutions do not necessarily exist. We propose two solutions to overcome this problem. In the first one, we relax envy-freeness to account for budget disparities. In the second one, we allow fractional allocations, in which agents may change rooms during the duration of the lease.

AAAI Conference 2023 Conference Paper

Multiwinner Voting with Possibly Unavailable Candidates

• Markus Brill
• Hayrullah Dindar
• Jonas Israel
• Jérôme Lang
• Jannik Peters
• Ulrike Schmidt-Kraepelin

Selecting a committee that meets diversity and proportionality criteria is a challenging endeavor that has been studied extensively in recent years. This task becomes even more challenging when some of the selected candidates decline the invitation to join the committee. Since the unavailability of one candidate may impact the rest of the selection, inviting all candidates at the same time may lead to a suboptimal committee. Instead, invitations should be sequential and conditional on which candidates invited so far accepted the invitation: the solution to the committee selection problem is a query policy. If invitation queries are binding, they should be safe: one should not query a candidate without being sure that whatever the set of available candidates possible at that stage, her inclusion will not jeopardize committee optimality. Assuming approval-based inputs, we characterize the set of rules for which a safe query exists at every stage. In order to parallelize the invitation process, we investigate the computation of safe parallel queries, and show that it is often hard. We also study the existence of safe parallel queries with respect to proportionality axioms such as extended justified representation.

AIJ Journal 2023 Journal Article

Portioning using ordinal preferences: Fairness and efficiency

• Stéphane Airiau
• Haris Aziz
• Ioannis Caragiannis
• Justin Kruger
• Jérôme Lang
• Dominik Peters

A divisible public resource is to be divided among projects. We study rules that decide on a distribution of the budget when voters have ordinal preference rankings over projects. Examples of such portioning problems are participatory budgeting, time shares, and parliament elections. We introduce a family of rules for portioning, inspired by positional scoring rules. Rules in this family are given by a scoring vector (such as plurality or Borda) associating a positive value with each rank in a vote, and an aggregation function such as leximin or the Nash product. Our family contains well-studied rules, but most are new. We discuss computational and normative properties of our rules. We focus on fairness, and introduce the SD-core, a group fairness notion. Our Nash rules are in the SD-core, and the leximin rules satisfy individual fairness properties. Both are Pareto-efficient.

IJCAI Conference 2022 Conference Paper

Approval with Runoff

• Théo Delemazure
• Jérôme Lang
• Jean-François Laslier
• M. Remzi Sanver

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.

JAAMAS Journal 2022 Journal Article

Approximating voting rules from truncated ballots

• Manel Ayadi
• Nahla Ben Amor
• Jérôme Lang

Abstract 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. The questions are then: Are these k-truncated approximations good predictors of the approximated rule? For which values of k and under which assumptions can we expect to output the correct winner with high probability? For different voting rules, we study these questions theoretically, by giving tight approximation ratios, and empirically, based on randomly generated profiles and on real data. 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.

UAI Conference 2022 Conference Paper

Multi-winner approval voting goes epistemic

• Tahar Allouche
• Jérôme Lang
• Florian Yger

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 aggregation of multi-label annotations with prior knowledge on the size of the ground truth. We posit noise models, for which we define rules that output an optimal set of winners. We report on experiments on multi-label annotations (which we collected).

IJCAI Conference 2022 Conference Paper

Online Approval Committee Elections

• Virginie Do
• Matthieu Hervouin
• Jérôme Lang
• Piotr Skowron

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.

AAMAS Conference 2022 Conference Paper

Selecting PhD Students and Projects with Limited Funding

• Jatin Jindal
• Jérôme Lang
• Katarína Cechlárová
• Julien Lesca

In some universities, there is a fixed number of PhD grants, but a larger number of eligible projects and students, each student being allowed to apply on several projects, and a committee builds up a ranking (masterlist) over student-project pairs. The paper analyses three mechanisms to choose the pairs to be funded. The first one, used in some universities, is a greedy mechanism that gives a huge priority to the masterlist and very little to student’s preferences. At the other extremity of the spectrum, we have a priority-list variant of student-oriented Gale-Shapley. It is strategyproof and optimal for students, but has one drawback: it pays too little attention to the masterlist, and thus to the committee. Inbetween, we have an intermediate mechanism which can be seen as a good tradeoff. Among the properties we study, one is specific to our setting: dynamic monotonicity, which deals with cases when a student suddenly leaves the system in the middle of the process.

AAAI Conference 2022 Conference Paper

Truth-Tracking via Approval Voting: Size Matters

• Tahar Allouche
• Jérôme Lang
• Florian Yger

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 likelihoodmaximizing 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.

AAAI Conference 2021 Conference Paper

A Market-Inspired Bidding Scheme for Peer Review Paper Assignment

• Reshef Meir
• Jérôme Lang
• Julien Lesca
• Nicholas Mattei
• Natan Kaminsky

We propose a market-inspired bidding scheme for the assignment of paper reviews in large academic conferences. We provide an analysis of the incentives of reviewers during the bidding phase, when reviewers have both private costs and some information about the demand for each paper; and their goal is to obtain the best possible k papers for a predetermined k. We show that by assigning ‘budgets’ to reviewers and a ‘price’ for every paper that is (roughly) proportional to its demand, the best response of a reviewer is to bid sincerely, i. e. , on her most favorite papers, and match the budget even when it is not enforced. This game-theoretic analysis is based on a simple, prototypical assignment algorithm. We show via extensive simulations on bidding data from real conferences, that our bidding scheme would substantially improve both the bid distribution and the resulting assignment.

AAAI Conference 2021 Short Paper

Compilation Complexity of Multi-Winner Voting Rules (Student Abstract)

• Neel Karia
• Jérôme Lang

Compiling the votes of a subelectorate consists of storing the votes of a subset of voters in a compressed form, such that the winners can still be determined when additional votes are included. This leads to the notion of compilation complexity, which has already been investigated for single-winner voting rules. We perform a compilation complexity analysis of several common multi-winner voting rules.

IJCAI Conference 2021 Conference Paper

Online Selection of Diverse Committees

• Virginie Do
• Jamal Atif
• Jérôme Lang
• Nicolas Usunier

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.

EUMAS Conference 2020 Conference Paper

Approximating Voting Rules from Truncated Ballots

• Manel Ayadi 0002
• Nahla Ben Amor
• Jérôme Lang

Abstract 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.

IJCAI Conference 2020 Conference Paper

Collective Decision Making under Incomplete Knowledge: Possible and Necessary Solutions

• Jérôme Lang

Most solution concepts in collective decision making are defined assuming complete knowledge of individuals' preferences and of the mechanism used for aggregating them. This is often unpractical or unrealistic. Under incomplete knowledge, a solution advocated by many consists in quanrtifying over all completions of the incomplete preference profile (or all instantiations of the incompletely specified mechanism). Voting rules can be `modalized' this way (leading to the notions of possible and necessary winners), and also efficiency and fairness notions in fair division, stability concepts in coalition formation, and more. I give here a survey of works along this line.

JAIR Journal 2020 Journal Article

Hedonic Games with Ordinal Preferences and Thresholds

• Anna Maria Kerkmann
• Jérôme Lang
• Anja Rey
• Jörg Rothe
• Hilmar Schadrack
• Lena Schend

We propose a new representation setting for hedonic games, where each agent partitions the set of other agents into friends, enemies, and neutral agents, with friends and enemies being ranked. Under the assumption that preferences are monotonic (respectively, antimonotonic) with respect to the addition of friends (respectively, enemies), we propose a bipolar extension of the responsive extension principle, and use this principle to derive the (partial) preferences of agents over coalitions. Then, for a number of solution concepts, we characterize partitions that necessarily or possibly satisfy them, and we study the related problems in terms of their complexity.

AIJ Journal 2020 Journal Article

Knowledge-based programs as succinct policies for partially observable domains

• Bruno Zanuttini
• Jérôme Lang
• Abdallah Saffidine
• François Schwarzentruber

We suggest to express policies for contingent planning by knowledge-based programs (KBPs). KBPs, introduced by Fagin et al. (1995) [32], are high-level protocols describing the actions that the agent should perform as a function of their current knowledge: branching conditions are epistemic formulas that are interpretable by the agent. The main aim of our paper is to show that KBPs can be seen as a succinct language for expressing policies in single-agent contingent planning. KBP are conceptually very close to languages used for expressing policies in the partially observable planning literature: like them, they have conditional and looping structures, with actions as atomic programs and Boolean formulas on beliefs for choosing the execution path. Now, the specificity of KBPs is that branching conditions refer to the belief state and not to the observations. Because of their structural proximity, KBPs and standard languages for representing policies have the same power of expressivity: every standard policy can be expressed as a KBP, and every KBP can be “unfolded” into a standard policy. However, KBPs are more succinct, more readable, and more explainable than standard policies. On the other hand, they require more online computation time, but we show that this is an unavoidable tradeoff. We study knowledge-based programs along four criteria: expressivity, succinctness, complexity of online execution, and complexity of verification.

JAIR Journal 2020 Journal Article

The Complexity Landscape of Outcome Determination in Judgment Aggregation

• Ulle Endriss
• Ronald de Haan
• Jérôme Lang
• Marija Slavkovik

We provide a comprehensive analysis of the computational complexity of the outcome determination problem for the most important aggregation rules proposed in the literature on logic-based judgment aggregation. Judgment aggregation is a powerful and flexible framework for studying problems of collective decision making that has attracted interest in a range of disciplines, including Legal Theory, Philosophy, Economics, Political Science, and Artificial Intelligence. The problem of computing the outcome for a given list of individual judgments to be aggregated into a single collective judgment is the most fundamental algorithmic challenge arising in this context. Our analysis applies to several different variants of the basic framework of judgment aggregation that have been discussed in the literature, as well as to a new framework that encompasses all existing such frameworks in terms of expressive power and representational succinctness.

TCS Journal 2019 Journal Article

Efficient reallocation under additive and responsive preferences

• Haris Aziz
• Péter Biró
• Jérôme Lang
• Julien Lesca
• Jérôme Monnot

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 allocation to her old one, and no agent prefers her old allocation 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 individual objects, and that their underlying preferences are additively separable. In this setting, we present characterizations and polynomial-time algorithms for possible and necessary Pareto optimality.

IJCAI Conference 2019 Conference Paper

Portioning Using Ordinal Preferences: Fairness and Efficiency

• Stéphane Airiau
• Haris Aziz
• Ioannis Caragiannis
• Justin Kruger
• Jérôme Lang
• Dominik Peters

A public divisible resource is to be divided among projects. We study rules that decide on a distribution of the budget when voters have ordinal preference rankings over projects. Examples of such portioning problems are participatory budgeting, time shares, and parliament elections. We introduce a family of rules for portioning, inspired by positional scoring rules. Rules in this family are given by a scoring vector (such as plurality or Borda) associating a positive value with each rank in a vote, and an aggregation function such as leximin or the Nash product. Our family contains well-studied rules, but most are new. We discuss computational and normative properties of our rules. We focus on fairness, and introduce the SD-core, a group fairness notion. Our Nash rules are in the SD-core, and the leximin rules satisfy individual fairness properties. Both are Pareto-efficient.

AAMAS Conference 2019 Conference Paper

Single Transferable Vote: Incomplete Knowledge and Communication Issues

• Manel Ayadi
• Nahla Ben Amor
• Jérôme Lang
• Dominik Peters

Single Transferable Vote (STV) is used in large political elections around the world. It is easy to understand and has desirable normative properties such as clone-proofness. However, voters need to report full rankings, which can make it less practical than plurality voting. We study ways to minimize the amount of communication required to use single-winner STV. In the first part of the paper, voters are assumed to report their top-k alternatives in a single shot. We empirically evaluate the extent to which STV with truncated ballots approximates STV with full information. We also study the computational complexity of the possible winner problem for top-k ballots. For k = 1, it can be solved in polynomial time, but is NPcomplete when k ⩾ 2. In the second part, we consider interactive communication protocols for STV. Building on a protocol proposed by Conitzer and Sandholm (2005), we show how we can reduce the amount of communication required in practice. We then study empirically the average communication complexity of these protocols, based on randomly generated profiles, and on real-world election data. Our conclusion is that STV needs, in practice, much less information than in the worst case.

AAAI Conference 2018 Conference Paper

Knowledge, Fairness, and Social Constraints

• Haris Aziz
• Sylvain Bouveret
• Ioannis Caragiannis
• Ira Giagkousi
• Jérôme Lang

In the context of fair allocation of indivisible items, fairness concepts often compare the satisfaction of an agent to the satisfaction she would have from items that are not allocated to her: in particular, envy-freeness requires that no agent prefers the share of someone else to her own share. We argue that these notions could also be defined relative to the knowledge that an agent has on how the items that she does not receive are distributed among other agents. We define a family of epistemic notions of envy-freeness, parameterized by a social graph, where an agent observes the share of her neighbours but not of her non-neighbours. We also define an intermediate notion between envy-freeness and proportionality, also parameterized by a social graph. These weaker notions of envy-freeness are useful when seeking a fair allocation, since envy-freeness is often too strong. We position these notions with respect to known ones, thus revealing new rich hierarchies of fairness concepts. Finally, we present a very general framework that covers all the existing and many new fairness concepts.

AIJ Journal 2018 Journal Article

Multi-attribute proportional representation

• Jérôme Lang
• Piotr Skowron

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. An example of application is the choice of members for a representative committee, where candidates are described by attributes such as gender, 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. Another example of application is the selection of a common set of items to be used by a group of users, where items are labelled by attribute values. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such a 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 computational complexity.

AIJ Journal 2018 Journal Article

Voting on multi-issue domains with conditionally lexicographic preferences

• Jérôme Lang
• Jérôme Mengin
• Lirong Xia

One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.

IJCAI Conference 2017 Conference Paper

Voting by sequential elimination with few voters

• Sylvain Bouveret
• Yann Chevaleyre
• François Durand
• Jérôme Lang

We define a new class of low-communication voting rules, tailored for contexts with few voters and possibly many candidates. These rules are defined by a predefined sequence of voters: at each stage, the designated voter eliminates a candidate, and the last remaining candidate wins. We study both deterministic (non-anonymous) variants, and randomized (and anonymous) versions of these rules. We focus on a subfamily of these rules defined by ``non-interleaved'' sequences. We first focus on the axiomatic properties of our rules. Then we focus on the identification of the non-interleaved sequence that gives the best approximation of the Borda score under the impartial culture. Finally, we apply our rules to randomly generated data. Our conclusion is that, in contexts where there are more candidates than voters, elimination-based rules allow for a very low communication complexity (and especially, avoid asking voters to rank alternatives), and yet can be good approximations of common voting rules, while enjoying a number of good properties.

AAAI Conference 2016 Conference Paper

Agenda Separability in Judgment Aggregation

• Jérôme Lang
• Marija Slavkovik
• Srdjan Vesic

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.

KR Conference 2016 Conference Paper

Boolean Hedonic Games

• Haris Aziz
• Paul Harrenstein
• Jérôme Lang
• Michael Wooldridge

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.

AIJ Journal 2016 Journal Article

Finding a collective set of items: From proportional multirepresentation to group recommendation

• Piotr Skowron
• Piotr Faliszewski
• Jérôme Lang

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.

AAAI Conference 2016 Conference Paper

Multi-Attribute Proportional Representation

• Jérôme Lang
• Piotr Skowron

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 fit. 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 boils down to the apportionment problem for party-list proportional representation systems (in such case the value of the single attribute is the political affiliation of a candidate). We study some properties of the associated subset selection rules, and address their computation.

AAMAS Conference 2016 Conference Paper

Optimal Reallocation Under Additive and Ordinal Preferences

• Haris Aziz
• Péter Biró
• Jérôme Lang
• Julien Lesca
• Jérôme Monnot

Reallocating resources to get mutually beneficial outcomes is a fundamental problem in various multi-agent settings. 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. General Terms Economics, Theory and Algorithms

KR Conference 2016 Conference Paper

Succinctness of Languages for Judgment Aggregation

• Ulle Endriss
• Umberto Grandi
• Ronald de Haan
• Jérôme Lang

We review several different languages for collective decision making problems, in which agents express their judgments, opinions, or beliefs over elements of a logically structured domain. Several such languages have been proposed in the literature to compactly represent the questions on which the agents are asked to give their views. In particular, the framework of judgment aggregation allows agents to vote directly on complex, logically related formulas, whereas the setting of binary aggregation asks agents to vote on propositional variables, over which dependencies are expressed by means of an integrity constraint. We compare these two languages and some of their variants according to their relative succinctness and according to the computational complexity of aggregating several individual views expressed in such languages into a collective judgment. Our main finding is that the formula-based language of judgment aggregation is more succinct than the constraint-based language of binary aggregation. In many (but not all) practically relevant situations, this increase in succinctness does not entail an increase in complexity of the corresponding problem of computing the outcome of an aggregation rule. 1 Jérôme Lang Algorithms and Complexity Group LAMSADE Technische Universität Wien Université Paris-Dauphine Austria France

ECAI Conference 2014 Conference Paper

A weakening of independence in judgment aggregation: agenda separability

• Jérôme Lang
• Marija Slavkovik 0001
• Srdjan Vesic

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 is a desirable property for various reasons, but unfortunately it is too strong, as, together with mild additional conditions, it implies dictatorship. We propose here a weakening of independence, named agenda separability and show that this property is discriminant, i. e. , some judgment aggregation rules satisfy it, others do not.

ECAI Conference 2014 Conference Paper

How Hard is it to Compute Majority-Preserving Judgment Aggregation Rules?

• Jérôme Lang
• Marija Slavkovik 0001

Several recent articles have studied judgment aggregation rules under the point of view of the normative properties they satisfy. However, a further criterion to choose between rules is their computational complexity. Here we review a few rules already proposed and studied in the literature, and identify the complexity of computing the outcome.

ECAI Conference 2014 Conference Paper

Manipulating picking sequences

• Sylvain Bouveret
• Jérôme Lang

Picking sequences are a natural way of allocating indivisible items to agents in a decentralized manner: at each stage, a designated agent chooses an item among those that remain available. We address the computational issues of the manipulation of picking sequences by an agent or a coalition of agents. We show that a single agent can compute an optimal manipulation in polynomial time. Then we consider several notions of coalitional manipulation; for one of these notions, we show that computing an optimal manipulation is easy. We temper these results by giving a nontrivial upper bound on the impact of manipulation on the loss of social welfare.

AAAI Conference 2014 Conference Paper

Robust Winners and Winner Determination Policies under Candidate Uncertainty

• Craig Boutilier
• Jérôme Lang
• Joel Oren
• Héctor Palacios

We consider voting situations in which some candidates may turn out to be unavailable. When determining availability is costly (e. g. , in terms of money, time, or computation), voting prior to determining candidate availability and testing the winner’s availability after the vote may be beneficial. However, since few voting rules are robust to candidate deletion, winner determination requires a number of such availability tests. We outline a model for analyzing such problems, defining robust winners relative to potential candidate unavailability. We assess the complexity of computing robust winners for several voting rules. Assuming a distribution over availability, and costs for availability tests/queries, we describe algorithms for computing optimal query policies, which minimize the expected cost of determining true winners.

ECAI Conference 2014 Conference Paper

Scoring Rules for the Allocation of Indivisible Goods

• Dorothea Baumeister
• Sylvain Bouveret
• Jérôme Lang
• Nhan-Tam Nguyen
• Trung Thanh Nguyen 0004
• Jörg Rothe

We define a family of rules for dividing m indivisible goods among agents, parameterized by a scoring vector and a social welfare aggregation function. We assume that agents' preferences over sets of goods are additive, but that the input is ordinal: each agent simply ranks single goods. Similarly to (positional) scoring rules in voting, a scoring vector s = (s1, .. ., sm) consists of m nonincreasing nonnegative weights, where siis the score of a good assigned to an agent who ranks it in position i. The global score of an allocation for an agent is the sum of the scores of the goods assigned to her. The social welfare of an allocation is the aggregation of the scores of all agents, for some aggregation function ★ such as, typically, + or min. The rule associated with s and ★ maps a profile to (one of) the allocation(s) maximizing social welfare. After defining this family of rules, and focusing on some key examples, we investigate some of the social-choice-theoretic properties of this family of rules, such as various kinds of monotonicity, separability, envy-freeness, and Pareto efficiency.

AAAI Conference 2014 Conference Paper

Voting with Rank Dependent Scoring Rules

• Judy Goldsmith
• Jérôme Lang
• Nicholas Mattei
• Patrice Perny

Positional scoring rules in voting compute the score of an alternative by summing the scores for the alternative induced by every vote. This summation principle ensures that all votes contribute equally to the score of an alternative. We relax this assumption and, instead, aggregate scores by taking into account the rank of a score in the ordered list of scores obtained from the votes. This defines a new family of voting rules, rank-dependent scoring rules (RDSRs), based on ordered weighted average (OWA) operators, which, include all scoring rules, and many others, most of which of new. We study some properties of these rules, and show, empirically, that certain RDSRs are less manipulable than Borda voting, across a variety of statistical cultures.

AIJ Journal 2013 Journal Article

Incentive engineering for Boolean games

• Michael Wooldridge
• Ulle Endriss
• Sarit Kraus
• Jérôme Lang

Boolean games are a natural, compact, and expressive class of logic-based games, in which each player exercises unique control over some set of Boolean variables, and has some logical goal formula that it desires to be achieved. A playerʼs strategy set is the set of all possible valuations that may be made to its variables. A playerʼs goal formula may contain variables controlled by other agents, and in this case, it must reason strategically about how best to assign values to its variables. In the present paper, we consider the possibility of overlaying Boolean games with taxation schemes. A taxation scheme imposes a cost on every possible assignment an agent can make. By designing a taxation scheme appropriately, it is possible to perturb the preferences of agents so that they are rationally incentivised to choose some desirable equilibrium that might not otherwise be chosen, or incentivised to rule out some undesirable equilibria. After formally presenting the model, we explore some issues surrounding it (e. g. , the complexity of finding a taxation scheme that implements some desirable outcome), and then discuss possible desirable properties of taxation schemes.

TARK Conference 2013 Conference Paper

Knowledge-Based Programs as Plans: Succinctness and the Complexity of Plan Existence

• Jérôme Lang
• Bruno Zanuttini

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 knowledgebased 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. 1.

TARK Conference 2013 Conference Paper

Strategic voting and the logic of knowledge

• Hans van Ditmarsch
• Jérôme Lang
• Abdallah Saffidine

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.

ECAI Conference 2012 Conference Paper

Knowledge-Based Programs as Plans - The Complexity of Plan Verification

• Jérôme Lang
• Bruno Zanuttini

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 underlooked. Given that to each KBP corresponds an equivalent plan and vice versa, KBPs are typically more succinct than standard plans, but imply more online computation time. Here we compare KBPs and standard plans according to succinctness and to the complexity of plan verification.

AIJ Journal 2011 Journal Article

Belief extrapolation (or how to reason about observations and unpredicted change)

• Florence Dupin de Saint-Cyr
• Jérôme Lang

We give a logical framework for reasoning with observations at different time points. We call belief extrapolation the process of completing initial belief sets stemming from observations by assuming minimal change. We give a general semantics and we propose several extrapolation operators. We study some key properties verified by these operators and we address computational issues. We study in detail the position of belief extrapolation with respect to revision and update: in particular, belief extrapolation is shown to be a specific form of time-stamped belief revision. Several related lines of work are positioned with respect to belief extrapolation.

TARK Conference 2011 Conference Paper

Compilation and communication protocols for voting rules with a dynamic set of candidates

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Jérôme Monnot

We address the problem of designing communication protocols for voting rules when the set of candidates can evolve via the addition of new candidates. We show that the necessary amount of communication that must be transmitted between the voters and the central authority depends on the amount of space devoted to the storage of the votes over the initial set of candidates. This calls for a bicriteria evaluation of protocols. We consider a few usual voting rules, and three types of storage functions: full storage, where the full votes on the initial set of voters are stored; null storage, where nothing is stored; and anonymous storage, which lies in-between. For some of these pairs (voting rule, type of storage) we design protocols and show that they are asymptotically optimal by determining the communication complexity of the rule under the storage function considered.

TARK Conference 2011 Conference Paper

Judgment aggregation rules based on minimization

• Jérôme Lang
• Gabriella Pigozzi
• Marija Slavkovik 0001
• Leendert W. N. van der Torre

Many voting rules are based on some minimization principle. Likewise, in the field of logic-based knowledge representation and reasoning, many belief change or inconsistency handling operators also make use of minimization. Surprisingly, minimization has not played a major role in the field of judgment aggregation, in spite of its proximity to voting theory and logic-based knowledge representation and reasoning. Here we make a step in this direction and study six judgment aggregation rules; two of them, based on distances, have been previously defined; the other four are new, and all inspired both by voting theory and knowledge representation and reasoning. We study the inclusion relationships between these rules and address some of their social choice theoretic properties.

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

Fair Division under Ordinal Preferences: Computing Envy-Free Allocations of Indivisible Goods

• Sylvain Bouveret
• Ulle Endriss
• Jérôme Lang

We study the problem of fairly dividing a set of goods amongst a group of agents, when those agents have preferences that are ordinal relations over alternative bundles of goods (rather than utility functions) and when our knowledge of those preferences is incomplete. The incompleteness of the preferences stems from the fact that each agent reports their preferences by means of an expression of bounded size in a compact preference representation language. Specifically, we assume that each agent only provides a ranking of individual goods (rather than of bundles). In this context, we consider the algorithmic problem of deciding whether there exists an allocation that is possibly (or necessarily) envy-free, given the incomplete preference information available, if in addition some mild economic efficiency criteria need to be satisfied. We provide simple characterisations, giving rise to simple algorithms, for some instances of the problem, and computational complexity results, establishing the intractability of the problem, for others.

KR Conference 2010 Conference Paper

From preference logics to preference languages, and back

• Meghyn Bienvenu
• Jérôme Lang
• Nic Wilson

show in the paper, some well-known preference languages Preference logics and AI preference representation languages are both concerned with reasoning about preferences on combinatorial domains, yet so far these two streams of research have had little interaction. This paper contributes to the bridging of these areas. We start by constructing a “prototypical” preference logic, which combines features of existing preference logics, and then we show that many well-known preference languages, such as CP-nets and its extensions, are natural fragments of it. After establishing useful characterizations of dominance and consistency in our logic, we study the complexity of satisfiability in the general case as well as for meaningful fragments, and we study the expressive power as well as the relative succinctness of some of these fragments.

JAAMAS Journal 2010 Journal Article

Guest editorial: special issue on computational social choice

• Edith Elkind
• Jérôme Lang

ECAI Conference 2010 Conference Paper

Learning conditionally lexicographic preference relations

• Richard Booth 0001
• Yann Chevaleyre
• Jérôme Lang
• Jérôme Mengin
• Chattrakul Sombattheera

We consider the problem of learning a user's ordinal preferences on a multiattribute domain, assuming that her preferences are lexicographic. We introduce a general graphical representation called LP-trees which captures various natural classes of such preference relations, depending on whether the importance order between attributes and/or the local preferences on the domain of each attribute is conditional on the values of other attributes. For each class we determine the Vapnik-Chernovenkis dimension, the communication complexity of preference elicitation, and the complexity of identifying a model in the class consistent with a set of user-provided examples.

AAAI Conference 2010 Conference Paper

Possible Winners when New Candidates Are Added: The Case of Scoring Rules

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Jérôme Monnot

In some voting situations, 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. Focusing on scoring rules, we give complexity results for the above possible winner problem.

AIJ Journal 2010 Journal Article

Reasoning under inconsistency: A forgetting-based approach

• Jérôme Lang
• Pierre Marquis

In this paper, a fairly general framework for reasoning from inconsistent propositional bases is defined. Variable forgetting is used as a basic operation for weakening pieces of information so as to restore consistency. The key notion is that of recoveries, which are sets of variables whose forgetting enables restoring consistency. Several criteria for defining preferred recoveries are proposed, depending on whether the focus is laid on the relative relevance of the atoms or the relative entrenchment of the pieces of information (or both). Our framework encompasses several previous approaches as specific cases, including reasoning from preferred consistent subsets, and some forms of information merging. Interestingly, the gain in flexibility and generality offered by our framework does not imply a complexity shift compared to these specific cases.

IJCAI Conference 2009 Conference Paper

• Lirong Xia
• Jérôme Lang

Sequential voting rules and correspondences provide a way for agents to make group decisions when the set of available options has a multi-issue structure. One important question about sequential voting rules (correspondences) is whether they satisfy two crucial criteria, namely neutrality and ef- ficiency. Recently, Benoit and Kornhauser established an important result about seat-by-seat voting rules (which are a special case of sequential voting rules): they proved that if the multi-issue domain satisfies some properties, then the only seat-by-seat rules being either efficient or neutral are dictatorships. However, there are still some cases not covered by their results, including a very important and interesting case—voting correspondences. In this paper, we extend the impossibility theorems by Benoit and Kornhauser to voting correspondences, and obtain a dichotomy theorem on the existence of efficient or neutral sequential (seat-by-seat) voting rules and correspondences. Therefore, the question of whether sequential (seat-by-seat) voting rules (correspondences) can be efficient or neutral is now completely answered.

IJCAI Conference 2009 Conference Paper

• Vincent Conitzer
• Jérôme Lang
• Lirong Xia

Voting on multiple related issues is an important and difficult problem. The key difficulty is that the number of alternatives is exponential in the number of issues, and hence it is infeasible for the agents to rank all the alternatives. A simple approach is to vote on the issues one at a time, in sequence; however, a drawback is that the outcome may depend on the order in which the issues are voted upon and decided, which gives the chairperson some control over the outcome of the election because she can strategically determine the order. While this is undeniably a negative feature of sequential voting, in this paper we temper this judgment by showing that the chairperson’s control problem is, in most cases, computationally hard.

IJCAI Conference 2009 Conference Paper

• Jérôme Lang
• Jérôme Mengin

We address the problem of learning preference relations on multi-attribute (or combinatorial) domains. We do so by making a very simple hypothesis about the dependence structure between attributes that the preference relation enjoys, namely separability (no preferential dependencies between attributes). Given a set of examples consisting of comparisons between alternatives, we want to output a separable CP-net, consisting of local preferences on each of the attributes, that fits the examples. We consider three forms of compatibility between a CP-net and a set of examples, and for each of them we give useful characterizations as well as complexity results.

IJCAI Conference 2009 Conference Paper

• Sylvain Bouveret
• Ulle Endriss
• Jérôme Lang

While there are several languages for representing combinatorial preferences over sets of alternatives, none of these are well-suited to the representation of ordinal preferences over sets of goods (which are typically required to be monotonic). We propose such a language, taking inspiration from previous work on graphical languages for preference representation, specifically CP-nets, and introduce conditional importance networks (CI-nets). A CI-net includes statements of the form “if I have a set A of goods, and I do not have any of the goods from some other set B, then I prefer the set of goods C over the set of goods D. ” We investigate expressivity and complexity issues for CI-nets. Then we show that CI-nets are well-suited to the description of fair division problems.

IJCAI Conference 2009 Conference Paper

• Yann Chevaleyre
• Jérôme Lang
• Nicolas Maudet
• Guillaume Ravilly-Abadie

In many practical contexts where a number of agents have to find a common decision, the votes do not come all together at the same time. In such situations, we may want to preprocess the information given by the subelectorate (consisting of the voters who have expressed their votes) so as to “compile” the known votes for the time when the latecomers have expressed their votes. We study the amount of space necessary for such a compilation, as a function of the voting rule, the number of candidates, and the number of votes already known. We relate our results to existing work, especially on communication complexity.

ECAI Conference 2008 Conference Paper

From Belief Change to Preference Change

• Jérôme Lang
• Leendert W. N. van der Torre

Various tasks need to consider preferences in a dynamic way. We start by discussing several possible meanings of preference change, and then focus on the one we think is the most natural: preferences evolving after some new fact has been learned. We define a family of such preference change operators, parameterized by a revision function on epistemic states and a semantics for interpreting preferences over formulas. We list some natural properties that this kind of preference change should fulfill and give conditions on the revision function and the semantics of preference for each of these properties to hold.

AIJ Journal 2008 Journal Article

On propositional definability

• Jérôme Lang
• Pierre Marquis

In standard propositional logic, logical definability is the ability to derive the truth value of some propositional symbols given a propositional formula and the truth values of some propositional symbols. Although appearing more or less informally in various AI settings, a computation-oriented investigation of the notion is still lacking, and this paper aims at filling the gap. After recalling the two definitions of definability, which are equivalent in standard propositional logic (while based on different intuitions), and defining a number of related notions, we give several characterization results, and many complexity results for definability. We also show close connections with hypothesis discriminability and with reasoning about action and change.

ECAI Conference 2008 Conference Paper

Single-peaked consistency and its complexity

• Bruno Escoffier
• Jérôme Lang
• Meltem Öztürk

A common way of dealing with the paradoxes of preference aggregation consists in restricting the domain of admissible preferences. The most well-known such restriction is single-peakedness. In this paper we focus on the problem of determining whether a given profile is single-peaked with respect to some axis, and on the computation of such an axis. This problem has already been considered in [2]; we give here a more efficient algorithm and address some related issues, such as the number of orders that may be compatible with a given profile, or the communication complexity of preference aggregation under the single-peakedness assumption.

JELIA Conference 2008 Invited Paper

Voting in Combinatorial Domains: What Logic and AI Have to Say

• Jérôme Lang

Abstract This talk is half-way between a survey and a report on ongoing research, most of which is joint work with Vincent Conitzer and Lirong Xia. The first part of the talk owes a lot to two survey papers co-authored with Yann Chevaleyre, Ulle Endriss and Nicolas Maudet [5, 6].

TARK Conference 2007 Conference Paper

Sequential voting rules and multiple elections paradoxes

• Lirong Xia
• Jérôme Lang
• Mingsheng Ying

Multiple election paradoxes arise when voting separately on each issue from a set of related issues results in an obviously undesirable outcome. Several authors have argued that a sufficient condition for avoiding multiple election paradoxes is the assumption that voters have separable preferences. We show that this extremely demanding restriction can be relaxed into the much more reasonable one: there exists a linear order x1 >. .. > xp on the set of issues such that for each voter, every issue xi is preferentially independent of xi+1, .. ., xp given x1, .. ., xi−1. This leads us to define a family of sequential voting rules, defined as the sequential composition of local voting rules. These rules relate to the setting of conditional preference networks (CP-nets) recently developed in the Artificial Intelligence literature. We study in detail how these sequential rules inherit, or do not inherit, the properties of their local components. We focus on the case of multiple referenda, corresponding to multiple elections with binary issues.

ECAI Conference 2006 Conference Paper

Boolean Games Revisited

• Elise Bonzon
• Marie-Christine Lagasquie-Schiex
• Jérôme Lang
• Bruno Zanuttini

Game theory is a widely used formal model for studying strategical interactions between agents. Boolean games [8] are two players, zero-sum static games where players' utility functions are binary and described by a single propositional formula, and the strategies available to a player consist of truth assignments to each of a given set of propositional variables (the variables controlled by the player.) We generalize the framework to n-players games which are not necessarily zero-sum. We give simple characterizations of Nash equilibria and dominated strategies, and investigate the computational complexity of the related problems.

ECAI Conference 2006 Conference Paper

Variable Forgetting in Preference Relations over Propositional Domains

• Philippe Besnard
• Jérôme Lang
• Pierre Marquis

Representing (and reasoning about) preference relations over combinatorial domains is computationally expensive. For many problems involving such preferences, it is relevant to simplify them by projecting them on a subset of variables. We investigate several possible definitions, focusing without loss of generality on propositional (binary) variables.

KER Journal 2005 Journal Article

Multiagent resource allocation

• Yann Chevaleyre
• Paul E. Dunne
• Ulle Endriss
• Jérôme Lang
• Nicolas Maudet
• Juan A. Rodríguez-Aguilar

Resource allocation in multiagent systems is a central research issue in the AgentLink community. The aim of the Technical Forum Group on Multiagent Resource Allocation (TFG-MARA) is to provide a venue for the exchange of ideas in this area and to foster collaboration between different research groups. In this article we report on the first meeting of TFG-MARA, which was held as part of the Second AgentLink III Technical Forum in Ljubljana.

IJCAI Conference 2005 Conference Paper

Reasoning under inconsistency: the forgotten connective

• Sébastien Konieczny
• Jérôme Lang
• Pierre

In many frameworks for reasoning under inconsistency, it is implicitly assumed that the formulae from the belief base are connected using a weak form of conjunction. When it is consistent, a belief base B = {ϕ1, .. ., ϕn}, where the ϕi are propositional formulae, is logically equivalent to the base {ϕ1 ∧. .. ∧ ϕn}. However, when it is not consistent, both bases typically lead to different conclusions. This illustrates the fact that the comma used in base B has to be considered as an additional, genuine connective, and not as a simple conjunction. In this work we define and investigate a propositional framework with such a “comma connective”. We give it a semantics and show how it generalizes several approaches for reasoning from inconsistent beliefs.

IJCAI Conference 2005 Conference Paper

The computational complexity of dominance and consistency in CP-nets

• Judy Goldsmith
• Jérôme Lang
• Miroslaw Truszczynski
• Nic

We investigate the computational complexity of testing dominance and consistency in CP-nets. Up until now, the complexity of dominance has been determined only 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. We show here that both dominance and consistency testing for general CP-nets are PSPACE-complete. The reductions used in the proofs are from STRIPS planning, and thus establish strong connections between both areas.

ICAPS Conference 2004 Conference Paper

A Preference-Based Interpretation of Other Agents' Actions

• Jérôme Lang

What can we infer about the beliefs, the goals and the intended next actions of an agent by observing him acting? We start from the same intuitive principle as in (Brafman and Tennenholtz 1997), namely, that an agent normally follows some optimal plan (with respect to some preference relation) and chooses actions that are part of this plan. This principle allows us to infer beliefs about the agent’s plausible next actions, about his goals and about his initial and current beliefs. We give several possible definitions and study their respective meanings, especially with respect to the assumptions about the acting agent’s rationality.

ECAI Conference 2004 Conference Paper

From Knowledge-Based Programs to Graded Belief-Based Programs Part I: On-Line Reasoning

• Noël Laverny
• Jérôme Lang

TARK Conference 2003 Conference Paper

How many candidates are needed to make elections hard to manipulate?

• Vincent Conitzer
• Jérôme Lang
• Tuomas Sandholm

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 [4], 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.

AIJ Journal 2002 Journal Article

Conditional independence in propositional logic

• Jérôme Lang
• Paolo Liberatore
• Pierre Marquis

Independence—the study of what is relevant to a given problem of reasoning—is an important AI topic. In this paper, we investigate several notions of conditional independence in propositional logic: Darwiche and Pearl's conditional independence, and some more restricted forms of it. Many characterizations and properties of these independence relations are provided. We show them related to many other notions of independence pointed out so far in the literature (mainly formula-variable independence, irrelevance and novelty under various forms, separability, interactivity). We identify the computational complexity of conditional independence and of all these related independence relations.

UAI Conference 2001 Conference Paper

Plausible reasoning from spatial observations

• Jérôme Lang
• Philippe Muller

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.

ECAI Conference 2000 Conference Paper

A modal logic for epistemic tests

• Andreas Herzig
• Jérôme Lang
• Thomas Polacsek

AAAI Conference 1998 Conference Paper

Two Forms of Dependence in Propositional Logic: Controllability and Definability

• Jérôme Lang

We investigate two forms of dependence between variables and/or formulas within a propositional knowledge base: controllability (a set of variables X controls a formula, if there is a way to fix the truth value of the variables in X in order to achieve, to have a prescribed truth value) and definability (X defines a variable y if every truth assignment of the variables in X enables us finding out the truth value of y). Several characterization results are pointed out, complexity issues are analyzed, and some applications of both notions, including decision under incomplete knowledge and/or partial observability, and hypothesis discrimination, are sketched.

ECAI Conference 1996 Conference Paper

Conditional Desires and Utilities: an Alternative Logical Approach to Qualitative Decision Theory

• Jérôme Lang

UAI Conference 1995 Conference Paper

A constraint satisfaction framework for decision under uncertainty

• Hélène Fargier
• Jérôme Lang
• Roger Martin-Clouaire
• Thomas Schiex

AIJ Journal 1994 Journal Article

From ordering-based nonmonotonic reasoning to conditional logics

• Luis Fariñas del Cerro
• Andreas Herzig
• Jérôme Lang

As Gärdenfors and Makinson have recently shown, a nonmonotonic inference relation can be generated from a total pre-ordering on the set of formulas, or equivalently from an uncertainty valuation. We build here on these results; we include the pre-ordering in the language by introducing a conditional operator, and we extend the generation of a nonmonotonic inference relation by allowing the use of incompletely specified pre-orderings. This allows effective procedures for computing nonmonotonic inferences by translating nonmonotonic reasoning into deduction in a conditional logic.

UAI Conference 1994 Conference Paper

Penalty Logic and its Link with Dempster-Shafer Theory

• Florence Dupin de Saint-Cyr
• Jérôme Lang
• Thomas Schiex

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.

UAI Conference 1994 Conference Paper

Possibility and Necessity Functions over Non-Classical Logics

• Philippe Besnard
• Jérôme Lang

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.

UAI Conference 1994 Conference Paper

Syntax-based Default Reasoning as Probabilistic Model-based Diagnosis

• Jérôme Lang

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.

UAI Conference 1993 Conference Paper

Possibilistic decreasing persistence

• Dimiter Driankov
• Jérôme Lang

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.

ECAI Conference 1992 Conference Paper

Dealing with Multi-Source Information in Possibilistic Logic

• Didier Dubois
• Jérôme Lang
• Henri Prade

ECAI Conference 1992 Conference Paper

From Ordering Based Nonmonotonic Reasoning to Conditional Logics

• Luis Fariñas del Cerro
• Andreas Herzig
• Jérôme Lang

UAI Conference 1991 Conference Paper

A Logic of Graded Possibility and Certainty Coping with Partial Inconsistency

• Jérôme Lang
• Didier Dubois
• Henri Prade

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.