Unordered constraint satisfaction games

Reference:

Lauri Ahlroth and Pekka Orponen. Unordered constraint satisfaction games. In R. Rovan, V. Sassone, and P. Widmayer, editors, Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012, Bratislava, August 2012), Lecture Notes in Computer Science, pages 64–75, Berlin Heidelberg, 2012. Springer-Verlag.

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).

Suggested BibTeX entry:

@inproceedings{AhOr12,
    address = {Berlin Heidelberg},
    author = {Lauri Ahlroth and Pekka Orponen},
    booktitle = {Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS 2012, Bratislava, August 2012)},
    editor = {R. Rovan and V. Sassone and P. Widmayer},
    language = {eng},
    pages = {64--75},
    publisher = {Springer-Verlag},
    series = {Lecture Notes in Computer Science},
    title = {Unordered constraint satisfaction games},
    year = {2012},
}