42:
is the ability to construct simple building-blocks (e.g. functions or procedures in a programming language), and compose them into larger structures (e.g. more complex functions or programs). This principle is also called
575:
63:
aims to apply the modularity principle to game theory. The main motivation is to make it easier to analyze large games using software tools.
622:
Hedges, Jules; Oliva, Paulo; Sprits, Evguenia; Winschel, Viktor; Zahn, Philipp (2015-06-03). "Higher-Order Game Theory".
591:
Atkey, Robert; Gavranović, Bruno; Ghani, Neil; Kupke, Clemens; Ledent, Jérémy; Nordvall
Forsberg, Fredrik (July 2020).
54:, even complex games are treated as single, monolithic objects. This makes the analysis of games hard to scale.
695:
351:, and returns a real number. Such a game can be represented as a higher-order game as follows. For each player
200:
The term "higher-order" comes from the latter element. The best-response correspondence of each player is a
201:
690:
152:. This function determines, for each combination of actions of the players, what the outcome will be.
656:
623:
553:
571:
476:
76:
666:
604:
563:
84:
39:
27:
469:
319:
499:
525:
684:
552:. LICS '18. New York, NY, US: Association for Computing Machinery. pp. 472–481.
30:, which aims to present large complex games as a composition of simple small games.
670:
51:
23:
550:
Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in
Computer Science
44:
567:
545:
544:
Ghani, Neil; Hedges, Jules; Winschel, Viktor; Zahn, Philipp (2018-07-09).
608:
644:
503:
241:
to the outcome that would result if all players except i play as in s
661:
628:
592:
558:
333:
In a standard game, instead of the selection function, there is a
454:
B, which is a function from X x (Y -> R) to a relation in
204:, as is input is itself a function. Every strategy-profile s
355:, the selection function returns the set of actions from
643:
Bolt, Joe; Hedges, Jules; Zahn, Philipp (2023-10-04).
597:
347:A utility function takes as input an outcome from
87:. Formally, a higher-order simultaneous game for
506:code for constructing and analyzing open games.
461:It is an abstraction of a higher-order game.
8:
593:"Compositional Game Theory, Compositionally"
378:. An open game has the following elements:
464:Open games can be decomposed in two ways:
170:. The selection function takes as input a
16:Branch of game theory and computer science
660:
627:
557:
227:: the function maps each possible action
91:players contains the following elements:
516:
374:The main object of study in CGT is the
7:
539:
537:
362:that maximize the utility of agent
603:. Online, United States: 198–214.
14:
527:Towards compositional game theory
124:as the Cartesian product of all
79:in which players are defined by
303:is contained in the output of
73:higher-order simultaneous game
1:
671:10.32408/compositionality-5-9
310:on the context generated by s
546:"Compositional Game Theory"
443:, which is a function from
421:, which is a function from
271:Given two strategy-tuples s
174:, which is a function from
712:
212:, defines for each player
524:Hedges, Jm (2016-10-03).
475:In parallel - yielding a
468:In sequence - yielding a
131:, and call it the set of
75:is a generalization of a
58:Compositional game theory
20:Compositional game theory
50:In contrast, in classic
568:10.1145/3209108.3209165
249:switches his action to
189:, which is a subset of
185:; and returns a set of
452:best-response function
366:, given the context.
316:best-response relation
645:"Bayesian open games"
202:higher-order function
609:10.4204/eptcs.333.14
489:Bayesian open games.
295:if, for each player
117:(possible actions).
256:. In other words, s
81:selection functions
161:selection function
577:978-1-4503-5583-4
477:simultaneous game
409:strategy profiles
245:, whereas player
133:strategy profiles
85:utility functions
77:Simultaneous game
67:Higher-order game
38:A major theme in
703:
675:
674:
664:
649:Compositionality
640:
634:
633:
631:
619:
613:
612:
588:
582:
581:
561:
541:
532:
531:
521:
500:Open game engine
343:for each player
335:utility function
264:in which player
216:a function from
155:For each player
142:outcome function
102:For each player
40:computer science
28:computer science
711:
710:
706:
705:
704:
702:
701:
700:
696:Category theory
681:
680:
679:
678:
642:
641:
637:
621:
620:
616:
590:
589:
585:
578:
543:
542:
535:
523:
522:
518:
513:
496:
486:
470:sequential game
438:coplay function
372:
360:
341:
320:binary relation
313:
308:
302:
294:
286:
283:, we say that s
278:
274:
259:
254:
244:
239:
232:
221:
207:
194:
179:
168:
129:
111:
83:rather than by
69:
36:
22:is a branch of
17:
12:
11:
5:
709:
707:
699:
698:
693:
683:
682:
677:
676:
635:
614:
583:
576:
533:
515:
514:
512:
509:
508:
507:
495:
494:External links
492:
491:
490:
485:
482:
481:
480:
473:
459:
458:
448:
434:
412:
401:
391:
371:
368:
358:
339:
311:
306:
300:
292:
284:
276:
272:
257:
252:
242:
237:
230:
219:
205:
198:
197:
192:
187:best-responses
177:
166:
153:
138:
137:
136:
127:
109:
100:
68:
65:
35:
32:
15:
13:
10:
9:
6:
4:
3:
2:
708:
697:
694:
692:
689:
688:
686:
672:
668:
663:
658:
654:
650:
646:
639:
636:
630:
625:
618:
615:
610:
606:
602:
598:
594:
587:
584:
579:
573:
569:
565:
560:
555:
551:
547:
540:
538:
534:
529:
528:
520:
517:
510:
505:
501:
498:
497:
493:
488:
487:
483:
478:
474:
471:
467:
466:
465:
462:
457:
453:
449:
446:
442:
439:
435:
432:
428:
424:
420:
417:
416:play function
413:
410:
406:
402:
400:
396:
392:
389:
385:
381:
380:
379:
377:
369:
367:
365:
361:
354:
350:
346:
342:
336:
331:
329:
326:, denoted by
325:
322:contained in
321:
317:
309:
298:
290:
289:best-response
282:
269:
267:
263:
255:
248:
240:
233:
226:
222:
215:
211:
203:
195:
188:
184:
180:
173:
169:
162:
159:, there is a
158:
154:
151:
147:
143:
139:
134:
130:
123:
119:
118:
116:
112:
105:
101:
98:
94:
93:
92:
90:
86:
82:
78:
74:
66:
64:
62:
59:
55:
53:
48:
46:
41:
33:
31:
29:
25:
21:
652:
648:
638:
617:
600:
596:
586:
549:
526:
519:
463:
460:
455:
451:
444:
440:
437:
430:
426:
422:
418:
415:
408:
404:
398:
394:
388:observations
387:
383:
375:
373:
363:
356:
352:
348:
344:
337:
334:
332:
327:
323:
315:
304:
296:
288:
280:
270:
265:
261:
260:defines the
250:
246:
235:
228:
224:
217:
213:
209:
199:
190:
186:
182:
175:
171:
164:
160:
156:
149:
145:
141:
132:
125:
121:
114:
107:
103:
96:
88:
80:
72:
70:
60:
57:
56:
49:
37:
19:
18:
691:Game theory
447:X x R to S;
95:A set R of
52:game theory
24:game theory
685:Categories
662:1910.03656
629:1506.01002
559:1603.04641
511:References
370:Open games
268:operates.
120:We define
45:modularity
34:Motivation
530:(Thesis).
399:outcomes;
376:open game
484:See also
163:denoted
106:, a set
97:outcomes
504:Haskell
262:context
172:context
144:, from
115:choices
574:
456:Σ x Σ.
403:A set
393:A set
382:A set
314:. The
657:arXiv
655:: 9.
624:arXiv
554:arXiv
324:Σ x Σ
318:is a
287:is a
275:and s
61:(CGT)
572:ISBN
291:to s
26:and
667:doi
605:doi
601:333
564:doi
445:Σ x
429:to
407:of
397:of
386:of
301:2,i
299:, s
279:in
234:in
223:to
208:in
181:to
148:to
140:An
113:of
687::
665:.
651:.
647:.
599:.
595:.
570:.
562:.
548:.
536:^
502:-
450:A
436:A
425:x
414:A
345:i.
330:.
71:A
47:.
673:.
669::
659::
653:5
632:.
626::
611:.
607::
580:.
566::
556::
479:.
472:;
441:C
433:;
431:Y
427:X
423:Σ
419:P
411:.
405:Σ
395:Y
390:;
384:X
364:i
359:i
357:X
353:i
349:R
340:i
338:u
328:B
312:1
307:i
305:d
297:i
293:1
285:2
281:Σ
277:2
273:1
266:i
258:1
253:i
251:x
247:i
243:1
238:i
236:X
231:i
229:x
225:R
220:i
218:X
214:i
210:Σ
206:1
196:.
193:i
191:X
183:R
178:i
176:X
167:i
165:d
157:i
150:R
146:Σ
135:.
128:i
126:X
122:Σ
110:i
108:X
104:i
99:.
89:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.