Gianluigi Greco

ECAI Conference 2025 Conference Paper

Advancing Wildfire Risk Prediction via Morphology-Aware Curriculum Contrastive Learning

• Fabrizio Lo Scudo
• Alessio De Rango
• Luca Furnari
• Alfonso Senatore
• Donato D'Ambrosio
• Giuseppe Mendicino
• Gianluigi Greco

Wildfires significantly impact natural ecosystems and human health, leading to biodiversity loss, increased hydrogeological risks, and elevated emissions of toxic substances. Climate change exacerbates these effects, particularly in regions with rising temperatures and prolonged dry periods, such as the Mediterranean. This requires the development of advanced risk management strategies that utilize state-of-the-art technologies. However, in this context, the data show a bias toward an imbalanced setting, where the incidence of wildfire events is significantly lower than typical situations. This imbalance, coupled with the inherent complexity of high-dimensional spatio-temporal data, poses significant challenges for training deep learning architectures. Moreover, since precise wildfire predictions depend mainly on weather data, finding a way to reduce computational costs to enable more frequent updates using the latest weather forecasts would be beneficial. This paper investigates how adopting a contrastive framework can address these challenges through enhanced latent representations for the patch’s dynamic features. We thus introduce a new morphology-based curriculum contrastive learning that mitigates issues associated with diverse regional characteristics and enables the use of smaller patch sizes without compromising performance. An experimental analysis is performed to validate the effectiveness of the proposed modeling strategies.

AAAI Conference 2025 Conference Paper

Fair Division with Social Impact

• Michele Flammini
• Gianluigi Greco
• Giovanna Varricchio

In this paper, we consider the problem of fair division of indivisible goods, where the allocation of goods impacts society. Specifically, we introduce a second valuation function for each agent, which determines the social impact of allocating a good to the agent. Such impact is considered desirable for the society -- the higher, the better. Our goal is to understand how to allocate goods fairly from the agents' perspective while maintaining society as happy as possible. To this end, we measure the impact on society using the utilitarian social welfare, and provide both possibility and impossibility results. Our findings reveal that achieving good approximations, better than linear in the number of agents, is not possible while ensuring fairness to the agents. These impossibility results can be attributed to the fact that agents are completely unconscious of their social impact. Consequently, we explore scenarios where agents are socially aware, by introducing related fairness notions, and demonstrate that an appropriate definition of fairness is compatible with the social objective.

AIJ Journal 2024 Journal Article

Discrete preference games with logic-based agents: Formal framework, complexity, and islands of tractability

• Gianluigi Greco
• Marco Manna

Analyzing and predicting the dynamics of opinion formation in the context of social environments are problems that attracted much attention in literature. While grounded in social psychology, these problems are nowadays popular within the artificial intelligence community, where opinion dynamics are often studied via game-theoretic models in which individuals/agents hold opinions taken from a fixed set of discrete alternatives, and where the goal is to find those configurations where the opinions expressed by the agents emerge as a kind of compromise between their innate opinions and the social pressure they receive from the environments. As a matter of facts, however, these studies are based on very high-level and sometimes simplistic formalizations of the social environments, where the mental state of each individual is typically encoded as a variable taking values from a Boolean domain. To overcome these limitations, the paper proposes a framework generalizing such discrete preference games by modeling the reasoning capabilities of agents in terms of weighted propositional logics. It is shown that the framework easily encodes different kinds of earlier approaches and fits more expressive scenarios populated by conformist and dissenter agents. Problems related to the existence and computation of stable configurations are studied, under different theoretical assumptions on the structural shape of the social interactions and on the class of logic formulas that are allowed. Remarkably, during its trip to identify some relevant tractability islands, the paper devises a novel technical machinery whose significance goes beyond the specific application to analyzing opinion formation and diffusion, since it significantly enlarges the class of Integer Linear Programs that were known to be tractable so far.

AAAI Conference 2024 Conference Paper

Maxileximin Envy Allocations and Connected Goods

• Gianluigi Greco
• Francesco Scarcello

Fair allocation of indivisible goods presents intriguing challenges from both a social choice perspective and an algorithmic standpoint. Due to the indivisibility of goods, it is common for one agent to envy the bundle of goods assigned to another agent and, indeed, envy-free solutions do not exist in general. In line with the classical game-theoretic concept of Nucleolus in coalitional games, we propose that a fair allocation should minimize the agents’ dissatisfaction profile in a lexicographic manner, where the dissatisfaction of an agent is defined as her maximum envy towards other agents. Therefore, we seek allocations that minimize the maximum envy. In cases where multiple solutions have an equal maximum value, we minimize the second-worst value, and so on. Additionally, as is customary in fair division problems, we also consider an efficiency requirement: among the allocations with the best agents’ dissatisfaction profile, we prioritize those that maximize the sum of agents’ utilities, known as maximum social welfare. Such allocations, referred to as maxileximin allocations, always exist. In this study, we analyze the computational properties of maxileximin allocations in the context of fair allocation problems with constraints. Specifically, we focus on the Connected Fair Division problem, where goods correspond to the nodes of a graph, and a bundle of goods is allowed if the subgraph formed by those goods is connected. We demonstrate that the problem is F∆P2 -complete, even for instances with simple graphical structures such as path and star graphs. However, we identify islands of tractability for instances with more intricate graphs, such as those having bounded treewidth, provided that the number of agents is bounded by a fixed number and utility functions use small values.

IJCAI Conference 2023 Conference Paper

GIDnets: Generative Neural Networks for Solving Inverse Design Problems via Latent Space Exploration

• Carlo Adornetto
• Gianluigi Greco

