Weighted Boolean Formula Games

B. Monien, M. Mavronicolas, K. Wagner, in: The ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, 2015, pp. 49–86.

Download
Restricted 232-chp_3A10.1007_2F978-3-319-24024-4_6.pdf 500.54 KB
Conference Paper
Author
Monien, Burkhard; Mavronicolas, Marios; Wagner, Klaus
Abstract
We introduce weighted boolean formula games (WBFG) as a new class of succinct games. Each player has a set of boolean formulas she wants to get satisfied; the formulas involve a ground set of boolean variables each of which is controlled by some player. The payoff of a player is a weighted sum of the values of her formulas. We consider both pure equilibria and their refinement of payoff-dominant equilibria [34], where every player is no worse-off than in any other pure equilibrium. We present both structural and complexity results:We consider mutual weighted boolean formula games (MWBFG), a subclass of WBFG making a natural mutuality assumption on the formulas of players. We present a very simple exact potential for MWBFG. We establish a polynomial monomorphism from certain classes of weighted congestion games to subclasses of WBFG and MWBFG, respectively, indicating their rich structure.We present a collection of complexity results about decision (and search) problems for both pure and payoff-dominant equilibria in WBFG. The precise complexities depend crucially on five parameters: (i) the number of players; (ii) the number of variables per player; (iii) the number of formulas per player; (iv) the weights in the payoff functions (whether identical or not), and (v) the syntax of the formulas. These results imply that, unless the polynomial hierarchy collapses, decision (and search) problems for payoff-dominant equilibria are harde than for pure equilibria.
Publishing Year
Proceedings Title
the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday
forms.conference.field.series_title_volume.label
LNCS
Page
49-86
LibreCat-ID
232

Cite this

Monien B, Mavronicolas M, Wagner K. Weighted Boolean Formula Games. In: The ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday. LNCS. ; 2015:49-86. doi:10.1007/978-3-319-24024-4_6
Monien, B., Mavronicolas, M., & Wagner, K. (2015). Weighted Boolean Formula Games. In the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday (pp. 49–86). https://doi.org/10.1007/978-3-319-24024-4_6
@inproceedings{Monien_Mavronicolas_Wagner_2015, series={LNCS}, title={Weighted Boolean Formula Games}, DOI={10.1007/978-3-319-24024-4_6}, booktitle={the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday}, author={Monien, Burkhard and Mavronicolas, Marios and Wagner, Klaus}, year={2015}, pages={49–86}, collection={LNCS} }
Monien, Burkhard, Marios Mavronicolas, and Klaus Wagner. “Weighted Boolean Formula Games.” In The ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, 49–86. LNCS, 2015. https://doi.org/10.1007/978-3-319-24024-4_6.
B. Monien, M. Mavronicolas, and K. Wagner, “Weighted Boolean Formula Games,” in the ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, 2015, pp. 49–86.
Monien, Burkhard, et al. “Weighted Boolean Formula Games.” The ´Festschrift´ Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday, 2015, pp. 49–86, doi:10.1007/978-3-319-24024-4_6.
Main File(s)
File Name
232-chp_3A10.1007_2F978-3-319-24024-4_6.pdf 500.54 KB
Access Level
Restricted Closed Access
Last Uploaded
2018-03-21T10:30:47Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar