Partial-order Boolean games: informational independence in a logic-based model of strategic interaction.
As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players - they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by depe...
| Publicado en: | Synthese Vol. 193; no. 3; pp. 781 - 812 |
|---|---|
| Autores principales: | , , |
| Formato: | Artículo |
| Publicado: |
Springer Nature
Mar2016
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=113040234&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 113040234 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00397857 4LI jtl: Synthese issn: 00397857 maglogo: N pubinfo: dt: Mar2016 vid: 193 iid: 3 pid: 237 pub: Springer Nature artinfo: ui: 113040234 10.1007/s11229-015-0991-y ppf: 781 ppct: 31 formats: fmt: @attributes: type: P size: 657KB tig: atl: Partial-order Boolean games: informational independence in a logic-based model of strategic interaction. aug: au: Bradfield, Julian Gutierrez, Julian Wooldridge, Michael affil: University of Edinburgh, Edinburgh UK University of Oxford, Oxford UK su: Boolean functions Game theory Semantic computing Graph theory Mathematical variables sug: subj: Boolean functions Game theory Semantic computing Graph theory Mathematical variables keyword: Boolean games Concurrency theory Foundations of games Logic ab: As they are conventionally formulated, Boolean games assume that players make their choices in ignorance of the choices being made by other players - they are games of simultaneous moves. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the informational dependencies between variables in a game. More precisely, dependency graphs play two roles. First, when we say that variable x depends on variable y, then we mean that when a strategy assigns a value to variable x, it can be informed by the value that has been assigned to y. Second, and as a consequence of the first property, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs implicitly define a partial ordering of the run-time events in a game: if x is dependent on y, then the assignment of a value to y must precede the assignment of a value to x; if x and y are independent, however, then we can say nothing about the ordering of assignments to these variables-the assignments may occur concurrently. We refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly (IF) logic. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y custom: Synthese is a copyright of Springer, 2016. All Rights Reserved. item: Synthese holder: Springer Nature dt: @attributes: year: 2016 holdings: @attributes: islocal: N |
|---|