Laurent Perrussel

AAAI Conference 2026 Conference Paper

Formal Verification of Diffusion Auctions

• Rustam Galimullin
• Munyque Mittelmann
• Laurent Perrussel

In diffusion auctions, sellers can leverage an underlying social network to broaden participation, thereby increasing their potential revenue. Specifically, sellers can incentivise participants in their auction to diffuse information about the auction through the network. While numerous variants of such auctions have been recently studied in the literature, the formal verification and strategic reasoning perspectives have not been investigated yet. Our contribution is threefold. First, we introduce a logical formalism that captures the dynamics of diffusion and its strategic dimension. Second, for such a logic, we provide model-checking procedures that allow one to verify properties like the Nash equilibrium, and that pave the way towards checking the existence of sellers' strategies. Third, we establish computational complexity results for the presented algorithms.

AIJ Journal 2025 Journal Article

Formal verification and synthesis of mechanisms for social choice

• Munyque Mittelmann
• Bastien Maubert
• Aniello Murano
• Laurent Perrussel

Mechanism Design (MD) aims at defining resources allocation protocols that satisfy a predefined set of properties, and Auction Mechanisms are of foremost importance. Core properties of mechanisms, such as strategy-proofness or budget balance, involve: (i) complex strategic concepts such as Nash equilibria, (ii) quantitative aspects such as utilities, and often (iii) imperfect information, with agents' private valuations. We demonstrate that Strategy Logic provides a formal framework fit to model mechanisms and express such properties, and we show that it can be used either to automatically check that a given mechanism satisfies some property (verification), or automatically produce a mechanism that does (synthesis). To do so, we consider a quantitative and variant of Strategy Logic. We first show how to express the implementation of social choice functions. Second, we show how fundamental mechanism properties can be expressed as logical formulas, and thus evaluated by model checking. We then prove that model checking for this particular variant of Strategy Logic can be done in polynomial space. Next, we show how MD can be rephrased as a synthesis problem, where mechanisms are automatically synthesized from a partial or complete logical specification. We solve the automated synthesis of mechanisms in two cases: when the number of actions is bounded, and when agents play in turns. Finally, we provide examples of auction design based for each of these two cases. The benefit of our approach in relation to classical MD is to provide a general framework for addressing a large spectrum of MD problems, which is not tailored to a particular setting or problem.

IJCAI Conference 2023 Conference Paper

Discounting in Strategy Logic

• Munyque Mittelmann
• Aniello Murano
• Laurent Perrussel

Discounting is an important dimension in multi-agent systems as long as we want to reason about strategies and time. It is a key aspect in economics as it captures the intuition that the far-away future is not as important as the near future. Traditional verification techniques allow to check whether there is a winning strategy for a group of agents but they do not take into account the fact that satisfying a goal sooner is different from satisfying it after a long wait. In this paper, we augment Strategy Logic with future discounting over a set of discounted functions D, denoted SL[D]. We consider “until” operators with discounting functions: the satisfaction value of a specification in SL[D] is a value in [0, 1], where the longer it takes to fulfill requirements, the smaller the satisfaction value is. We motivate our approach with classical examples from Game Theory and study the complexity of model-checking SL[D]-formulas.

AAAI Conference 2023 Conference Paper

Formal Verification of Bayesian Mechanisms

• Munyque Mittelmann
• Bastien Maubert
• Aniello Murano
• Laurent Perrussel

In this paper, for the first time, we study the formal verification of Bayesian mechanisms through strategic reasoning. We rely on the framework of Probabilistic Strategy Logic (PSL), which is well-suited for representing and verifying multi-agent systems with incomplete information. We take advantage of the recent results on the decidability of PSL model checking under memoryless strategies, and reduce the problem of formally verifying Bayesian mechanisms to PSL model checking. We show how to encode Bayesian-Nash equilibrium and economical properties, and illustrate our approach with different kinds of mechanisms.

AAMAS Conference 2023 Conference Paper

Representing and Reasoning about Auctions

• Munyque Mittelmann
• Laurent Perrussel
• Sylvain Bouveret

