ocirc; me Lang

IJCAI Conference 2016 Conference Paper

Computing Pareto Optimal Committees

• Haris Aziz
• ocirc; me Lang
• J
• eacute; r
• ocirc; me Monnot

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 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 four prominent extensions (responsive, leximax, 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 three of the set extensions, we present linear-time, Pareto optimal and strategyproof algorithms that work even for weak preferences.

IJCAI Conference 2016 Conference Paper

Conditional and Sequential Approval Voting on Combinatorial Domains

• Nathana
• euml; l Barrot
• J
• eacute; r
• ocirc; me Lang

Several methods exist for making collective decisions on a set of variables when voters possibly have preferential dependencies. None is based on approval voting. We define a family of rules for approval-based voting on combinatorial domains, where voters cast conditional approval ballots, allowing them to approve values of a variable conditionally on the values of other variables. We study three such rules. The first two generalize simple multiwinner approval voting and minimax approval voting. The third one is an approval-based version of sequential voting on combinatorial domains. We study some properties of these rules, and compare their outcomes.

IJCAI Conference 2016 Conference Paper

How Hard Is It for a Party to Nominate an Election Winner?

• Piotr Faliszewski
• Laurent Gourv
• egrave; s
• ocirc; me Lang
• Julien Lesca
• J
• eacute; r
• ocirc; me Monnot

We consider a Plurality-voting scenario, where the candidates are split between parties, and each party nominates exactly one candidate for the final election. We study the computational complexity of deciding if there is a set of nominees such that a candidate from a given party wins in the final election. In our second problem, the goal is to decide if a candidate from a given party always wins, irrespective who is nominated. We show that these problems are computationally hard, but are polynomial-time solvable for restricted settings.

IJCAI Conference 2015 Conference Paper

Probabilistic Knowledge-Based Programs

• J
• eacute; r
• ocirc; me Lang
• Bruno Zanuttini

We introduce Probabilistic Knowledge-Based Programs (PKBPs), a new, compact representation of policies for factored partially observable Markov decision processes. PKBPs use branching conditions such as if the probability of ϕ is larger than p, and many more. While similar in spirit to valuebased policies, PKBPs leverage the factored representation for more compactness. They also cope with more general goals than standard state-based rewards, such as pure information-gathering goals. Compactness comes at the price of reactivity, since evaluating branching conditions on-line is not polynomial in general. In this sense, PKBPs are complementary to other representations. Our intended application is as a tool for experts to specify policies in a natural, compact language, then have them verified automatically. We study succinctness and the complexity of verification for PKBPs.

AAMAS Conference 2012 Conference Paper

Campaigns for Lazy Voters: Truncated Ballots

• Dorothea Baumeister
• Piotr Faliszewski
• eacute; r
• ocirc; me Lang
• J
• ouml; rg Rothe

We study elections in which voters may submit partial ballots consisting of truncated lists: each voter ranks some of her top candidates (and possibly some of her bottom candidates) and is indifferent among the remaining ones. Holding elections with such votes requires adapting classical voting rules (which expect complete rankings as input) and these adaptations create various opportunities for candidates who want to increase their chances of winning. We provide complexity results regarding planning various kinds of campaign in such settings, and we study the complexity of the possible winner problem for the case of truncated votes.

AAMAS Conference 2012 Conference Paper

Possible and Necessary Winners of Partial Tournaments

• Haris Aziz
• Markus Brill
• Felix Fischer
• Paul Harrenstein
• J
• eacute; r
• ocirc; me Lang
• Hans Georg Seedig

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts---including the uncovered set, Borda, ranked pairs, and maximin---and show that for most of them possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.

AAMAS Conference 2012 Conference Paper

Strategic voting and the logic of knowledge

• Hans van Ditmarsch
• J
• eacute; r
• ocirc; me Lang
• Abdallah Saffidine

IJCAI Conference 2011 Conference Paper

A General Elicitation-Free Protocol for Allocating Indivisible Goods

• Sylvain Bouveret
• J
• eacute; r
• ocirc; me Lang

We consider the following sequential allocation process. A benevolent central authority has to allocate a set of indivisible goods to a set of agents whose preferences it is totally ignorant of. We consider the process of allocating objects one after the other by designating an agent and asking her to pick one of the objects among those that remain. The problem consists in choosing the "best" sequence of agents, according to some optimality criterion. We assume that agents have additive preferences over objects. The choice of an optimality criterion depends on three parameters: how utilities of objects are related to their ranking in an agent's preference relation; how the preferences of different agents are correlated; and how social welfare is defined from the agents' utilities. We address the computation of a sequence maximizing expected social welfare under several assumptions. We also address strategical issues.

IJCAI Conference 2011 Conference Paper

Choosing Collectively Optimal Sets of Alternatives Based on the Condorcet Criterion

• Edith Elkind
• J
• eacute; r
• ocirc; me Lang
• Abdallah Saffidine

In elections, an alternative is said to be a Condorcet winner if it is preferred to any other alternative by a majority of voters. While this is a very attractive solution concept, many elections do not have a Condorcet winner. In this paper, we propose a setvalued relaxation of this concept, which we call a Condorcet winning set: such sets consist of alternatives that collectively dominate any other alternative. We also consider a more general version of this concept, where instead of domination by a majority of voters we require domination by a given fraction theta of voters; we refer to this concept as theta-winning set. We explore social choice-theoretic and algorithmic aspects of these solution concepts, both theoretically and empirically.

AAMAS Conference 2011 Conference Paper

Designing Incentives for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

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 the agents within a society, so that agents are rationally incentivised to choose some socially desirable equilibrium that would not otherwise be chosen, or incentivised to rule out some socially 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 socially desirable outcome), and then discuss possible desirable properties of taxation schemes.