In a number of different fields, including Engeneering, Chemistry and Physics, the design of technological tools and device structures is increasingly supported by deep-learning based methods, which provide suggestions on crucial architectural choices based on the properties that these tools and structures should exhibit. The paper proposes a novel architecture, named GIDnet, to address this inverse design problem, which is based on exploring a suitably defined latent space associated with the possible designs. Among its distinguishing features, GIDnet is capable of identifying the most appropriate starting point for the exploration and of likely converging into a point corresponding to a design that is a feasible one. Results of a thorough experimental activity evidence that GIDnet outperforms earlier approaches in the literature.

ECAI Conference 2023 Conference Paper

On the Effectiveness of Compact Strategies for Opinion Diffusion in Social Environments

• Carlo Adornetto
• Valeria Fionda
• Gianluigi Greco

An opinion diffusion scenario is considered where two marketers compete to diffuse their own opinions over a social network. In particular, they implement social proof marketing approaches that naturally give rise to a strategic setting, where it is crucial to find the appropriate order for targeting the individuals to which provide the incentives to adopt their opinions. The setting is extensively studied from the theoretical and empirical viewpoint, by considering strategies defined in a compact way, such as those that can be defined by selecting the individuals according to their degree of centrality in the underlying network. In addition to depicting a clear picture of the complexity issues arising in the setting, several compact strategies are empirically compared on real-world social networks. Results suggest that the effectiveness of compact strategies is moderately influenced by the characteristic of the network, with some centrality measures naturally emerging as good candidates to define heuristic approaches for marketing campaigns.

AIJ Journal 2022 Journal Article

Answers set programs for non-transferable utility games: Expressiveness, complexity and applications

• Giovanni Amendola
• Gianluigi Greco
• Pierfrancesco Veltri

Coalitional games are mathematical models suited to study payoff distribution problems in cooperative scenarios. In abstract terms, a coalitional game can be specified by explicitly listing all possible—in fact, exponentially many—coalitions with their associated distributions. This naïve representation, however, quickly becomes infeasible over games involving many agents, thereby calling for suitable compact representations, that is, encoding mechanisms that (on some specific classes of games of interest) take an amount of space that grows polynomially with the number of agents. To date, a plethora of compact encodings have been already introduced and analyzed from the algorithm and computational viewpoints. Despite their specific technical differences, these encodings typically share the assumption that the utility associated with a coalition can be freely transferred among agents. Indeed, designing encoding mechanisms for the non-transferable utility (NTU) setting is a research issue that has been largely unexplored so far. The paper addresses this issue by proposing a compact encoding for representing and reasoning about the outcomes of NTU coalitional games founding on answer set programming. By exploiting the expressiveness of this well-known knowledge representation formalism, it is shown that the proposed representation can succinctly encode several games of interest within a wide range of application domains. Computational issues arising in the setting have been studied too, by addressing questions related to certain payoff distributions enjoying desirable stability properties. Eventually, a prototype system supporting the proposed framework has been implemented by leveraging a state-of-the-art answer set engine, and results of a thorough experimental activity conducted on top of it have been discussed.

IJCAI Conference 2022 Conference Paper

LTL on Weighted Finite Traces: Formal Foundations and Algorithms

• Carmine Dodaro
• Valeria Fionda
• Gianluigi Greco

LTL on finite traces (LTLf ) is a logic that attracted much attention in recent literature, for its ability to formalize the qualitative behavior of dynamical systems in several application domains. However, its practical usage is still rather limited, as LTLf cannot deal with any quantitative aspect, such as with the costs of realizing some desired behaviour. The paper fills the gap by proposing a weighting framework for LTLf encoding such quantitative aspects in the traces over which it is evaluated. The complexity of reasoning problems on weighted traces is analyzed and compared to that of standard LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of relevant syntactic restrictions. Moreover, a reasoner for LTL on weighted finite traces is presented, and its performances are assessed on benchmark data.

TCS Journal 2021 Journal Article

Optimal majority dynamics for the diffusion of an opinion when multiple alternatives are available

• Vincenzo Auletta
• Diodato Ferraioli
• Gianluigi Greco

We consider opinion diffusion on social graphs where agents hold opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. Within this setting, we look for dynamics that allows us to maximize the diffusion of a target opinion given the initial opinions of all agents. In particular, we focus on the setting where more than two opinions are available to the agents, and we show that the properties of this setting are entirely different from those characterizing the setting where agents hold binary opinions only. Indeed, while it is well-known that greedy dynamics are always optimal ones in the binary case, this is no longer true in our more general setting and—rather surprisingly—even if just three opinions are available. Moreover, while it is possible to decide in polynomial time if a dynamics leading to consensus exists when agents have two available opinions, the problem becomes computationally intractable with three opinions, regardless of the fraction of agents that have the target opinion as their initial opinion.

AIJ Journal 2020 Journal Article

Coalitional games induced by matching problems: Complexity and islands of tractability for the Shapley value

• Gianluigi Greco
• Francesco Lupia
• Francesco Scarcello

The paper focuses on cooperative games where the worth of any coalition of agents is determined by the optimal value of a matching problem on (possibly weighted) graphs. These games come in different forms that can be grouped in two broad classes, namely of matching and allocation games, and they have a wide spectrum of applications, ranging from two-sided markets where buyers and sellers are encoded as vertices in a graph, to allocation problems where indivisible goods have to be assigned (matched) to agents in a fair way, possibly using monetary compensations. The Shapley value and the related notion of Banzhaf value have often been identified as appropriate solution concepts for many applications of matching/allocation games, but their computation is intractable in general. It is known that these concepts can be computed in polynomial time for matching games on unweighted trees and on graphs having degree at most two. However, it was open whether or not such positive results could be extended to the more general case of graphs having bounded treewidth, and to the case of allocation problems on weighted graphs. The paper provides a positive answer to these questions, by showing that computing the Shapley value and the Banzhaf value is feasible in polynomial time for the following classes of games: matching games over unweighted graphs having bounded treewidth, allocation games over weighted graphs having bounded treewidth, and allocation games over weighted graphs and such that each good is of interest for two agents at most. Without such structural restrictions, computing these solution concepts on allocation games is instead shown to be #P-hard, even in the case of unweighted graphs.

