@inproceedings{1138, abstract = {Automata with monitor counters, where the transitions do not depend on counter values, and nested weighted automata are two expressive automata-theoretic frameworks for quantitative properties. For a well-studied and wide class of quantitative functions, we establish that automata with monitor counters and nested weighted automata are equivalent. We study for the first time such quantitative automata under probabilistic semantics. We show that several problems that are undecidable for the classical questions of emptiness and universality become decidable under the probabilistic semantics. We present a complete picture of decidability for such automata, and even an almost-complete picture of computational complexity, for the probabilistic questions we consider. © 2016 ACM.}, author = {Chatterjee, Krishnendu and Henzinger, Thomas A and Otop, Jan}, booktitle = {Proceedings of the 31st Annual ACM/IEEE Symposium}, location = {New York, NY, USA}, pages = {76 -- 85}, publisher = {IEEE}, title = {{Quantitative automata under probabilistic semantics}}, doi = {10.1145/2933575.2933588}, year = {2016}, } @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 H 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{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}, } @inproceedings{1325, abstract = {We study graphs and two-player games in which rewards are assigned to states, and the goal of the players is to satisfy or dissatisfy certain property of the generated outcome, given as a mean payoff property. Since the notion of mean-payoff does not reflect possible fluctuations from the mean-payoff along a run, we propose definitions and algorithms for capturing the stability of the system, and give algorithms for deciding if a given mean payoff and stability objective can be ensured in the system.}, author = {Brázdil, Tomáš and Forejt, Vojtěch and Kučera, Antonín and Novotny, Petr}, location = {Quebec City, Canada}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Stability in graphs and games}}, doi = {10.4230/LIPIcs.CONCUR.2016.10}, volume = {59}, year = {2016}, } @inproceedings{1324, abstract = {DEC-POMDPs extend POMDPs to a multi-agent setting, where several agents operate in an uncertain environment independently to achieve a joint objective. DEC-POMDPs have been studied with finite-horizon and infinite-horizon discounted-sum objectives, and there exist solvers both for exact and approximate solutions. In this work we consider Goal-DEC-POMDPs, where given a set of target states, the objective is to ensure that the target set is reached with minimal cost. We consider the indefinite-horizon (infinite-horizon with either discounted-sum, or undiscounted-sum, where absorbing goal states have zero-cost) problem. We present a new and novel method to solve the problem that extends methods for finite-horizon DEC-POMDPs and the RTDP-Bel approach for POMDPs. We present experimental results on several examples, and show that our approach presents promising results. Copyright }, author = {Chatterjee, Krishnendu and Chmelik, Martin}, booktitle = {Proceedings of the Twenty-Sixth International Conference on International Conference on Automated Planning and Scheduling}, location = {London, United Kingdom}, pages = {88 -- 96}, publisher = {AAAI Press}, title = {{Indefinite-horizon reachability in Goal-DEC-POMDPs}}, volume = {2016-January}, year = {2016}, } @inproceedings{1327, abstract = {We consider partially observable Markov decision processes (POMDPs) with a set of target states and positive integer costs associated with every transition. The traditional optimization objective (stochastic shortest path) asks to minimize the expected total cost until the target set is reached. We extend the traditional framework of POMDPs to model energy consumption, which represents a hard constraint. The energy levels may increase and decrease with transitions, and the hard constraint requires that the energy level must remain positive in all steps till the target is reached. First, we present a novel algorithm for solving POMDPs with energy levels, developing on existing POMDP solvers and using RTDP as its main method. Our second contribution is related to policy representation. For larger POMDP instances the policies computed by existing solvers are too large to be understandable. We present an automated procedure based on machine learning techniques that automatically extracts important decisions of the policy allowing us to compute succinct human readable policies. Finally, we show experimentally that our algorithm performs well and computes succinct policies on a number of POMDP instances from the literature that were naturally enhanced with energy levels. }, author = {Brázdil, Tomáš and Chatterjee, Krishnendu and Chmelik, Martin and Gupta, Anchit and Novotny, Petr}, booktitle = {Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems}, location = {Singapore}, pages = {1465 -- 1466}, publisher = {ACM}, title = {{Stochastic shortest path with energy constraints in POMDPs}}, year = {2016}, } @inproceedings{1326, abstract = {Energy Markov Decision Processes (EMDPs) are finite-state Markov decision processes where each transition is assigned an integer counter update and a rational payoff. An EMDP configuration is a pair s(n), where s is a control state and n is the current counter value. The configurations are changed by performing transitions in the standard way. We consider the problem of computing a safe strategy (i.e., a strategy that keeps the counter non-negative) which maximizes the expected mean payoff. }, author = {Brázdil, Tomáš and Kučera, Antonín and Novotny, Petr}, location = {Chiba, Japan}, pages = {32 -- 49}, publisher = {Springer}, title = {{Optimizing the expected mean payoff in Energy Markov Decision Processes}}, doi = {10.1007/978-3-319-46520-3_3}, volume = {9938}, year = {2016}, } @article{1333, abstract = {Social dilemmas force players to balance between personal and collective gain. In many dilemmas, such as elected governments negotiating climate-change mitigation measures, the decisions are made not by individual players but by their representatives. However, the behaviour of representatives in social dilemmas has not been investigated experimentally. Here inspired by the negotiations for greenhouse-gas emissions reductions, we experimentally study a collective-risk social dilemma that involves representatives deciding on behalf of their fellow group members. Representatives can be re-elected or voted out after each consecutive collective-risk game. Selfish players are preferentially elected and are hence found most frequently in the "representatives" treatment. Across all treatments, we identify the selfish players as extortioners. As predicted by our mathematical model, their steadfast strategies enforce cooperation from fair players who finally compensate almost completely the deficit caused by the extortionate co-players. Everybody gains, but the extortionate representatives and their groups gain the most.}, author = {Milinski, Manfred and Hilbe, Christian and Semmann, Dirk and Sommerfeld, Ralf and Marotzke, Jochem}, journal = {Nature Communications}, publisher = {Nature Publishing Group}, title = {{Humans choose representatives who enforce cooperation in social dilemmas through extortion}}, doi = {10.1038/ncomms10915}, volume = {7}, year = {2016}, }