In this paper, we propose a framework for representing and reasoning about auction-based protocols. Such a framework is of interest for building digital marketplaces based on auctions and should fulfill two requirements: (i) it should enable bidders to express their preferences over combinations of items and (ii) it should allow the mechanism designer to describe the rules governing the market, namely the legality of bids, the allocative choice, and the payment rule. To do so, we define a logical language in the spirit of the Game Description Language, namely Auction Description Language with a set of functions FB (ADL[FB]). ADL[FB] is expressive enough to represent different kinds of protocols and enables reasoning about auction properties, including playability, termination, and budget-balance. We also study the complexity of model-checking ADL[FB].

IJCAI Conference 2022 Conference Paper

Automated Synthesis of Mechanisms

• Munyque Mittelmann
• Bastien Maubert
• Aniello Murano
• Laurent Perrussel

Mechanism Design aims to design a game so that a desirable outcome is reached regardless of agents' self-interests. In this paper, we show how this problem can be rephrased as a synthesis problem, where mechanisms are automatically synthesized from a partial or complete specification in a high-level logical language. We show that Quantitative Strategy Logic is a perfect candidate for specifying mechanisms as it can express complex strategic and quantitative properties. We solve automated mechanism design in two cases: when the number of actions is bounded, and when agents play in turn.

AAMAS Conference 2022 Conference Paper

Reasoning about Human-Friendly Strategies in Repeated Keyword Auctions

• Francesco Belardinelli
• Wojtek Jamroga
• Vadim Malvone
• Munyque Mittelmann
• Aniello Murano
• Laurent Perrussel

In online advertising, search engines sell ad placements for keywords continuously through auctions. This problem can be seen as an infinitely repeated game since the auction is executed whenever a user performs a query with the keyword. As advertisers may frequently change their bids, the game will have a large set of equilibria with potentially complex strategies. In this paper, we propose the use of natural strategies for reasoning in such setting as they are processable by artificial agents with limited memory and/or computational power as well as understandable by human users. To reach this goal, we introduce a quantitative version of Strategy Logic with natural strategies in the setting of imperfect information. In a first step, we show how to model strategies for repeated keyword auctions and take advantage of the model for proving properties evaluating this game. In a second step, we study the logic in relation to the distinguishing power, expressivity, and model-checking complexity for strategies with and without recall.

JAAMAS Journal 2022 Journal Article

Representing and reasoning about auctions

• Munyque Mittelmann
• Sylvain Bouveret
• Laurent Perrussel

Abstract The goal of this paper is to propose a framework for representing and reasoning about the rules of auction-based protocols. Such a framework is of interest for building digital marketplaces based on this type of mechanism. Hence the framework should fulfill two requirements: (i) it should enable bidders to express their preferences over combinations of items and (ii) it should allow the mechanism designer to describe the rules governing the market, namely the legality of bids, the allocative choice, and the payment rule. To do so, we define a logical language in the spirit of the Game Description Language, namely Auction Description Language with a set of functions \(\mathcal {F}_{\mathcal {B}}\) ( ADL \([\mathcal {F}_{\mathcal {B}}]\) ). ADL \([\mathcal {F}_{\mathcal {B}}]\) is the first language for describing auctions in a logical framework. With our approach, each stage in a protocol is seen as an independent direct revelation mechanism. Our contribution is three-fold: first, we illustrate the general dimension by representing different kinds of protocols. Second, we show how this machine-processable language enables reasoning about auction properties, including playability, termination, and classical conditions from mechanism design (e. g. , budget-balance and individual rationality). Finally, we develop a model-checking algorithm for ADL \([\mathcal {F}_{\mathcal {B}}]\), with complexity in PTIME when the functions in \(\mathcal {F}_{\mathcal {B}}\) can be computed in polynomial time.

LAMAS&SR Workshop 2022 Workshop Paper

Strategic Reasoning in Automated Mechanism Design

• Bastien Maubert
• Munyque Mittelmann
• Aniello Murano
• Laurent Perrussel

AAMAS Conference 2021 Conference Paper

A General Framework for the Logical Representation of Combinatorial Exchange Protocols

• Munyque Mittelmann
• Sylvain Bouveret
• Laurent Perrussel

