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.

Argument Mining (AM) [1], the task of extracting arguments and their relations (e.g. attacks, supports) from text, has lead to potential applications of formal models of argumentation on real-world scenarios. However, AM methods largely depend on Machine Learning (ML) techniques, which require high-quality annotated data. This poses a significant limitation in domains like legal reasoning, where annotated corpora are extremely scarce. Current legal AM research relies almost entirely on a single dataset from the European Court of Human Rights (ECHR) [2], limiting the development of robust, argumentation-driven automated legal reasoning systems. Addressing this data scarcity is essential for advancing computational legal argumentation. To address this challenge, this paper briefly describes some preliminary results that demonstrate the promising potential of LLMs to assist legal experts in annotating additional legal corpora. This advancement paves the way for more robust, argumentation-driven automated reasoning systems in the legal domain. More details on our approach and experimental results are provided in [3].

International audience

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.

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.

Abstract Bisimulations are a key notion to study the expressive power of a modal language. This paper studies the expressivity of Game Description Language (GDL) and its epistemic extension Epistemic GDL (EGDL) through a bisimulation approach. We first define a notion of bisimulation for GDL and prove that it coincides with the indistinguishability of GDL formulas. Based on it, we establish a characterization of the definability of GDL in terms of $k$-bisimulations. Then we design novel notions of bisimulation for EGDL and obtain characterizations of the expressive power of EGDL in terms of them. These characterizations provide a powerful tool to identify the expressive power of game description languages. Finally, we demonstrate with real games that bisimulation can be generalized to capture a wide range of game equivalence.

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.

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.

Abstract In this paper, we present two models for reasoning about strategic actions in opinion diffusion. In both models, the agents are endowed with goals expressed compactly in a suitably defined language of linear temporal logic and are connected in an influence network which defines the underlying opinion diffusion process. The agents can act by exerting their influence or retain from it: in one case, we assume an initial state of incomplete information about the agents’ opinions, while in the other, we assume that the agents have complete information. We investigate the interplay between simple network structures (e.g. certain acyclic graphs) and the existence of game-theoretic solution concepts for the unanimity aggregator. We also give bounds for the computational complexity of strategic reasoning in both our models on arbitrary networks.

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.

International audience

Judgment aggregation deals with the problem of how collective judgments on logically connected propositions can be formed based on individual judgments on the same propositions. The existing literature on judgment aggregation mainly focuses on the anonymity condition requiring that individual judgments be treated equally. However, in many real‐world situations, a group making collective judgments may assign individual members or subgroups different priorities to determine the collective judgment. Based on this consideration, this article relaxes the anonymity condition by giving a hierarchy over individuals so as to investigate how the judgment from each individual affects the group judgment in such a hierarchical environment. Moreover, we assume that an individual can abstain from voting on a proposition and the collective judgment on a proposition can be undetermined, which means that we do not require completeness at both individual and collective levels. In this new setting, we first identify an impossibility result and explore a set of plausible conditions in terms of abstentions. Secondly, we develop an aggregation rule based on the hierarchy of individuals and show that the aggregation rule satisfies those plausible conditions. The computational complexity of this rule is also investigated. Finally, we show that the proposed rule is (weakly) oligarchic over a subset of agenda. This is by no means a negative result. In fact, our result reveals that with abstentions, oligarchic aggregation is not necessary to be a single‐level determination but can be a multiple‐level collective decision making, which partially explains its ubiquity in the real world.

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.

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.

Studies on mechanism design mostly focus on a single market where sellers and buyers trade. This paper examines the problem of mechanism design for capacity allocation in two connected markets where a supplier allocates products to a set of retailers and the retailers resale the products to end-users in price competition. We consider the problems of how allocation mechanisms in the upstream market determine the behaviors of markets in the downstream market and how pricing policy in the downstream market influences the properties of allocation mechanisms. We classify an effective range of capacity that influences pricing strategies in the downstream market according to allocated quantities. Within the effective capacity range, we show that the retailers tend to inflate orders under proportional allocation, but submit truthful orders under uniform allocation. We observe that heterogeneous allocations results in greater total retailer profit which is a unique phenomenon in our model. The results would be applied to the design and analysis of Business-to-Business (B2B) marketplaces and supply chain management.

This paper focuses on the features of belief change in a multi-agent context where agents consider beliefs and disbeliefs. Disbeliefs represent explicit ignorance and are useful to prevent agents to entail conclusions due to their ignorance. Agents receive messages holding information from other agents and change their belief state accordingly. An agent may refuse to adopt incoming information if it prefers its own (dis)beliefs. For this, each agent maintains a preference relation over its own beliefs and disbeliefs in order to decide if it accepts or rejects incoming information whenever inconsistencies occur. This preference relation may be built by considering several criteria such as the reliability of the sender of statements or temporal aspects. This process leads to non-prioritized belief revision. In this context we first present the * and − operators which allow an agent to revise, respectively contract, its belief state in a non-prioritized way when it receives an incoming belief, respectively disbelief. We show that these operators behave properly. Based on this we then illustrate how the receiver and the sender may argue when the incoming (dis)belief is refused. We describe pieces of dialog where (i) the sender tries to convince the receiver by sending arguments in favor of the original (dis)belief and (ii) the receiver justifies its refusal by sending arguments against the original (dis)belief. We show that the notion of acceptability of these arguments can be represented in a simple way by using the non-prioritized change operators * and −. The advantage of argumentation dialogs is twofold. First whenever arguments are acceptable the sender or the receiver reconsider its belief state; the main result is an improvement of the reconsidered belief state. Second the sender may not be aware of some sets of rules which act as constraints to reach a specific conclusion and discover them through argumentation dialogs.

We present a logical framework for reasoning about inconsistent requirements in the context of the multi-viewpoint requirements engineering process. In order to analyse the sources of inconsistencies and to reason with inconsistent requirements, we present an argumentation view of the requirements. Intuitively, argumentation is a tool for reasoning with inconsistent knowledge: requirements are defined in terms of arguments (a conclusion with its support); then, a class of acceptable arguments is built (arguments with no counterarguments). We propose to characterize different classes of requirements which are ordered: from weakly confident to strongly confident (i.e. consistent). We present inference rules to build intra and inter-viewpoint reasoning. Inference rules are issued from the classes of requirements. We show how this work is useful for the requirements engineers to analyse inconsistent fragments of requirements.

The requirement engineering activity (for composite systems) implies the existence of several viewpoints on the software to be designed. The specifications will be issued from those different perspectives which complement but also contradict each other. Notably each perspective may be specified using a particular language. Consequently the central problem is to express links between those perspectives, i.e. the specification fragments. This article outlines a multi agent system for expressing the inter perspective relationships. Each perspective is associated with an agent. The distributed artificial intelligence (DAI) framework allows one to represent links between perspectives and to represent the dynamics of those links. Notably, our multi agent system can represent temporal constraints on the dynamics of the relations between the agents and then between the perspectives. To this end we characterize the inter perspective relationships. A logical approach of these relationships based on temporal logic is then presented and discussed.