Abstract argumentation framework ( AF ) is a unifying framework able to encompass a variety of nonmonotonic reasoning approaches, logic programming and computational argumentation. Yet, efficient approaches for most of the decision and enumeration problems associated to AF s are missing, thus limiting the efficacy of argumentation-based approaches in real domains. In this paper, we present an algorithm for enumerating the preferred extensions of abstract argumentation frameworks which exploits parallel computation. To this purpose, the SCC-recursive semantics definition schema is adopted, where extensions are defined at the level of specific sub-frameworks. The algorithm shows significant performance improvements in large frameworks, in terms of number of solutions found and speedup.

The recent years have seen several proposals aimed at placing the revision of logic programs within the belief change frameworks established for classical logic. A crucial challenge of this task lies in the nonmonotonicity of standard logic programming semantics. Existing approaches have thus used the monotonic characterisation via SE-models to develop semantic revision operators, which however neglect any syntactic information, or reverted to a syntax-oriented belief base approach altogether. In this paper, we bridge the gap between semantic and syntactic techniques by adapting the idea of a partial meet construction from classical belief change. This type of construction allows us to define new model-based operators for revising as well as contracting logic programs that preserve the syntactic structure of the programs involved. We demonstrate the rationality of our operators by testing them against the classic AGM or alternative belief change postulates adapted to the logic programming setting. We further present an algorithm that reduces the partial meet revision or contraction of a logic program to performing revision or contraction only on the relevant subsets of that program.

Module extraction — the task of computing a (preferably small) fragment M of an ontology T that preserves entailments over a signature S — has found many applications in recent years. Extracting modules of minimal size is, however, computationally hard, and often algorithmically infeasible. Thus, practical techniques are based on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations, however, ensure that M preserves all second-order entailments of T w.r.t. S, which is stronger than is required in many applications, and may lead to large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach not only generalises existing approximations in an elegant way, but it can also be tailored to preserve only specific kinds of entailments, which allows us to extract significantly smaller modules. An evaluation on widely-used ontologies has shown very encouraging results.

Evacuation planning is a critical aspect of disaster preparedness and response to minimize the number of people exposed to a threat. Controlled evacuations aim at managing the flow of evacuees as efficiently as possible and have been shown to produce significant benefits compared to self-evacuations. However, existing approaches do not capture the delays introduced by diverging and crossing evacuation routes, although evidence from actual evacuations highlights that these can lead to significant congestion. This paper introduces the concept of convergent evacuation plans to tackle this issue. It presents a MIP model to obtain optimal convergent evacuation plans which, unfortunately, does not scale to realistic instances. The paper then proposes a two-stage approach that separates the route design and the evacuation scheduling. Experimental results on a real case study show that the two-stage approach produces better primal bounds than the MIP model and is two orders of magnitude faster; It also produces dual bounds stronger than the linear relaxation of the MIP model. Finally, simulations of the evacuation demonstrate that convergent evacuation plans outperform existing approaches for realistic driver behaviors.

Stackelberg security games have been widely deployed to protect real-word assets. The main solution concept there is the Strong Stackelberg Equilibrium (SSE), which optimizes the defender's random allocation of limited security resources. However, solely deploying the SSE mixed strategy has limitations. In the extreme case, there are security games where the defender is able to defend all the assets ``almost perfectly" at the SSE, but she still sustains significant loss. In this paper, we propose an approach for improving the defender's utility in such scenarios. Perhaps surprisingly, our approach is to strategically reveal to the attacker information about the sampled pure strategy. Specifically, we propose a two-stage security game model, where in the first stage the defender allocates resources and the attacker selects a target to attack, and in the second stage the defender strategically reveals local information about that target, potentially deterring the attacker's attack plan. We then study how the defender can play optimally in both stages. We show, theoretically and experimentally, that the two-stage security game model allows the defender to gain strictly better utility than SSE.

