Knowledge and Games. Theory and Implementation [PhD Thesis]

Introduction 1
1 Guarding common knowledge 13
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.1.3 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 16
1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.2.1 CSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.2 Graph theory . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.3 Symmetric electoral systems . . . . . . . . . . . . . . . . . 21
1.3 Setting the stage . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.3.1 Pairwise synchronization . . . . . . . . . . . . . . . . . . . 22
1.3.2 Peer-to-peer networks . . . . . . . . . . . . . . . . . . . . . 24
1.3.3 G-symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . 26
1.4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.1 Positive results . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4.2 Negative result . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2 Knowledge in interaction structures 37
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.1.2 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 38
2.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2.3 Properties of knowledge . . . . . . . . . . . . . . . . . . . . . . . 41
2.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4.2 Possible extensions . . . . . . . . . . . . . . . . . . . . . . 48
3 Strategies in interaction structures 51
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.1.2 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 53
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Iterated strategy elimination . . . . . . . . . . . . . . . . . . . . . 55
3.3.1 Completed communication . . . . . . . . . . . . . . . . . . 55
3.3.2 Intermediate states . . . . . . . . . . . . . . . . . . . . . . 59
3.4 Epistemic foundation . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.1 Epistemic language and states . . . . . . . . . . . . . . . . 63
3.4.2 Correctness result . . . . . . . . . . . . . . . . . . . . . . . 64
3.5 Distributed implementation . . . . . . . . . . . . . . . . . . . . . 67
3.5.1 T operator approach . . . . . . . . . . . . . . . . . . . . . 69
3.5.2 Knowledge module approach . . . . . . . . . . . . . . . . . 70
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.6.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.6.2 Possible extensions . . . . . . . . . . . . . . . . . . . . . . 75
4 Epistemic reasoning in computer games 77
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.1.2 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Programming with knowledge . . . . . . . . . . . . . . . . . . . . 79
4.3 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.1 Existing games . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.2 Research . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.4 Potential applications . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Catching the Thief . . . . . . . . . . . . . . . . . . . . . . 84
4.4.2 Adding credence to Assassin’s Creed . . . . . . . . . . . . 86
4.5 Implementation study for Thief . . . . . . . . . . . . . . . . . . . 87
4.5.1 Knowledge module . . . . . . . . . . . . . . . . . . . . . . 87
4.5.2 Expected impact on gameplay . . . . . . . . . . . . . . . . 89
4.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.6.1 Explicit knowledge programming . . . . . . . . . . . . . . 90
4.6.2 Alternatives and extensions . . . . . . . . . . . . . . . . . 91
4.6.3 Cognitive considerations . . . . . . . . . . . . . . . . . . . 92
4.6.4 Final words . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5 Coalition formation: A generic approach 95
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1.1 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
5.1.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.1.3 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 97
5.2 Comparing and transforming collections . . . . . . . . . . . . . . 97
5.3 TU-games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.4 Individual values . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.5 Stable partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.6 Stable partitions and merge/split rules . . . . . . . . . . . . . . . 106
5.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.7.1 Coalitional TU-games . . . . . . . . . . . . . . . . . . . . 109
5.7.2 Hedonic games . . . . . . . . . . . . . . . . . . . . . . . . 112
5.7.3 Exchange economy games . . . . . . . . . . . . . . . . . . 113
5.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
6 Time constraints in mixed auctions 115
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.1.2 Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.1.3 Plan of the chapter . . . . . . . . . . . . . . . . . . . . . . 117
6.2 Bidding language . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.2.1 Transformations and time points . . . . . . . . . . . . . . 118
6.2.2 Valuations . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.2.3 Bids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.2.4 Time constraints . . . . . . . . . . . . . . . . . . . . . . . 120
6.2.5 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
6.2.6 Syntactic sugar . . . . . . . . . . . . . . . . . . . . . . . . 122
6.2.7 Expressive power . . . . . . . . . . . . . . . . . . . . . . . 124
6.3 Winner determination . . . . . . . . . . . . . . . . . . . . . . . . 125
6.3.1 WDP with time constraints . . . . . . . . . . . . . . . . . 125
6.3.2 Original integer program . . . . . . . . . . . . . . . . . . . 127
6.3.3 Modified integer program . . . . . . . . . . . . . . . . . . 128
6.3.4 Valuation for the auctioneer . . . . . . . . . . . . . . . . . 130
6.3.5 Computational complexity . . . . . . . . . . . . . . . . . . 132
6.4 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
6.5 Conclusions and related work . . . . . . . . . . . . . . . . . . . . 134
6.5.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . 134
6.5.2 Possible extensions . . . . . . . . . . . . . . . . . . . . . . 134
7 Outlook 137
Bibliography 141
Index 155
Samenvatting 159
Abstract 161