The goal of this work is to propose a framework for representing and reasoning about the rules governing a combinatorial exchange. Such a framework is at first interest as long as we want to build up digital marketplaces based on auction, a widely used mechanism for automated transactions. Hence the framework should fulfill two requirements: (i) it should enable bidders to express their bids on combinations of goods and (ii) it should allow describing the rules governing some market, namely the legal bids, the allocation and payment rules. To do so, we define a logical language in the spirit of the Game Description Language: the Combinatorial Exchange Description Language is the first language for describing combinatorial exchange in a logical framework. The contribution is two-fold: first, we illustrate the general dimension by representing different kinds of protocols, and second, we show how to reason about auction properties in this machine-processable language.

AIJ Journal 2021 Journal Article

Epistemic GDL: A logic for representing and reasoning about imperfect information games

• Guifei Jiang
• Dongmo Zhang
• Laurent Perrussel
• Heng Zhang

This paper proposes a logical framework for representing and reasoning about imperfect information games. We first extend Game Description Language (GDL) with the standard epistemic operators and provide it with a semantics based on the epistemic state transition model. We then demonstrate how to use the language to represent the rules of an imperfect information game and formalize common game properties as well as epistemic properties. We also show how to use the framework to reason about players' own and each others' knowledge during game playing. Furthermore, we prove that the model-checking problem of the framework is in Δ 2 P, even though its lower bound is Θ 2 P. These results indicate that the framework makes a good balance between expressive power and computational efficiency. Finally we provide a sound and complete axiomatic system for this logic. With action, temporal and epistemic operators, the completeness proof requires a novel combination of techniques used for completeness of dynamic logic and epistemic temporal logics. The proof theory provides a feasible tool to analyze properties of a family of games.

LAMAS&SR Workshop 2021 Workshop Paper

Epistemic Reasoning about Rationality and Bids in Auctions

• Munyque Mittelmann
• Andreas Herzig
• Laurent Perrussel

The goal of this work is to investigate strategic reasoning in the context of auctions. More precisely, we establish an explicit link between the agents’ choice of bidding actions and bounded rationality. To do so, we extend the Auction Description Language with an epistemic operator and a choice operator and use it to represent a classical auction where agents have imperfect information about other bidders’ valuations. We formalize bounded rationality concepts in iterative protocols and show how to use them to reason about the players’ actions. Finally, we provide a model checking algorithm.

JELIA Conference 2021 Conference Paper

Epistemic Reasoning About Rationality and Bids in Auctions

• Munyque Mittelmann
• Andreas Herzig
• Laurent Perrussel

Abstract In this paper, we investigate strategic reasoning in the context of auctions. More precisely, we establish an explicit link between bidding actions and bounded rationality. To do so, we extend the Auction Description Language with an epistemic operator and an action choice operator and use it to represent a classical auction where agents have imperfect information about other agents’ valuations. We formalize bounded rationality concepts in iterative protocols and show how to use them to reason about the players’ actions. Finally, we provide a model checking algorithm.

KR Conference 2021 Conference Paper

Strategic Reasoning in Automated Mechanism Design

• Bastien Maubert
• Munyque Mittelmann
• Aniello Murano
• Laurent Perrussel

Mechanism Design aims at defining mechanisms that satisfy a predefined set of properties, and Auction Mechanisms are of foremost importance. Core properties of mechanisms, such as strategy-proofness or budget-balance, involve: (i) complex strategic concepts such as Nash equilibria, (ii) quantitative aspects such as utilities, and often (iii) imperfect information, with agents’ private valuations. We demonstrate that Strategy Logic provides a formal framework fit to model mechanisms, express such properties, and verify them. To do so, we consider a quantitative and epistemic variant of Strategy Logic. We first show how to express the implementation of social choice functions. Second, we show how fundamental mechanism properties can be expressed as logical formulas, and thus evaluated by model checking. Finally, we prove that model checking for this particular variant of Strategy Logic can be done in polynomial space.

ECAI Conference 2020 Conference Paper

Auction Description Language (ADL): General Framework for Representing Auction-Based Markets

• Munyque Mittelmann
• Laurent Perrussel

