@inproceedings{1140,
abstract = {Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental -regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical -regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives. © 2016 ACM.},
author = {Chatterjee, Krishnendu and Dvoák, Wolfgang and Henzinger, Monika and Loitzenbauer, Veronika},
booktitle = {Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science},
location = {New York, NY, USA},
pages = {197 -- 206},
publisher = {IEEE},
title = {{Model and objective separation with conditional lower bounds disjunction is harder than conjunction}},
doi = {10.1145/2933575.2935304},
year = {2016},
}
@inproceedings{1093,
abstract = {We introduce a general class of distances (metrics) between Markov chains, which are based on linear behaviour. This class encompasses distances given topologically (such as the total variation distance or trace distance) as well as by temporal logics or automata. We investigate which of the distances can be approximated by observing the systems, i.e. by black-box testing or simulation, and we provide both negative and positive results. },
author = {Daca, Przemyslaw and Henzinger, Thomas A and Kretinsky, Jan and Petrov, Tatjana},
location = {Quebec City; Canada},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
title = {{Linear distances between Markov chains}},
doi = {10.4230/LIPIcs.CONCUR.2016.20},
volume = {59},
year = {2016},
}
@inproceedings{1182,
abstract = {Balanced knockout tournaments are ubiquitous in sports competitions and are also used in decisionmaking and elections. The traditional computational question, that asks to compute a draw (optimal draw) that maximizes the winning probability for a distinguished player, has received a lot of attention. Previous works consider the problem where the pairwise winning probabilities are known precisely, while we study how robust is the winning probability with respect to small errors in the pairwise winning probabilities. First, we present several illuminating examples to establish: (a) there exist deterministic tournaments (where the pairwise winning probabilities are 0 or 1) where one optimal draw is much more robust than the other; and (b) in general, there exist tournaments with slightly suboptimal draws that are more robust than all the optimal draws. The above examples motivate the study of the computational problem of robust draws that guarantee a specified winning probability. Second, we present a polynomial-time algorithm for approximating the robustness of a draw for sufficiently small errors in pairwise winning probabilities, and obtain that the stated computational problem is NP-complete. We also show that two natural cases of deterministic tournaments where the optimal draw could be computed in polynomial time also admit polynomial-time algorithms to compute robust optimal draws.},
author = {Chatterjee, Krishnendu and Ibsen-Jensen, Rasmus and Tkadlec, Josef},
location = {New York, NY, USA},
pages = {172 -- 179},
publisher = {AAAI Press},
title = {{Robust draws in balanced knockout tournaments}},
volume = {2016-January},
year = {2016},
}
@article{1200,
author = {Hilbe, Christian and Traulsen, Arne},
journal = {Physics of Life Reviews},
pages = {29 -- 31},
publisher = {Elsevier},
title = {{Only the combination of mathematics and agent based simulations can leverage the full potential of evolutionary modeling: Comment on “Evolutionary game theory using agent-based methods” by C. Adami, J. Schossau and A. Hintze}},
doi = {10.1016/j.plrev.2016.10.004},
volume = {19},
year = {2016},
}
@inproceedings{1245,
abstract = {To facilitate collaboration in massive online classrooms, instructors must make many decisions. For instance, the following parameters need to be decided when designing a peer-feedback system where students review each others' essays: the number of students each student must provide feedback to, an algorithm to map feedback providers to receivers, constraints that ensure students do not become free-riders (receiving feedback but not providing it), the best times to receive feedback to improve learning etc. While instructors can answer these questions by running experiments or invoking past experience, game-theoretic models with data from online learning platforms can identify better initial designs for further improvements. As an example, we explore the design space of a peer feedback system by modeling it using game theory. Our simulations show that incentivizing students to provide feedback requires the value obtained from receiving a feedback to exceed the cost of providing it by a large factor (greater than 7). Furthermore, hiding feedback from low-effort students incentivizes them to provide more feedback.},
author = {Pandey, Vineet and Chatterjee, Krishnendu},
booktitle = {Proceedings of the ACM Conference on Computer Supported Cooperative Work},
location = {San Francisco, CA, USA},
number = {Februar-2016},
pages = {365 -- 368},
publisher = {ACM},
title = {{Game-theoretic models identify useful principles for peer collaboration in online learning platforms}},
doi = {10.1145/2818052.2869122},
volume = {26},
year = {2016},
}