Team formation is a core problem in AI. Remarkably, little prior work has addressed the problem of mechanism design for team formation, accounting for the need to elicit agents' preferences over potential teammates. Coalition formation in the related hedonic games has received much attention, but only from the perspective of coalition stability, with little emphasis on the mechanism design objectives of true preference elicitation, social welfare, and equity. We present the first formal mechanism design framework for team formation, building on recent combinatorial matching market design literature. We exhibit four mechanisms for this problem, two novel, two simple extensions of known mechanisms from other domains. Two of these (one new, one known) have desirable theoretical properties. However, we use extensive experiments to show our second novel mechanism, despite having no theoretical guarantees, empirically achieves good incentive compatibility, welfare, and fairness.

In cooperative game theory, it is typically assumed that the value of each coalition is known. We depart from this, assuming that v(S) is only a noisy estimate of the true value V (S), which is not yet known. In this context, we investigate which solution concepts maximize the probability of ex-post stability (after the true values are revealed). We show how various conditions on the noise characterize the least core and the nucleolus as optimal. Modifying some aspects of these conditions to (arguably) make them more realistic, we obtain characterizations of new solution concepts as being optimal, including the partial nucleolus, the multiplicative least core, and the multiplicative nucleolus.

We study strong equilibria in symmetric capacitated cost-sharing games. In these games, a graph with designated source s and sink t is given, and each edge is associated with some cost. Each agent chooses strategically an s-t path, knowing that the cost of each edge is shared equally between all agents using it. Two variants of cost-sharing games have been previously studied: (i) games where coalitions can form, and (ii) games where edges are associated with capacities; both variants are inspired by real-life scenarios. In this work we combine these variants and analyze strong equilibria (profiles where no coalition can deviate) in capacitated games. This combination gives rise to new phenomena that do not occur in the previous variants. Our contribution is two-fold. First, we provide a topological characterization of networks that always admit a strong equilibrium. Second, we establish tight bounds on the efficiency loss that may be incurred due to strategic behavior, as quantified by the strong price of anarchy (and stability) measures. Interestingly, our results are qualitatively different than those obtained in the analysis of each variant alone, and the combination of coalitions and capacities entails the introduction of more refined topology classes than previously studied.

Roughly speaking, Interdependent Defense (IDD) games, previously proposed, model the situation where an attacker wants to cause as much damage as possible to a network by attacking one of the sites in the network. Each site must make an investment decision regarding security to protect itself against a direct or indirect attack, the latter due to potential transfer-risk from an unprotected neighboring site. The work introducing IDD games discusses potential applications to model the essence of real-world scenarios such as the 2006 transatlantic aircraft plot. In this paper, our focus is the study of the problem of computing a Nash Equilibrium (NE) in IDD games. We show that an efficient algorithm to determine whether some attacker’s strategy can be a part of a NE in an instance of IDD games is unlikely to exist. Yet, we provide a dynamic programming algorithm to compute an approximate NE when the graph/network structure of the game is a directed tree with a single source, and show that it is an FPTAS. We also introduce an improved heuristic to compute an approximate NE on arbitrary graph structures. Our experiments show that our heuristic is more efficient, and provides better approximations, than best-response-gradient dynamics for the case of Internet games, a class of games introduced and studied in the original work on IDD games.

Auction theory traditionally assumes that bidders’ val- uation distributions are known to the auctioneer, such as in the celebrated, revenue-optimal Myerson auc- tion (Myerson 1981). However, this theory does not de- scribe how the auctioneer comes to possess this infor- mation. Recently work (Cole and Roughgarden 2014) showed that an approximation based on a finite sample of independent draws from each bidder’s distribution is sufficient to produce a near-optimal auction. In this work, we consider the problem of learning bidders’ val- uation distributions from much weaker forms of obser- vations. Specifically, we consider a setting where there is a repeated, sealed-bid auction with n bidders, but all we observe for each round is who won, but not how much they bid or paid. We can also participate (i.e., submit a bid) ourselves, and observe when we win. From this information, our goal is to (approximately) recover the inherently recoverable part of the underlying bid distributions. We also consider extensions where different subsets of bidders participate in each round, and where bidders’ valuations have a common-value component added to their independent private values.