AIJ Journal 2020 Journal Article

On the complexity of reasoning about opinion diffusion under majority dynamics

• Vincenzo Auletta
• Diodato Ferraioli
• Gianluigi Greco

We study opinion diffusion on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by the majority of their neighbors. We provide bounds relating the number of agents that suffice to spread an opinion to all other agents with the number of required propagation steps. Bounds are established constructively, via polynomial time algorithms that identify the agents that must act as seeds. In particular, we show that, on any given social graph G = ( N, E ), it is possible to efficiently identify a set formed by half of the agents that can lead to consensus in min ⁡ { ⌊ | N | / 2 ⌋, even ( G ) + 1 } propagation steps, where even ( G ) is the number of agents with an even number of neighbors in G. The result marks the boundary of tractability, since we show that the existence of sets of seeds consisting of less than half of the agents depends on certain features of the underlying graphs, which are NP-hard to identify. In fact, other NP-hardness results emerge from our analysis. In particular, by closing a problem left open in the literature, we show that it is intractable to decide whether further stable configurations exist in addition to the “consensus” ones (where all agents hold the same opinion). Eventually, for all these problems related to reasoning about opinion diffusion, we show that islands of tractability can be identified by focusing on classes of tree-like social graphs.

ECAI Conference 2020 Conference Paper

On the Effectiveness of Social Proof Recommendations in Markets with Multiple Products

• Vincenzo Auletta
• Diodato Ferraioli
• Gianluigi Greco

The social proof marketing strategy assumes that the marketer provides a novel product for free to some users of a social network and then promptly recommends the product to other users, by informing them that a number of their friends are already using it. In this paper we study this popular marketing strategy in scenarios where the new product enters in markets where two old products are already competing. We show that if customers tend to adopt the product that is the most popular one (over the three alternative products) among their friends, then this marketing strategy allows to maximize the diffusion of the new product only on a narrow class of networks. Moreover, even if we focus on this narrow class of networks, computing the best order of the recommendations is computationally intractable. Instead, if customers are less prone to change their mind, that is, if they are willing to adopt some product only when an absolute majority of their friends has already agreed on it, then the marketing strategy always works well and, furthermore, an optimal order of recommendations can be computed in polynomial time.

AAAI Conference 2020 Conference Paper

The Complexity of Computing Maximin Share Allocations on Graphs

• Gianluigi Greco
• Francesco Scarcello

Maximin share is a compelling notion of fairness proposed by Buddish as a relaxation of more traditional concepts for fair allocations of indivisible goods. In this paper we consider this notion within a setting where bundles of goods must induce connected subsets over an underlying graph. This setting received much attention in earlier literature, and our study answers a number of questions that were left open. First, we show that computing maximin share allocations is FΔP 2 complete, even when focusing on consistent scenarios, that is, where such allocations are a-priori guaranteed to exist. Moreover, the problem remains intractable if all agents have the same type, i. e. , have the same utility functions, and if either the values returned by the utility functions are polynomially bounded, or the underlying graphs have a low degree of cyclicity (more precisely, have bounded treewidth). However, if these conditions hold all together, then computing maximin share allocations (or checking that none exists) becomes tractable. The result is established via machineries based on logspace alternating machines that use partial representations of connected bundles, which are interesting in their own.

AAMAS Conference 2019 Conference Paper

Maximizing the Spread of an Opinion when Tertium Datur Est

• Vincenzo Auletta
• Diodato Ferraioli
• Valeria Fionda
• Gianluigi Greco

IJCAI Conference 2018 Conference Paper

Constrained Coalition Formation on Valuation Structures: Formal Framework, Applications, and Islands of Tractability (Extended Abstract)

• Gianluigi Greco
• Antonella Guzzo

Coalition structure generation is considered in a setting where feasible coalition structures must satisfy constraints of two different kinds modeled in terms of a valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems in real-world applications. Moreover, complexity issues arising with them are studied, by focusing in particular on identifying islands of tractability based on topological properties of the underlying interaction graph. Stability issues on valuation structures are studied too.

JAIR Journal 2018 Journal Article

LTL on Finite and Process Traces: Complexity Results and a Practical Reasoner

• Valeria Fionda
• Gianluigi Greco

Linear temporal logic (LTL) is a modal logic where formulas are built over temporal operators relating events happening in different time instants. According to the standard semantics, LTL formulas are interpreted on traces spanning over an infinite timeline. However, applications related to the specification and verification of business processes have recently pointed out the need for defining and reasoning about a variant of LTL, which we name LTLp, whose semantics is defined over process traces, that is, over finite traces such that, at each time instant, precisely one propositional variable (standing for the execution of some given activity) evaluates true. The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf, which had already attracted attention in the literature and where formulas have the same syntax as in LTLp and are evaluated over finite traces, but without any constraint on the number of variables simultaneously evaluating true. The two formalisms are comparatively analyzed, by pointing out similarities and differences. In addition, a thorough complexity analysis has been conducted for reasoning problems about LTLp and LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of restrictions on the temporal operators that are allowed. Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature.

IJCAI Conference 2018 Conference Paper

Reasoning about Consensus when Opinions Diffuse through Majority Dynamics

• Vincenzo Auletta
• Diodato Ferraioli
• Gianluigi Greco

