@inproceedings{
    AhOr12,
    editor = "Rovan, R. and Sassone, V. and Widmayer, P.",
    author = "Ahlroth, Lauri and Orponen, Pekka",
    series = "Lecture Notes in Computer Science",
    abstract = "We consider two-player constraint satisfaction games on systems of Boolean constraints, in which the players take turns in selecting one of the available variables and setting it to true or false, with the goal of maximising (for Player I) or minimising (for Player II) the number of satisfied constraints. Unlike in standard QBF-type variable assignment games, we impose no order in which the variables are to be played. This makes the game setup more natural, but also more challenging to control. We provide polynomial-time, constant-factor approximation strategies for Player I when the constraints are parity functions or threshold functions with a threshold that is small compared to the arity of the constraints. Also, we prove that the problem of determining if Player I can satisfy all constraints is PSPACE-complete even in this unordered setting, and when the constraints are disjunctions of at most 6 literals (an unordered-game analogue of 6-QBF).",
    il = "no",
    year = "2012",
    keywords = "",
    juforank = "1",
    title = "Unordered constraint satisfaction games",
    eventlocation = "Bratislava, Slovakia",
    booktitle = "Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012, Bratislava, August 2012)",
    note = "",
    unitcode = "T306-99, T312-1",
    impactfactor = "A4",
    eventtime = "August 27-31",
    publisher = "Springer-Verlag",
    volume = "7464",
    address = "Berlin Heidelberg",
    kay = "NA",
    pages = "64--75",
    responsibleauthor = "Ahlroth, Lauri and Orponen, Pekka",
    language = "eng",
    url = "http://dx.doi.org/10.1007/978-3-642-32589-2_9",
    country = "Germany",
    flags = "public copy HIIT"
}