The goal of this paper is to propose a language for representing and reasoning about the rules governing an auction-based market. Such language is at first interest as long as we want to build up digital market places based on auction, a widely used framework for automated transactions. Auctions may differ in several aspects: single or double-side, ascending or descending, single or multi-unit, open cry or sealed-bid, and so on. This variety prevents an agent to easily switch between different (auction-based) markets. The first requirement for building such agents is to have a general language for describing auction-based markets. Second, this language should also allow the reasoning about the key issues of a specific market, namely the allocation and payment rules. To do so, we define a language in the spirit of the Game Description Language (GDL): the Auction Description Language (ADL) is the first language for describing auctions in a logical framework. In this paper, we illustrate this general dimension by representing two different types of well-known auctions: an English Auction and a Multi-Unit Vickrey Auction. We show the benefit of ADL by deriving properties about these two auction protocols. It also enables us to show in an explicit way what should be assumed about the behavior of a rational bidder.

AAAI Conference 2020 Conference Paper

Refining HTN Methods via Task Insertion with Preferences

• Zhanhao Xiao
• Hai Wan
• Hankui Hankz Zhuo
• Andreas Herzig
• Laurent Perrussel
• Peilin Chen

Hierarchical Task Network (HTN) planning is showing its power in real-world planning. Although domain experts have partial hierarchical domain knowledge, it is time-consuming to specify all HTN methods, leaving them incomplete. On the other hand, traditional HTN learning approaches focus only on declarative goals, omitting the hierarchical domain knowledge. In this paper, we propose a novel learning framework to refine HTN methods via task insertion with completely preserving the original methods. As it is difficult to identify incomplete methods without designating declarative goals for compound tasks, we introduce the notion of prioritized preference to capture the incompleteness possibility of methods. Specifically, the framework first computes the preferred completion profile w. r. t. the prioritized preference to refine the incomplete methods. Then it finds the minimal set of refined methods via a method substitution operation. Experimental analysis demonstrates that our approach is effective, especially in solving new HTN planning instances.

AAMAS Conference 2019 Conference Paper

Multi-Issue Opinion Diffusion under Constraints

• Sirin Botan
• Umberto Grandi
• Laurent Perrussel

Most existing models of opinion diffusion on networks neglect the existence of logical constraints that might correlate individual opinions on multiple issues. In this paper we study the diffusion of constrained opinions on a social network as an iterated process of aggregating neighbouring opinions. Individual views are modelled as vectors of yes/no answers to a number of propositions subject to integrity constraints, and each individual updates her opinion by looking at the aggregated opinion of her influencers. To overcome the problem of updating towards inconsistent influencing opinions, we propose a model based on individual updates on subsets of the issues of limited size called propositionwise updates. By adapting notions from the theory of boolean functions, we identify classes of integrity constraints on which propositionwise updates decrease the influence gap between nodes of the network and their influencers caused by the presence of an integrity constraint. Furthermore, we provide a detailed study of the termination of the proposed diffusion processes.

IJCAI Conference 2017 Conference Paper

Hierarchical Task Network Planning with Task Insertion and State Constraints

• Zhanhao Xiao
• Andreas Herzig
• Laurent Perrussel
• Hai Wan
• Xiaoheng Su

We extend hierarchical task network planning with task insertion (TIHTN) by introducing state constraints, called TIHTNS. We show that just as for TIHTN planning, all solutions of the TIHTNS planning problem can be obtained by acyclic decomposition and task insertion, entailing that its plan-existence problem is decidable without any restriction on decomposition methods. We also prove that the extension by state constraints does not increase the complexity of the plan-existence problem, which stays 2-NEXPTIME-complete, based on an acyclic progression operator. In addition, we show that TIHTNS planning covers not only the original TIHTN planning but also hierarchy-relaxed hierarchical goal network planning.

LORI Conference 2017 Conference Paper

On Axiomatization of Epistemic GDL

• Guifei Jiang
• Laurent Perrussel
• Dongmo Zhang

Abstract The Game Description Language (GDL) has been introduced as an official language for specifying games in the AAAI General Game Playing Competition since 2005. It was originally designed as a declarative language for representing rules of arbitrary games with perfect information. More recently, an epistemic extension of GDL, called EGDL, has been proposed for representing and reasoning about imperfect information games. In this paper, we develop an axiomatic system for a variant of EGDL and prove its soundness and completeness with respect to the semantics based on the epistemic state transition model. With a combination of action symbols, temporal modalities and epistemic operators, the completeness proof requires novel combinations of techniques used for completeness of propositional dynamic logic and epistemic temporal logic. We demonstrate how to use the proof theory for inferring game properties from game rules.

