Title : DL Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog
| Presenter | Gastón Tagni |
| Abstract | During my next WAI talk I will first present a novel approach based on Ordered Binary Decision Diagrams (OBDDs) for terminological reasoning in the Description Logic SHIQ. Under this new paradigm SHIQ terminologies are translated into the DL ALCIb and the resulting Tbox is then converted into an OBDD that represents a canonical model of the terminology. The approach exploits the fact that models for the DL ALCIb can be decomposed into smaller components, called dominoes, and that suitable domino sets can be used to reconstruct models of ALCIb terminologies. Based on this, satisfiability of ALCIb terminologies can be reduced to checking the existence of such suitable sets. In other words, a ALCIb terminology is satisfiable iff its canonical domino set is non-empty. After presenting this approach I will discuss the possibility of using Evolutionary Computing methods for "guessing" suitable domino sets. This is in contrast to the idea of constructing the canonical domino set starting from the exponentially large set of all possible dominoes, as it is the case with the OBDD-based paradigm. |
| Slides | Click on that link to get the slides |
Title : Beating Cheating: Dealing with Collusion in the Non-Iterated Prisoner’s Dilemma
| Presenter | Nicolas Höning |
| Abstract | The Iterated Prisoner’s Dilemma (IPD) is a well-known challenging problem for researching multi-agent interactions in competitive and cooperative situations. In this paper, we present the Ask-First (AF) strategy for playing multi-agent non-Iterated PD (nIPD) that is based on evolving trust chains between agents. Each agent maintains a (relatively small) table containing trust values of other agents. When agents are to play each other, they ask their neighbours what trust they put in the opponent. Chains are then followed until an agent is found that knows the opponent and the trust value is propagated back through the chain. The played move is then decided based upon this trust value. When two agents have played each other, they update their trust tables on the basis of the outcome of the game. The strategy is first evaluated in a benchmark scenario where it is shown that it outperforms a number of benchmark strategies. Secondly, we evaluate the strategy in a scenario with a group of colluding agents. The experiments show that the AF strategy is successful here as well. We conclude that the AF strategy is a highly flexible, scalable and distributed way (the chain topology adapts to the way that agents are picked to play each other) to deal with a difficult multi-agent nIPD problem (i.e., robust against collusions). |