Opinion diffusion is studied on social graphs where agents hold binary opinions and where social pressure leads them to conform to the opinion manifested by their neighbors. Within this setting, questions related to whether a minority/majority can spread the opinion it supports to all the other agents are considered. It is shown that, no matter of the graph given at hand, there always exists a group formed by a half of the agents that can annihilate the opposite opinion. Instead, the influence power of minorities depends on certain features of the underlying graphs, which are NP-hard to be identified. Deciding whether the two opinions can coexist in some stable configuration is NP-hard, too.

AIJ Journal 2017 Journal Article

Constrained coalition formation on valuation structures: Formal framework, applications, and islands of tractability

• Gianluigi Greco
• Antonella Guzzo

Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept.

AAMAS Conference 2017 Conference Paper

Group Reasoning in Social Environments

• Erman Acar
• Gianluigi Greco
• Marco Manna

IJCAI Conference 2017 Conference Paper

The Tractability of the Shapley Value over Bounded Treewidth Matching Games

• Gianluigi Greco
• Francesco Lupia
• Francesco Scarcello

Matching games form a class of coalitional games that attracted much attention in the literature. Indeed, several results are known about the complexity of computing over them {solution concepts}. In particular, it is known that computing the Shapley value is intractable in general, formally #P-hard, and feasible in polynomial time over games defined on trees. In fact, it was an open problem whether or not this tractability result holds over classes of graphs properly including acyclic ones. The main contribution of the paper is to provide a positive answer to this question, by showing that the Shapley value is tractable for matching games defined over graphs having bounded treewidth. The proposed technique has been implemented and tested on classes of graphs having different sizes and treewidth at most three.

AIJ Journal 2016 Journal Article

Characteristic function games with restricted agent interactions: Core-stability and coalition structures

• Georgios Chalkiadakis
• Gianluigi Greco
• Evangelos Markakis

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i. e. , for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years.

EUMAS Conference 2016 Conference Paper

Coalition Formation with Logic-Based Agents

• Gianluigi Greco
• Antonella Guzzo

Abstract Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent s/he prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of “neighbors” occurring with them in the coalition that emerged. Within this setting, the computational complexity of a number of relevant reasoning problems is studied, by charting a clear picture of the intrinsic difficulty of finding “agreements” in such social environments. Some restrictions leading to identify classes of tractable instances are discussed, too.

IJCAI Conference 2016 Conference Paper

Modeling and Reasoning about NTU Games via Answer Set Programming

• Giovanni Amendola
• Gianluigi Greco
• Nicola Leone
• Pierfrancesco Veltri

A compact representation for non-transferable utility games founding on answer set programming is proposed. The representation is fully expressive, in that it can capture all games defined over a finite set of alternatives. Moreover, due to the knowledge representation capabilities of answer set programs, it can easily accommodate the definition of games within a wide range of application domains, ranging from scheduling, to routing and planning, just to name a few. The computational complexity of the proposed framework is studied, in particular, by focusing on the core as the prototypical solution concept. A system supporting the basic reasoning tasks arising therein is also made available, and results of experimental activity are discussed.

MFCS Conference 2016 Conference Paper

Ride Sharing with a Vehicle of Unlimited Capacity

• Angelo Fanelli 0001
• Gianluigi Greco

A ride sharing problem is considered where we are given a graph, whose edges are equipped with a travel cost, plus a set of objects, each associated with a transportation request given by a pair of origin and destination nodes. A vehicle travels through the graph, carrying each object from its origin to its destination without any bound on the number of objects that can be simultaneously transported. The vehicle starts and terminates its ride at given nodes, and the goal is to compute a minimum-cost ride satisfying all requests. This ride sharing problem is shown to be tractable on paths by designing a O(h*log(h)+n) algorithm, with h being the number of distinct requests and with n being the number of nodes in the path. The algorithm is then used as a subroutine to efficiently solve instances defined over cycles, hence covering all graphs with maximum degree 2. This traces the frontier of tractability, since NP-hard instances are exhibited over trees whose maximum degree is 3.

AAAI Conference 2016 Conference Paper

The Complexity of LTL on Finite Traces: Hard and Easy Fragments

• Valeria Fionda
• Gianluigi Greco

This paper focuses on LTL on finite traces (LTLf ) for which satisfiability is known to be PSPACE-complete. However, little is known about the computational properties of fragments of LTLf. In this paper we fill this gap and make the following contributions. First, we identify several LTLf fragments for which the complexity of satisfiability drops to NP-complete or even P, by considering restrictions on the temporal operators and Boolean connectives being allowed. Second, we study a semantic variant of LTLf, which is of interest in the domain of business processes, where models have the property that precisely one propositional variable evaluates true at each time instant. Third, we introduce a reasoner for LTLf and compare its performance with the state of the art.

IJCAI Conference 2015 Conference Paper

Group Decision Making via Weighted Propositional Logic: Complexity and Islands of Tractability

• Gianluigi Greco
• Jerome Lang

We study a general class of multiagent optimization problems, together with a compact representation language of utilities based on weighted propositional formulas. We seek solutions maximizing utilitarian social welfare as well as fair solutions maximizing the utility of the least happy agent. We show that many problems can be expressed in this setting, such as fair division of indivisible goods, some multiwinner elections, or multifacility location. We focus on the complexity of finding optimal solutions, and we identify the tractability boarder between polynomial and NP-hard settings, along several parameters: the syntax of formulas, the allowed weights, as well as the number of agents, propositional symbols, and formulas per agent.

IJCAI Conference 2015 Conference Paper

Structural Tractability of Shapley and Banzhaf Values in Allocation Games

• Gianluigi Greco
• Francesco Lupia
• Francesco Scarcello