TARK Conference 2017 Conference Paper

Relaxing Exclusive Control in Boolean Games

• Francesco Belardinelli
• Umberto Grandi
• Andreas Herzig
• Dominique Longin
• Emiliano Lorini
• Arianna Novaro
• Laurent Perrussel

In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they ac- count for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC.

AAMAS Conference 2017 Conference Paper

Strategic Disclosure of Opinions on a Social Network

• Umberto Grandi
• Emiliano Lorini
• Arianna Novaro
• Laurent Perrussel

This paper starts from a simple model of strategic reasoning in situations of social influence. Agents express binary views on a set of propositions, and iteratively update their views by taking into account the expressed opinion of their influencers. We empower agents with the ability to disclose or hide their opinions, in order to attain a predetermined goal. We study classical game-theoretic solution concepts in the resulting games, observing a non-trivial interplay between the individual goals and the structure of the underlying network. By making use of different logics for strategic reasoning, we show how apparently simple problems in strategic opinion diffusion require a complex logical machinery to be properly formalized and handled.

IJCAI Conference 2016 Conference Paper

Epistemic GDL: A Logic for Representing and Reasoning about Imperfect Information Games

• Guifei Jiang
• Dongmo Zhang
• Laurent Perrussel
• Heng Zhang

This paper proposes a logical framework for representing and reasoning about imperfect information games. We first extend the game description language (GDL) with the standard epistemic operators and provide it with a semantics based on the epistemic state transition model. We then demonstrate how to use the language to represent the rules of an imperfect information game and formalize its epistemic properties. We also show how to use the framework to reason about player's own as well as other players' knowledge during game playing. Finally we prove that the model-checking problem of the framework is in Δ 2 p, which is the lowest among the existing similar frameworks, even though its lower bound is Θ 2 p. These results indicate that the framework makes a good balance between expressive power and computational efficiency.

JELIA Conference 2016 Conference Paper

On Hierarchical Task Networks

• Andreas Herzig
• Laurent Perrussel
• Zhanhao Xiao

Abstract In planning based on hierarchical task networks (HTN), plans are generated by refining high-level actions (‘compound tasks’) into lower-level actions, until primitive actions are obtained that can be sent to execution. While a primitive action is defined by its precondition and effects, a high-level action is defined by zero, one or several methods: sets of (high-level or primitive) actions decomposing it together with a constraint. We give a semantics of HTNs in terms of dynamic logic with program inclusion. We propose postulates guaranteeing soundness and completeness of action refinement. We also show that hybrid planning can be analysed in the same dynamic logic framework.

JELIA Conference 2016 Conference Paper

Refinement of Intentions

• Andreas Herzig
• Laurent Perrussel
• Zhanhao Xiao
• Dongmo Zhang

Abstract According to Bratman, future-directed intentions are high-level plans. We view such plans as high-level actions that can typically not be executed directly: they have to be progressively refined until executable basic actions are obtained. Higher- and lower-level actions are linked by the means-end relation, alias instrumentality relation. In this paper we extend Shoham’s database perspective of Bratman’s theory by the notions of refinement and instrumentality.

AAMAS Conference 2016 Conference Paper

Strategic Disclosure of Opinions on a Social Network (Extended Abstract)

• Umberto Grandi
• Emiliano Lorini
• Laurent Perrussel

KR Conference 2014 Conference Paper

A dynamic logic framework for abstract argumentation

• Sylvie Doutre
• Andreas Herzig
• Laurent Perrussel

