Notice: Undefined offset: 0 in /home/web/Documents/EPCL/includes/header.inc.php on line 23

Notice: Array to string conversion in /home/web/Documents/EPCL/includes/header.inc.php on line 32

Notice: Array to string conversion in /home/web/Documents/EPCL/includes/header.inc.php on line 34
menu path: Array EPCL

Notice: Undefined index: node_type in /home/web/Documents/EPCL/includes/header.inc.php on line 152

Notice: Undefined index: node_type in /home/web/Documents/EPCL/includes/header.inc.php on line 153
Free University of Bozen - Bolzano Technische Universität Dresden Vienna University of Technology Universidade Nova de Lisboa

EPCL Research Talks in December 2013 at TU Dresden

Wolfgang Dvořák, University of Vienna
Complexity-Sensitive Decision Procedures for Abstract Argumentation
Joint work with: Matti Järvisalo, Johannes Peter Wallner, Stefan Woltran
Tuesday, 17.12.2013, 9:30, INF 2101

Abstract: Abstract argumentation frameworks (AFs) provide the basis for various reasoning problems and efficient evaluation of AFs has been identified as an important research challenge. So far, implemented systems for evaluating AFs have either followed a straight-forward reduction-based approach or been limited to certain tractable classes of AFs. In this work, we present a generic approach for reasoning over AFs, based on the novel concept of complexity-sensitivity. Establishing the theoretical foundations of this approach, we derive several new complexity results for preferred, semistable and stage semantics which complement the current complexity landscape for abstract argumentation, providing further understanding on the sources of intractability of AF reasoning problems. The introduced generic framework exploits decision procedures for problems of lower complexity whenever possible. This allows, in particular, instantiations of the generic framework via harnessing in an iterative way current sophisticated Boolean satisfiability (SAT) solver technology for solving the considered AF reasoning problems. First experimental results show that the SAT-based instantiation of our novel approach outperforms existing systems.

Wolfgang Dvořák, University of Vienna
Uniform Price Strategies to Exploit Positive Network Externalities
Joint work with: Ludek Cigler, Monika Henzinger, Martin Starnberger
Tuesday, 17.12.2013, 14:00, INF 1004

Abstract: Assume a seller wants to sell a digital product in a social network where nodes represent clients and edges represent a friend-like relationship between them. Assume further that the value of the item for a buyer has positive network externalities, i.e., it is a monotone function of the set of neighbors that already have the item. The goal of the seller is to maximize his revenue. Previous work on this problem studies the case where clients are offered the item in sequence and have to pay personalized prices. This is highly infeasible in large scale networks such as the Facebook graph: (1) Offering items to the clients one after the other consumes a large amount of time, and (2) price-discrimination of clients could appear unfair to them and result in negative client reaction or could conflict with legal requirements. On the other side, offering the same price to every client significantly reduces the seller's revenue. Thus, we study settings where we limit the duration of the selling process and the amount of price discrimination. Specifically, the item is offered in parallel to multiple clients at the same time and at the same price. This is called a round. We show that with O(log n) rounds, where n is the number of clients, a constant factor of the revenue with price discrimination can be achieved and that this is not possible with o(log n) rounds. Moreover we show that it is APX-hard to maximize the revenue even if the externalities in the clients' valuation functions are very restricted, and we give constant factor approximation algorithms for various further settings of limited price discrimination.


Last update:   Wed, 11 Dec 2013 13:35:21