Allocation games are coalitional games defined in the literature as a way to analyze fair division problems of indivisible goods. The prototypical solution concepts for them are the Shapley value and the Banzhaf value. Unfortunately, their computation is intractable, formally #P-hard. Motivated by this bad news, structural requirements are investigated which can be used to identify islands of tractability. The main result is that, over the class of allocation games, the Shapley value and the Banzhaf value can be computed in polynomial time when interactions among agents can be formalized as graphs of bounded treewidth. This is shown by means of technical tools that are of interest in their own and that can be used for analyzing different kinds of coalitional games. Tractability is also shown for games where each good can be assigned to at most two agents, independently of their interactions.

AAAI Conference 2015 Conference Paper

Trust Models for RDF Data: Semantics and Complexity

• Valeria Fionda
• Gianluigi Greco

Due to the openness and decentralization of the Web, mechanisms to represent and reason about the reliability of RDF data become essential. This paper embarks on a formal analysis of RDF data enriched with trust information by focusing on the characterization of its model-theoretic semantics and on the study of relevant reasoning problems. The impact of trust values on the computational complexity of well-known concepts related to the entailment of RDF graphs is studied. In particular, islands of tractability are identified for classes of acyclic and nearly-acyclic graphs. Moreover, an implementation of the framework and an experimental evaluation on real data are discussed.

TCS Journal 2014 Journal Article

Tree projections and structural decomposition methods: Minimality and game-theoretic characterization

• Gianluigi Greco
• Francesco Scarcello

Tree projections provide a mathematical framework that encompasses all the various (purely) structural decomposition methods that have been proposed in the literature to single out classes of nearly-acyclic (hyper)graphs, such as the tree decomposition method, which is the most powerful decomposition method on graphs, and the (generalized) hypertree decomposition method, which is its natural counterpart on arbitrary hypergraphs. The paper analyzes this framework, by focusing in particular on “minimal” tree projections, that is, on tree projections without useless redundancies. First, it is shown that minimal tree projections enjoy a number of properties that are usually required for normal form decompositions in various structural decomposition methods. In particular, they enjoy the same kind of connection properties as (minimal) tree decompositions of graphs, with the result being tight in the light of the negative answer that is provided to the open question about whether they enjoy a slightly stronger notion of connection property, defined to speed-up the computation of hypertree decompositions. Second, it is shown that tree projections admit a natural game-theoretic characterization in terms of the Robber and Captain game. In this game, as for the Robber and Cops game characterizing tree decompositions, the existence of winning strategies implies the existence of monotone ones. As a special case, the Robber and Captain game can be used to characterize the generalized hypertree decomposition method, where such a game-theoretic characterization was missing and asked for. Besides their theoretical interest, these results have immediate algorithmic applications both for the general setting and for structural decomposition methods that can be recast in terms of tree projections.

AIJ Journal 2013 Journal Article

The complexity of mixed multi-unit combinatorial auctions: Tractability under structural and qualitative restrictions

• Valeria Fionda
• Gianluigi Greco