the semantics. This is done in an extension of the language of attack variables by variables representing argument acceptance. Based on such a logical representation, several authors have recently investigated the dynamics of the AF, such as (Baumann 2012; Booth et al. 2013; Bisquert et al. 2013; Coste-Marquis et al. 2013). They start by distinguishing several kinds of modification of the AF, such as the addition or the removal of attacks, or the enforcement of the acceptability of an argument a (e. g. such that a is part of at least one extension). All these papers build on previous work in belief change, either referring to AGM theory (Alchourrón, Gärdenfors, and Makinson 1985), such as (Booth et al. 2013; Coste-Marquis et al. 2013), or to KM theory (Katsuno and Mendelzon 1992), such as (Bisquert et al. 2013). They express the modification as a logical formula describing some goal, i. e., a property that AF should satisfy: the task is to revise/update AF so that this formula is true. The above papers do not provide a single framework encompassing at the same time AF, the logical definition of the enforcement constraint and the change operations: there is usually one language for representing AF and another language for representing constraints, plus some definitions in the metalanguage connecting them. This has motivated us to provide a general, unified logical framework for the representation and the update of argumentation frameworks. We make use of a flexible yet simple logic: Dynamic Logic of Propositional Assignments, abbreviated DL-PA (Balbiani, Herzig, and Troquard 2013). DL-PA is a simple instantiation of Propositional Dynamic Logic PDL (Harel 1984; Harel, Kozen, and Tiuryn 2000) whose atomic programs are assignments of propositional variables to either true or false. Complex programs are built then from atomic programs by the standard PDL program operators of sequential composition, nondeterministic composition, and test. We here moreover add a less frequently considered PDL program operator, namely the converse operator. The language of DL-PA has formulas of the form hπiϕ and [π]ϕ, where π is a program and ϕ is a formula. The former expresses that ϕ is true after some possible execution of π, and the latter expresses that ϕ is true after every possible execution of π. It is shown in (Balbiani, Herzig, and Troquard 2013) that every DL-PA formula can be reduced to an equivalent propositional formula. The reduction extends to the converse operator in a straight- We provide a logical analysis of abstract argumentation frameworks and their dynamics. Following previous work, we express attack relation and argument status by means of propositional variables and define acceptability criteria by formulas of propositional logic. We here study the dynamics of argumentation frameworks in terms of basic operations on these propositional variables, viz. change of their truth values. We describe these operations in a uniform way within a well-known variant of Propositional Dynamic Logic PDL: the Dynamic Logic of Propositional Assignments, DL-PA. The atomic programs of DL-PA are assignments of propositional variables to truth values, and complex programs can be built by means of the connectives of sequential and nondeterministic composition and test. We start by showing that in DL-PA, the construction of extensions can be performed by a DL-PA program that is parametrized by the definition of acceptance. We then mainly focus on how the acceptance of one or more arguments can be enforced and show that this can be achieved by changing the truth values of the propositional variables describing the attack relation in a minimal way.

ECAI Conference 2014 Conference Paper

Trust-based belief change

• Emiliano Lorini
• Guifei Jiang
• Laurent Perrussel

We propose a modal logic that supports reasoning about trust-based belief change. The term trust-based belief change refers to belief change that depends on the degree of trust the receiver has in the source of information.

ECAI Conference 2012 Conference Paper

Multi-unit Double Auction under Group Buying

• Dengji Zhao
• Dongmo Zhang
• Laurent Perrussel

Group buying is a business model in which a number of buyers join together to make an order of a product in a certain quantity in order to gain a desirable discounted price. Such a business model has recently received significant attention from researchers in economics and computer science, mostly due to its successful application in online businesses, such as Groupon. This paper deals with the market situation when multiple sellers sell a product to a number of buyers with discount for group buying. We model this problem as a multi-unit double auction. We first examine two deterministic mechanisms that are budget balanced, individually rational and only one-sided truthful, i. e. it is truthful for either buyers or sellers. Then we find that, although there exists a "trivial" (non-deterministic) mechanism that is (weakly) budget balanced, individually rational and truthful for both buyers and sellers, such a mechanism is not achievable if we further require that both the trading size and the payment are neither seller-independent nor buyer-independent. In addition, we show that there is no budget balanced, individually rational and truthful mechanism that can also guarantee a reasonable trading size.

JELIA Conference 2012 Conference Paper

Relevant Minimal Change in Belief Update

• Laurent Perrussel
• Jerusa Marchi
• Jean-Marc Thévenin
• Dongmo Zhang