IJCAI Conference 2011 Conference Paper

Hypercubewise Preference Aggregation in Multi-Issue Domains

• Vincent Conitzer
• J
• eacute; r
• ocirc; me Lang
• Lirong Xia

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

IJCAI Conference 2011 Conference Paper

Incentive Engineering for Boolean Games

• Ulle Endriss
• Sarit Kraus
• J
• eacute; r
• ocirc; me Lang
• Michael Wooldridge

We investigate the problem of influencing the preferences of players within a Boolean game so that, if all players act rationally, certain desirable outcomes will result. The way in which we influence preferences is by overlaying games with taxation schemes. In a Boolean game, each player has unique control of a set of Boolean variables, and the choices available to the player correspond to the possible assignments that may be made to these variables. Each player also has a goal, represented by a Boolean formula, that they desire to see satisfied. Whether or not a player's goal is satisfied will depend both on their own choices and on the choices of others, which gives Boolean games their strategic charac- ter. We extend this basic framework by introducing an external principal who is able to levy a taxation scheme on the game, which imposes a cost on every possible action that a player can choose. By designing a taxation scheme appropriately, it is possible to perturb the preferences of the players, so that they are incentivised to choose some equilibrium that would not otherwise be chosen. After motivating and formally presenting our model, we explore some issues surrounding it, including the complexity of finding a taxation scheme that implements some socially desirable outcome, and then discuss desirable properties of taxation schemes.

AAMAS Conference 2011 Conference Paper

Possible Winners When New Alternatives Join: New Results Coming Up!

• Lirong Xia
• ocirc; me Lang
• J
• eacute; r
• ocirc; me Monnot

In a voting system, sometimes multiple new alternatives will join the election after the voters' preferences over the initial alternatives have been revealed. Computing whether a given alternative can be a co-winner when multiple new alternatives join the election is called the possible co-winner with new alternatives (PcWNA) problem and was introduced by (Chevaleyre et al. , 2010). In this paper, we show that the PcWNA problems are NP-complete for the Bucklin, Copeland _0, and maximin (a. k. a. Simpson) rule, even when the number of new alternatives is no more than a constant. We also show that the PcWNA problem can be solved in polynomial time for plurality with runoff. For the approval rule, we examine three different ways to extend a linear order with new alternatives, and characterize the computational complexity of the PcWNA problem for each of them.

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang

Although many papers about belief update have been written, its precise scope still remains unclear. In this paper we aim at identifying this scope, and we show that belief update is a specific case of feedback-free action progression. This strong connection with the field of reasoning about action leads us to reconsider belief update and investigate new issues, especially reverse update, which is to regression what update is to progression.

IJCAI Conference 2007 Conference Paper

• James P. Delgrande
• J
• eacute; r
• ocirc; me Lang
• Torsten Schaub

A general framework for minimisation-based belief change is presented. A problem instance is made up of an undirected graph, where a formula is associated with each vertex. For example, vertices may represent spatial locations, points in time, or some other notion of locality. Information is shared between vertices via a process of minimisation over the graph. We give equivalent semantic and syntactic characterisations of this minimisation. We also show that this approach is general enough to capture existing minimisation-based approaches to belief merging, belief revision, and (temporal) extrapolation operators. While we focus on a set-theoretic notion of minimisation, we also consider other approaches, such as cardinality-based and priority-based minimisation.

IJCAI Conference 2007 Conference Paper

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

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

IJCAI Conference 2007 Conference Paper

• J
• eacute; r
• ocirc; me Lang

In many real-world collective decision problems, the set of alternatives is a Cartesian product of finite value domains for each of a given set of variables. The prohibitive size of such domains makes it practically impossible to represent preference relations explicitly. Now, AI has been developing languages for representing preferences on such domains in a succinct way, exploiting structural properties such as conditional preferential independence. Here we reconsider voting and aggregation rules in the case where voters' preferences have a common preferential independence structure, and address the decompossition a voting rule or an aggregation function following a linear order over variables.

AAMAS Conference 2005 Conference Paper

Allocation Of Indivisible Goods: A General Model And Some Complexity Results

• Sylvain Bouveret
• H
• eacute; l
• egrave; ne Fargier
• J
• eacute; r
• ocirc; me Lang
• Michel Lema

AAMAS Conference 2005 Conference Paper

Negotiating over Small Bundles of Resources

• Yann Chevaleyre
• Ulle Endriss
• J
• eacute; r
• ocirc; me Lang
• Nicolas Maudet