Mixed multi-unit combinatorial auctions (MMUCAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i. e. , determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from classical combinatorial auctions, little was known about whether polynomial-time solvable classes of MMUCAs can be singled out on the basis of their characteristics. The paper fills this gap, by studying the computational complexity of MMUCA instances under structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively.

ECAI Conference 2012 Conference Paper

Hard and Easy k-Typed Compact Coalitional Games: The Knowledge of Player Types Marks the Boundary

• Gianluigi Greco
• Enrico Malizia
• Francesco Scarcello
• Luigi Palopoli 0001

Coalitional games model scenarios where rational agents can form coalitions so as to obtain higher worths than by acting in isolation. Once a coalition forms and obtains its worth, the problem of how this worth can be fairly distributed has to be faced. Desirable worth distributions are usually referred to as solution concepts. Recent research pointed out that, while reasoning problems involving such solution concepts are hard in general for games specified in compact form (e. g. , graph games), some of them, in particular the core, become tractable when agents come partitioned into a fixed number k of types, i. e. , of classes of strategically equivalent players. The paper continues along this line of research, by firstly showing that two other relevant solution concepts, the kernel and the nucleolus, are tractable in this setting and independently of the specific game encoding, provided worth functions are given as a polynomial-time computable oracles. Then, it analyzes a different setting where games are still k-typed but the actual player partitioning is not a-priori known. Within this latter setting, the paper addresses the question about how efficiently strategic equivalence between pairs of players can be recognized, and reconsiders the computational complexity of the core, the kernel, and the nucleolus. All such problems and notions emerged to be intractable, thereby evidencing that the knowledge of player types marks the boundary of tractability for reasoning about k-typed coalitional games.

AIJ Journal 2012 Journal Article

Magic Sets for disjunctive Datalog programs

• Mario Alviano
• Wolfgang Faber
• Gianluigi Greco
• Nicola Leone

In this paper, a new technique for the optimization of (partially) bound queries over disjunctive Datalog programs with stratified negation is presented. The technique exploits the propagation of query bindings and extends the Magic Set optimization technique (originally defined for non-disjunctive programs). An important feature of disjunctive Datalog programs is non-monotonicity, which calls for non-deterministic implementations, such as backtracking search. A distinguishing characteristic of the new method is that the optimization can be exploited also during the non-deterministic phase. In particular, after some assumptions have been made during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space. In contrast, the effect of the previously defined Magic Set methods for disjunctive Datalog is limited to the deterministic portion of the process. In this way, the potential performance gain by using the proposed method can be exponential, as could be observed empirically. The correctness of the method is established and proved in a formal way thanks to a strong relationship between Magic Sets and unfounded sets that has not been studied in the literature before. This knowledge allows for extending the method and the correctness proof also to programs with stratified negation in a natural way. The proposed method has been implemented in the DLV system and various experiments on synthetic as well as on real-world data have been conducted. The experimental results on synthetic data confirm the utility of Magic Sets for disjunctive Datalog, and they highlight the computational gain that may be obtained by the new method with respect to the previously proposed Magic Set method for disjunctive Datalog programs. Further experiments on data taken from a real-life application show the benefits of the Magic Set method within an application scenario that has received considerable attention in recent years, the problem of answering user queries over possibly inconsistent databases originating from integration of autonomous sources of information.

ECAI Conference 2012 Conference Paper

Process Discovery via Precedence Constraints

• Gianluigi Greco
• Antonella Guzzo
• Luigi Pontieri

A key task in process mining consists of building a graph of causal dependencies over process activities, which can then be used to derive more expressive models in some high-level modeling language. An approach to accomplish this task is presented where the learning process can exploit the background knowledge that, in many cases, is available to the analysts taking care of the process (re-)design. The method is based on encoding the information gathered from the log and the (possibly) given background knowledge in terms of precedence constraints, i. e. , constraints over the topology of the graphs. Learning algorithms are eventually formulated in terms of reasoning problems over precedence constraints, and the computational complexity of such problems is thoroughly analyzed by tracing their tractability frontier. The whole approach has been implemented in a prototype system leveraging a solid constraint programming platform, and results of experimental activity are reported.

AIJ Journal 2011 Journal Article

On the complexity of core, kernel, and bargaining set

• Gianluigi Greco
• Enrico Malizia
• Luigi Palopoli
• Francesco Scarcello

Coalitional games model scenarios where players can collaborate by forming coalitions in order to obtain higher worths than by acting in isolation. A fundamental issue of coalitional games is to single out the most desirable outcomes in terms of worth distributions, usually called solution concepts. Since decisions taken by realistic players cannot involve unbounded resources, recent computer science literature advocated the importance of assessing the complexity of computing with solution concepts. In this context, the paper provides a complete picture of the complexity issues arising with three prominent solution concepts for coalitional games with transferable utility, namely, the core, the kernel, and the bargaining set, whenever the game worth-function is represented in some reasonably compact form. The starting points of the investigation are the settings of graph games and of marginal contribution nets, where the worth of any coalition can be computed in polynomial time in the size of the game encoding and for which various open questions were stated in the literature. The paper answers these questions and, in addition, provides new insights on succinctly specified games, by characterizing the computational complexity of the core, the kernel, and the bargaining set in relevant generalizations and specializations of the two settings. Concerning the generalizations, the paper shows that dealing with arbitrary polynomial-time computable worth functions—no matter of the specific game encoding being considered—does not provide any additional source of complexity compared to graph games and marginal contribution nets. Instead, only for the core, a slight increase in complexity is exhibited for classes of games whose worth functions encode NP-hard optimization problems, as in the case of certain combinatorial games. As for specializations, the paper illustrates various tractability results on classes of bounded treewidth graph games and marginal contribution networks.

IJCAI Conference 2011 Conference Paper

On the Complexity of the Core over Coalition Structures

• Gianluigi Greco
• Enrico Malizia
• Luigi Palopoli
• Francesco Scarcello

The computational complexity of relevant corerelatedquestions for coalitional games is addressed from the coalition structure viewpoint, i. e. , withoutassuming that the grand-coalition necessarily forms. In the analysis, games are assumed to be in "compact" form, i. e. , their worth functions are implicitly given as polynomial-time computable functions over succinct game encodings provided as input. Within this setting, a complete picture of the complexity issues arising with the core, as well as with the related stability concepts of least core and cost of stability, is depicted. In particular, the special cases of superadditive games and of games whose sets of feasible coalitions are restricted over tree-like interaction graphs are also studied.

AIJ Journal 2010 Journal Article

On the power of structural decompositions of graph-based representations of constraint problems

• Gianluigi Greco
• Francesco Scarcello

The Constraint Satisfaction Problem (CSP) is a central issue of research in Artificial Intelligence. Due to its intractability, many efforts have been made in order to identify tractable classes of CSP instances, and in fact deep and useful results have already been achieved. In particular, this paper focuses on structural decomposition methods, which are essentially meant to look for near-acyclicity properties of the graphs or hypergraphs that encode the structure of the constraints interactions. In general, constraint scopes comprise an arbitrary number of variables, and thus this structure may be naturally encoded via hypergraphs. However, in many practical applications, decomposition methods are applied over suitable graph representations of the (possibly non-binary) CSP instances at hand. Despite the great interest in such binary approaches, a formal analysis of their power, in terms of their ability of identifying islands of tractability, was missing in the literature. The aim of this paper is precisely to fill this gap, by studying the relationships among binary structural methods, and by providing a clear picture of the tractable fragments of CSP that can be specified with respect to each of these decomposition approaches, when they are applied to binary representations of non-binary CSP instances. In particular, various long-standing questions about primal, dual and incidence graph encodings are answered. The picture is then completed by comparing methods on binary encodings with methods specifically conceived for non-binary constraints.

IJCAI Conference 2009 Conference Paper

• Gianluigi Greco
• Enrico Malizia
• Luigi Palopoli
• Francesco Scarcello

A significantly complete account of the complexity underlying the computation of relevant solution concepts in compact coalitional games is provided. The starting investigation point is the setting of graph games, about which various long-standing open problems were stated in the literature. The paper gives an answer to most of them, and in addition provides new insights on this setting, by stating a number of complexity results about some relevant generalizations and specializations. The presented results also pave the way towards precisely carving the tractability frontier characterizing computation problems on compact coalitional games.

IJCAI Conference 2009 Conference Paper

• Valeria Fionda
• Gianluigi Greco

Mixed multi-unit combinatorial auctions (MMU- CAs) are extensions of classical combinatorial auctions (CAs) where bidders trade transformations of goods rather than just sets of goods. Solving MMUCAs, i. e. , determining the sequences of bids to be accepted by the auctioneer, is computationally intractable in general. However, differently from CAs, little was known about whether polynomialtime solvable classes of MMUCAs can be singled out based on constraining their characteristics. The paper precisely fills this gap, by depicting a clear picture of the “tractability frontier” for MMUCA instances under both structural and qualitative restrictions, which characterize interactions among bidders and types of bids involved in the various transformations, respectively. By analyzing these restrictions, a sharp frontier is charted based on various dichotomy results. In particular, tractability islands resulting from the investigation generalize on MMUCAs the largest class of tractable CAs emerging from the literature.

TCS Journal 2009 Journal Article

On the complexity of constrained Nash equilibria in graphical games

• Gianluigi Greco
• Francesco Scarcello

A widely accepted rational behavior for non-cooperative players is based on the notion of Nash equilibrium. Although the existence of a Nash equilibrium is guaranteed in the mixed framework (i. e. , when players select their actions in a randomized manner) in many real-world applications the existence of “any” equilibrium is not enough. Rather, it is often desirable to single out equilibria satisfying some additional requirements (in order, for instance, to guarantee a minimum payoff to certain players), which we call constrained Nash equilibria. In this paper, a formal framework for specifying these kinds of requirement is introduced and investigated in the context of graphical games, where a player p may directly be interested in some of the other players only, called the neighbors of p. This setting is very useful for modeling large population games, where typically each player does not directly depend on all the players, and representing her utility function extensively is either inconvenient or infeasible. Based on this framework, the complexity of deciding the existence and of computing constrained equilibria is then investigated, in the light of evidencing how the intrinsic difficulty of these tasks is affected by the requirements prescribed at the equilibrium and by the structure of players’ interactions. The analysis is carried out for the setting of mixed strategies as well as for the setting of pure strategies, i. e. , when players are forced to deterministically choose the action to perform. In particular, for this latter case, restrictions on players’ interactions and on constraints are identified, that make the computation of Nash equilibria an easy problem, for which polynomial and highly-parallelizable algorithms are presented.

IJCAI Conference 2007 Conference Paper

• Georg Gottlob
• Gianluigi Greco
• Toni Mancini

In this paper we make a comprehensive study of the complexity of the problem of deciding the existence of equilibria in strategic games with incomplete information, in case of pure strategies. In particular, we show that this is NP-complete in general Bayesian Games in Standard Normal Form, and that it becomes PP-hard (and, in fixed-precision scenarios, PP-complete), when the game is represented succinctly in General Normal Form. Suitable restrictions in case of graphical games that make the problem tractable are also discussed.

IJCAI Conference 2007 Conference Paper

• Georg Gottlob
• Gianluigi Greco
• Toni Mancini

Conditional Constraint Satisfaction Problems (CCSPs) are generalizations of classical CSPs that support conditional activation of variables and constraints. Despite the interest emerged for CCSPs in the context of modelling the intrinsic dynamism of diagnosis, structural design, and product configuration applications, a complete characterization of their computational properties and of their expressiveness is still missing. In fact, the aim of the paper is precisely to face these open research issues. First, CCSPs are formally characterized in terms of a suitable fragment of first-order logic. Second, the complexity of some basic reasoning tasks for CCSPs is studied, by establishing completeness results for the first and the second level of the polynomial hierarchy. Finally, motivated by the hardness results, an island of tractability for CCSPs is identified, by extending structural decomposition methods originally proposed for CSPs.

UAI Conference 2005 Conference Paper

Bounding the Uncertainty of Graphical Games: The Complexity of Simple Requirements, Pareto and Strong Nash Equilibria

• Gianluigi Greco
• Francesco Scarcello

We investigate the complexity of bounding the uncertainty of graphical games, and we provide new insight into the intrinsic difficulty of computing Nash equilibria. In particular, we show that, if one adds very simple and natural additional requirements to a graphical game, the existence of Nash equilibria is no longer guaranteed, and computing an equilibrium is an intractable problem. Moreover, if stronger equilibrium conditions are required for the game, we get hardness results for the second level of the polynomial hierarchy. Our results offer a clear picture of the complexity of mixed Nash equilibria in graphical games, and answer some open research questions posed by Conitzer and Sandholm (2003).

IJCAI Conference 2005 Conference Paper

The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions

• Georg Gottlob
• Gianluigi Greco
• Francesco

We give a clear picture of the tractability/intractability frontier for quantified constraint satisfaction problems (QCSPs) under structural restrictions. On the negative side, we prove that checking QCSP satisfiability remains PSPACE-hard for all known structural properties more general than bounded treewidth and for the incomparable hypergraph acyclicity. Moreover, if the domain is not fixed, the problem is PSPACE-hard even for tree-shaped constraint scopes. On the positive side, we identify relevant tractable classes, including QCSPs with prefix ∃∀ having bounded hypertree width, and QCSPs with a bounded number of guards. The latter are solvable in polynomial time without any bound on domains or quantifier alternations.

ECAI Conference 2004 Conference Paper

Constrained Pure Nash Equilibria in Graphical Games

• Gianluigi Greco
• Francesco Scarcello

JELIA Conference 2004 Conference Paper

Discovering Anomalies in Evidential Knowledge by Logic Programming

• Fabrizio Angiulli
• Gianluigi Greco
• Luigi Palopoli 0001

Abstract The development of effective knowledge discovery techniques has become in the recent few years a very active research area due to the important impact it has in several relevant application areas. One interesting task thereof is that of singling out anomalous individuals from a given population, e. g. , to detect rare events in time-series analysis settings, or to identify objects whose behavior is deviant w. r. t. a codified standard set of “social” rules. Such exceptional individuals are usually referred to as outliers in the literature. Recently, outlier detection has also emerged as a relevant KR&R problem in the context of default logic [2]. For instance, detection algorithms can be used by rational agents to single out those observations that are anomalous to some extent w. r. t. their own, trustable knowledge about the world encoded in the form of a suitable logic theory. In this paper, we formally state the concept of outliers in the context of logic programming. Besides the novel formalization we propose which helps in shedding some lights on the real nature of outliers, a major contribution of the work lies in the exploitation of a minimality criteria in their detection. Moreover, the computational complexity of outlier detection problems arising in this novel setting is thoroughly investigated and accounted for in the paper as well. Finally, we also propose a rewriting algorithm that transforms any outlier problem into an equivalent answer set computation problem, thereby making outlier computation effective and realizable on top of any answer set engine.

IJCAI Conference 2003 Conference Paper

Non-Binary Constraints and Optimal Dual-Graph Representations

• Gianluigi Greco
• Francesco Scarcello

We study the relationships among structural methods for identifying and solving tractable classes of Constraint Satisfaction Problems (CSPs). In particular, we first answer a long-standing question about the notion of biconnected components applied to an "optimal" reduct of the dual constraint-graph, by showing that this notion is in fact equivalent to the hinge decomposition method. Then, we give a precise characterization of the relationship between the treewidth notion applied to the hidden-variable encoding of a CSP and the same notion applied to some optimal reduct of the dual constraint-graph. Finally, we face the open problem of computing such an optimal reduct. We provide an algorithm that outputs an approximation of an optimal tree decomposition, and give a qualitative explanation of the difference between this graph-based method and more general hypergraph-based methods.

TARK Conference 2003 Conference Paper

Pure Nash equilibria: hard and easy games

• Georg Gottlob
• Gianluigi Greco
• Francesco Scarcello

In this paper we investigate complexity issues related to pure Nash equilibria of strategic games. We show that, even in very restrictive settings, determining whether a game has a pure Nash Equilibrium is NP-hard, while deciding whether a game has a strong Nash equilibrium is St-complete. We then study practically relevant restrictions that lower the complexity. In particular, we are interested in quantitative and qualitative restrictions of the way each player's move depends on moves of other players. We say that a game has small neighborhood if the " utility function for each player depends only on (the actions of) a logarithmically small number of other players, The dependency structure of a game G can he expressed by a graph G(G) or by a hypergraph I-I(G). Among other results, we show that if jC has small neighborhood and if I-I(G) has botmdecl hypertree width (or if G(G) has bounded treewidth), then finding pure Nash and Pareto equilibria is feasible in polynomial time. If the game is graphical, then these problems are LOGCFL-complete and thus in the class _NC~of highly parallelizable problems.

JELIA Conference 2002 Conference Paper

Complexity and Algorithms for the Matching of Bag and Set Terms

• Gianluigi Greco
• Ester Zumpano

Abstract Bounded bag and set terms are complex terms in which every element can be a constant or a variable. These types of complex terms have been introduced in several logic languages, such as LDL, Coral and Godel, in order to increase their expressive power, and they have been recently used to define logic languages for database integration. The paper addresses the problem of computing the set of matchers of two bag (or set) terms, by providing a general complexity analysis and a closed formula for determining the number of matchers for tractable cases. An algorithm for the general problem and optimal algorithms for tractable cases are also provided.

LPAR Conference 2002 Conference Paper

Query Optimization of Disjunctive Databases with Constraints through Binding Propagation

• Gianluigi Greco
• Sergio Greco
• Irina Trubitsyna
• Ester Zumpano

Abstract In this paper we present a technique for the optimization of bound queries over disjunctive deductive databases with constraints, i. e. rules defining properties which have to be satisfied by all instances over database schema. The technique we propose, allows the binding propagation into disjunctive queries with a set of constraints; thus, reducing the size of the data relevant to answer the query it, consequently, minimizes both the complexity of computing a single model and the whole number of models to be considered. The main contribution of this work consists in the extension of previous techniques by considering Datalog programs with both disjunctive heads and constraints. In particular, by considering weak constraints the technique is also suitable for dealing with optimization problems. Several experiments have confirmed the value of the technique.

LOPSTR Conference 2002 Conference Paper

Translating Datalog-Like Optimization Queries into ILOG Programs

• Gianluigi Greco
• Sergio Greco
• Irina Trubitsyna
• Ester Zumpano

Abstract This paper presents a logic language, called \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) suitable for expressing NP search and optimization problems. The ‘search’ language extends stratified Datalog with constraints and allows disjunction to define nondeterministically partitions of relations. It’s well known that \( \mathcal{N}\mathcal{P} \) search problems can be formulated as unstratified DATALOG queries under nondeterministic stable model semantics so that each stable model corresponds to a possible solution. \( \mathcal{N}\mathcal{P} \) optimization problems are then formulated by adding a max (or min ) construct to select the stable model (thus, the solution) which maximizes (resp. , minimizes) the result of a polynomial function applied to the answer relation. The problem in using DATALOG ¬ to express search and optimization problems is that the unrestricted negation in programs is often neither simple nor intuitive and, besides, it does not allow to discipline the expressive power. Thus, we consider restricted forms of negation which force user to write programs in a more disciplined way without loosing of expressive power. More specifically, we consider the language \( \mathcal{N}\mathcal{P}{\mathbf{ }}Datalog \) which extends DATALOG ¬ s with two simple forms of unstratified negation embedded into built-in constructs: head disjunction and constraints. Thus the core of our language is stratified Datalog extended with two constructs allowing nondeterministic selections and with query goals enforcing conditions to be satisfied by stable models.