Abstract The notion of relevance was introduced by Parikh in the belief revision field for handling minimal change. It prevents the loss of beliefs that do not have connections with the epistemic input. But, the problem of minimal change and relevance is still an open issue in belief update. In this paper, a new framework for handling minimal change and relevance in the context of belief update is introduced. This framework goes beyond relevance in Parikh’s sense and enforces minimal change by first rewriting the Katzuno-Mendelzon postulates for belief update and second by introducing a new relevance postulate. We show that relevant minimal change can be characterized by setting agent’s preferences on beliefs where preferences are indexed by subsets of models of the belief set. Each subset represents a prime implicant of the belief set and thus stresses the key propositional symbols for representing the belief set.

IJCAI Conference 2011 Conference Paper

Mechanism Design for Double Auctions with Temporal Constraints

• Dengji Zhao
• Dongmo Zhang
• Laurent Perrussel

This paper examines an extended double auction model where market clearing is restricted by temporal constraints. It is found that the allocation problem in this model can be effectively transformed into a weighted bipartite matching in graph theory. By using the augmentation technique, we propose a Vickrey-Clarke-Groves (VCG) mechanism in this model and demonstrate the advantages of the payment compared with the classical VCG payment (the Clarke pivot payment). We also show that the algorithms for both allocation and payment calculation run in polynomial time. It is expected that the method and results provided in this paper can be applied to the design and analysis of dynamic double auctions and futures markets.

AAAI Conference 2010 Conference Paper

Dynamic Auction: A Tractable Auction Procedure

• Dongmo Zhang
• Laurent Perrussel

Dynamic auctions are trading mechanisms for discovering market-clearing prices and efficient allocations based on price adjustment processes. This paper studies the computational issues of dynamic auctions for selling multiple indivisible items. Although the decision problem of efficient allocations in a dynamic auction in general is intractable, it can be solved in polynomial time if the economy under consideration satisfies the condition of Gross Substitutes and Complements, which is known as the most general condition that guarantees the existence of Walrasian equilibrium. We propose a polynomial algorithm that can be used to find efficient allocations and introduce a double-direction auction procedure to discover a Walrasian equilibrium in polynomial time.

AAMAS Conference 2007 Conference Paper

Arguing for Gaining Access to Information

• Sylvie Doutre
• Peter McBurney
• Laurent Perrussel
• Jean-Marc Thevenin

This paper presents a protocol for agents engaged in argumentation over access to information sources. Obtaining relevant information is essential for agents engaged in autonomous, goal-directed behavior, but access to such information is usually controlled by other autonomous agents having their own goals. Because these various goals may be in conflict with one another, rational interactions between the two agents may take the form of a dialog, in which requests for information are successively issued, considered, justified and criticized. Even when the agents involved in such discussions agree on all the arguments for and the arguments against granting access to some information source, they may still disagree on their preferences between these arguments.

ECAI Conference 2006 Conference Paper

Elaborating Domain Descriptions

• Andreas Herzig
• Laurent Perrussel
• Ivan Varzinczak

In this work we address the problem of elaborating domain descriptions (alias action theories), in particular those that are expressed in dynamic logic. We define a general method based on contraction of formulas in a version of propositional dynamic logic with a solution to the frame problem. We present the semantics of our theory change and define syntactical operators for contracting a domain description. We establish soundness and completeness of the operators w. r. t. the semantics for descriptions that satisfy a principle of modularity that we have defined in previous work.

ECAI Conference 2006 Conference Paper

Mutual Enrichment for Agents Through Nested Belief Change: A Semantic Approach

• Laurent Perrussel
• Jean-Marc Thévenin
• Thomas Andreas Meyer

AAMAS Conference 2006 Conference Paper

Mutual Enrichment Through Nested Belief Change

• Laurent Perrussel
• Jean-Marc Thevenin
• Thomas Meyer

AAMAS Conference 2004 Conference Paper

A logical Approach for describing (dis)belief change and message processing

• Laurent Perrussel
• Jean-Marc Thevenin

ECAI Conference 2004 Conference Paper

A Syntactical Approach to Revision

• Guilherme Bittencourt
• Laurent Perrussel
• Jerusa Marchi

ECAI Conference 1998 Conference Paper

Contextual Reasoning

• Laurent Perrussel