-
Notifications
You must be signed in to change notification settings - Fork 0
/
README
593 lines (397 loc) · 24.5 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
Mathematica Package: TuGames Version 3.1.4
==============================
Contents:
1. Introduction
2. Custom Installation
3. Getting Started
3.1 Basic Example
3.2 Using a different Solver
4. Running the Package in Parallel
4.1 General Procedure
4.2 Running the Cddmathlink libraries in Parallel
5. MATLink and MATtug (Matlab toolbox MatTuGames)
6. Documentation
7. Graphics
8. Acknowledgment
1. Introduction
===============
TuGames is a Mathematica package to determine and to check some
game properties of transferable utility games. It provides more
than 200 different functions to calculate, for instance, (pre-)kernel
elements, the (pre-)nucleolus, the modiclus, the modified and proper modified
pre-kernel, the Shapley value, Lorenz solution, Dutta-Ray solution,
excess payoffs, the tau-value, the vertices of a core, and much more.
Moreover, it verifies if the game is convex, average-convex or superadditive
just to mention some interesting game properties. It can be used in serial
as well as in parallel mode, and in conjunction with MATLink to build up a Matlab
connection to invoke the toolbox MatTuGames. This package is exclusively
dedicated to Mathematica version 12.x and higher, because `TUG-3.0.0` is the first
version that is transcribed to the new collection of algorithms for solving convex problems
introduced in version 12. For Mathematica versions smaller than 12.0 one should use `TUG-2.6.2`.
This version remains compatible with the most recent Mathematica version as long as
ConstrainedMax/ConstrainedMin and LinearProgramming/DualLinearProgramming are supported by Wolfram Research,
otherwise one has to switch to `TUG-3.0.0` or later. In this respect, the graphical
features should run on all platforms. As a highlight, a fast algorithm to seek for a
pre-kernel element is implemented in the updated package. This algorithm is described
in the book
The Pre-Kernel as a Tractable Solution for Cooperative Games
An Exercise in Algorithmic Game Theory
Series: Theory and Decision Library C, Vol. 45
Meinhardt, Holger Ingmar
2014, XXXIII, 242 p. 8 illus., 4 illus. in color
http://www.springer.com/economics/game+theory/book/978-3-642-39548-2
Moreover, we have included a new package called ParaTuGames to literally run the
major commands of TuGames in parallel. Notice that this package has not passed
its stage of development. Hence, the user should use it with care and for testing
only.
In addition, note that these functions/interfaces had to be provided in a Global context
to call the parallel commands of Mathematica within a package. This design requires
that during a running session with ParaTuGames no other variables of Global context
should be defined to avoid name conflicts and wrong results. Though use only the
commands that start with the prefix Para, and which returns a description of how to
use it. To get an idea of its usage, invoke in the panel of the Documentation Center "TUG"
and click then on hyperlink "ParaTuGames Package" to open the file
TUG/Tutorials/ParaExpGamePers12 from the Documentation Center (cf. Section 6).
Finally, this package does not require the configuration procedure as under Section 4.
A modified version of the package CooperativeGames that has been developed
by M. Carter to run properly with Mathematica 12.x and higher is enclosed.
It must be mentioned in this place that some commands of TuGames require
routines that have been provided by the package CooperativeGames. A description
of the package CooperativeGames can be found in
Hal R. Varian, Economic and Financial Modeling with Mathematica,
Telos Springer Publisher,1993, Chapter 8.
Furthermore, if one is interested in computing the vertices of a core
the Mathematica package VertexEnum written by K. Fukuda and I. Mizukoshi
must also be installed on the computer. But note that this function is very
slow in computing all vertices of a core even for modern computers. You can
overcome these shortcomings of VertexEnum by installing the C-library
Cddmathlink written by the same authors to perform the same computational task
more efficiently. It can be found under
https://inf.ethz.ch/personal/fukudak/cdd_home/
for various UNIX, MacOSX and for Window systems. The library is linked via MathLink
with the Mathematica Kernel. Under Linux and Mathematica 11.3 we complied successfully
the binaries using the following compiler flags
MLFLAGS = -lML64i4 -lpthread -lrt -luuid -ldl
See also our post at
http://mathematica.stackexchange.com/questions/59660/any-packages-for-vertex-enumeration-on-mathematica
to overcome possible pitfalls, which might occur during a compilation of the
Cddmathlink binaries.
For Windows and MacOSX Operating Systems pre-build binaries are
available under
ftp://ftp.math.ethz.ch/users/fukudak/cdd/cddlibml_binary/
This C-library is required to use the graphical features of the package.
Notice that the functions that based on this library are activated. To deactivate them
comment in the corresponding lines in the TuGames.m file (cf. Section 2).
In order to install the library, we recommend it to do so in the TUG directory tree.
We have provided several folders that should receive the Cddmathlink executables for
different Operating System ABIs. To retrieve your system ID execute in a Notebook
$SystemID
We have provided some executables for RHEL 7.5, RHEL 8.2, and MacOSX. Unfortunately, we are not
experienced enough under Windows to provide any for those. Thus, we invite the community
to fill that gap and to provide some.
In order check for Mathematica versions smaller than 12.1 the paths where you have to install the Cddmathlink library call
the command
In[1]:= PacletInformation["TUG"]
Out[1]= {Name -> TUG, Version -> 3.1.4, BuildNumber -> , Qualifier -> , WolframVersion -> 12+,
SystemID -> All, Description -> A Mathematica Package for Cooperative Game Theory,
Category -> , Creator -> Holger Ingmar Meinhardt <holger.meinhardt@partner.kit.edu>,
Publisher -> , Support -> , Internal -> False, Location -> /home/kit/xxx/xxxx/.Mathematica/Paclets/Repository/TUG-3.1.4
Context -> {TUG`coop`, TUG`vertex`, TUG`}, Enabled -> True, Loading -> Manual}
To get the same information and beyond that under Mathematica version 12.1, it is required to execute
In[1]:= PacletObject["TUG"][All]
Out[1]= {"Name" -> "TUG", "Version" -> "3.1.4", "WolframVersion" -> "12+",
"Qualifier" -> "", "SystemID" -> All, "Description" -> "A Mathematica Package for Cooperative Game Theory",
"Category" -> Missing["NotAvailable"], "Keywords" -> Missing["NotAvailable"],
"UUID" -> Missing["NotAvailable"],
"Creator" ->
"Holger Ingmar Meinhardt <holger.meinhardt@partner.kit.edu>",
"URL" -> "https://github.com/himeinhardt/TuGames",
"Internal" -> False,
"Context" -> {"TUG`coop`", "TUG`vertex`", "TUG`"},
"Loading" -> Manual, "AutoUpdating" -> False, "Enabled" -> True,
"Location" -> "/home/kit/xxx/xxxx/.Mathematica/Paclets/Repository/TUG-3.1.4"}
or alternatively/
Information[PacletObject["TUG"]]
Then open the directory for Mathematica versions smaller than 12.1 by
SystemOpen@Lookup[PacletInformation["TUG"], "Location"]
or for Mathematica version 12.1 one opens the directory via
SystemOpen@Lookup[PacletObject["TUG"][All], "Location"]
This returns the root directory of TUG, and shows you the three folders
cddmathlink, cddmathlink2 and cddmathlink2gmp that should receive the Cddmathlink
executables.
The author has tested the functions extensively under LINUX x86/64, HP-UX and AIX.
Furthermore, the package was also be installed and tested successfully under Windows XP
and MacOSX. For more recent Windows OS the author has no experience. But the
programming language of Mathematica is system independent, thus, there should no problems
occur on these operating systems to run the basic functions of the package.
2. Custom Installation
======================
Since Version 2.5.1, the package is distributed as a Paclet, which allows a custom installation.
The installation of the package requires about 90 MB free hard-disk space, and the Mathematica
version should not be smaller than 10. For Mathematica versions smaller than Version 10, a manual
installation is requested. In that case one has to follow the guidelines related to the associated
operating system that can be found from the Mathematica documentation.
Notice that `TUG-2.6.2` is the latest version that is compatible with Mathematica versions smaller than 12.0,
and will remain compatible with the most recent Mathematica version as long as ConstrainedMax/ConstrainedMin and
LinearProgramming/DualLinearProgramming are supported by Wolfram Research, otherwise one has to update
to `TUG-3.0.0` or later.
The simplest method is to install the `Paclet` directly from GitHub under Mathematica V12.0 or later
while executing
ResourceFunction["GitHubInstall"]["himeinhardt", "TuGames"]
For smaller versions than 12.0 start Mathematica, open a notebook, and execute therein
PacletInstall["/full/Path/to/TUG-2.6.2.paclet"]
to install TUG-2.6.2 the last version compatible with a Mathematica version smaller than 12.0. That should return the value
Paclet[TUG, 2.6.2, <>]
to indicate a successful installation. Notice that
"/full/Path/to/TUG-2.6.2.paclet"
indicates the directory where the TUG-2.6.2.paclet is located at your hard-disk.
Alternatively, one can directly install the package from GitHub with the help of the Mathematica-Tools from
https://github.com/b3m2a1/mathematica-tools
For doing so, install first the package paclet generator and installer while executing within a running Mathematica session the command
Get["https://github.com/raw/b3m2a1/mathematica-tools/master/PackageDataPacletInstall.m"]
After that, the current version of TuGames can be installed while calling from your notebook
PDInstallPaclet["https://github.com/himeinhardt/TuGames"]
The drawback of the foregoing procedure is that Linux (MacOSX?) users have to change the access permissions of the Cddmathlink executables.
Follow the instructions from Section 1 to locate the Cddmathlink executables on your system after installation. Then change
the file permissions in the associated folders by
chmod 755 cddmathlink
chmod 755 cddmathlink2
chmod 755 cddmathlink2gmp
within a Linux console. After this procedure, your Cddmathlink executables are available on your computer.
In order to use the graphical features of the package, it is recommended to install the Cddmathlink executables
in pre-defined folders as described in Section 1. This C-library must be compiled by yourself if the shipped
executables are not binary compatible with your OS. Windows users should compile it with the help of Cygwin.
If you plan to install these libraries somewhere else, then insert the path to this library in the file TuGames.m
after the line of
:Comments for Windows OS ends:
Notice that this C-library is not necessary to run the package, however, the graphical features are then disabled.
After these steps, the installation procedure is completed, and one can start a session while executing
Needs["TUG`"]
All this does not affect an older installation.
Finally, in order to see how to open the documentation and to run some example we refer the user to Section 6 below.
3. Getting Started
==================
The forthcoming discussion assumes that you have properly installed the files mentioned above on your computer.
3.1 Basic Example
=================
To start with the calculation, we have to load some packages in a first step. This can be done by the following commands.
In[1]:= Needs["TUG`"]
===================================================
Loading Package 'TuGames' for Unix
===================================================
TuGames V3.1.4 by Holger I. Meinhardt
Release Date: 03.06.2024
Program runs under Mathematica Version 12.0 or later
Version 12.x or higher is recommended
===================================================
===================================================
Package 'TuGames' loaded
===================================================
Let us consider a small three-person TU-game. For this purpose define first
the player set
In[2]:= T={1,2,3};
and then the characteristic values through
In[3]:= clv={0,0,0,0,90,100,120,220};
These data are necessary to define the TU-game, which can be accomplished by
In[4]:= ExpGame = DefineGame[T,clv];
After that we are in position to impose some basic operations like
In[5]:= ConvexQ[ExpGame]
Out[5]= True
In[6]:= CoreQ[ExpGame]
Out[6]= True
In[7]:= AverageConvexQ[ExpGame]
Out[7]= True
In[8]:= GameMonotoneQ[ExpGame]
Out[8]= True
In[9]:= ker=Kernel[ExpGame]
170 230 260
Out[9]= {---, ---, ---}
3 3 3
In[10]:= shv=ShapleyValue[ExpGame]
Out[10]= {65, 75, 80}
In[11]:= nc=Nucleolus[ExpGame]
170 230 260
Out[11]= {---, ---, ---}
3 3 3
In[12]:= WeaklyBalancedCollectionQ[ExpGame,nc]
Out[12]= True
In[13]:= prn=PreNucleolus[ExpGame]
170 230 260
Out[13]= {---, ---, ---}
3 3 3
In[14]:= BalancedCollectionQ[ExpGame,prn]
Out[14]= True
In[15]:= prk=PreKernelSolution[ExpGame]
170 230 260
Out[15]= {---, ---, ---}
3 3 3
In[16]:= mnc=Modiclus[ExpGame]
220 220 220
Out[16]= {---, ---, ---}
3 3 3
In[17]:= IsModiclusQ[ExpGame,mnc]
Out[17]= True
3.2 Using a different Solver
============================
Alternatively, one can also supply a different method to check the existence of the core or to find a (pre-)kernel element or the (pre-)nucleolus. This may be useful when one encounters numerical issues, the evaluation lasts too long or with the need to determine an additional (pre-)kernel element. Although, the latter case is not relevant for a three-person game, we nevertheless demonstrate its usage for the above example.
In[18]:= CoreQ[ExpGame,Method->RevisedSimplex]
Out[18]= True
In[19]:= ker=Kernel[ExpGame,CallMaximize->False,Method->CLP]
170 230 260
Out[19]= {---, ---, ---}
3 3 3
In[20]:= nc=Nucleolus[ExpGame,CallMaximize->False,Method->RevisedSimplex]
170 230 260
Out[20]= {---, ---, ---}
3 3 3
In[21]:= prn=PreNucleolus[ExpGame,CallMaximize->False,Method->{InteriorPoint, Tolerance->10^-8}]
1065164637 695287163 1514771007
Out[21]= {----------, ---------, ----------}
18797023 9068963 17478127
In[22]:= WeaklyBalancedCollectionQ[ExpGame,prn]
Out[22]= False
In[23]:= BalancedCollectionQ[ExpGame,prn]
Out[23]= False
In[24]:= prn=PreNucleolus[ExpGame,CallMaximize->False,Method->{InteriorPoint, Tolerance->10^-9}]
170 230 260
Out[24]= {---, ---, ---}
3 3 3
In[25]:= prk=PreKernelSolution[ExpGame,SolutionExact->False,Method->IPOPT]
FindMinimum::sdir: Search direction has become too small.
FindMinimum::sdir: Search direction has become too small.
170 230 260
Out[25]= {---, ---, ---}
3 3 3
In[26]:= mnc=Modiclus[ExpGame,Method->{InteriorPoint, Tolerance->10^-7}]
297599353 80924213 63785847
Out[26]= {---------, --------, --------}
4058173 1103512 869807
In[27]:= IsModiclusQ[ExpGame,mnc]
Out[27]= False
In[28]:= Modiclus[ExpGame,Method->{InteriorPoint, Tolerance->10^-8}]
220 220 220
Out[28]= {---, ---, ---}
3 3 3
Admissible methods for the presented commands CoreQ, Kernel, Nucleolus, PreNucleolus or Modiclus are: RevisedSimplex, CLP, GUROBI, MOSEK, or Automatic. The default setting is Automatic. This option must be used in connection with CallMaximize->False. One can even try Method->{InteriorPoint, Tolerance->10^-7} to get a more precise result whenever one encounters numerical issues. In contrast, admissible methods for the function PreKernelSolution are: Automatic, Newton, ConjugateGradient, PrincipalAxis or IPOPT. Here, one has in addition to set SolutionExact->False to change to the non-default setting.
For more information see TUG/Tutorials/GettingStarted from the Documentation Center (cf. Section 6).
4. Running the Package in Parallel
=================================
4.1 General Procedure
=====================
In order to run the TuGames package in parallel, we recommend putting at least in the Kernel
init.m file a new variable called $ParaMode while setting its value to "False". For doing so, open
the init.m file under "~/.Mathematica/Kernel" by your favorite editor. Windows and MacOSX users should
consult $UserBaseDirectory to find their personal init.m. Then copy the variable
below with its value at the end of your Kernel init.m file, that is,
# init.m
$ParaMode="False";
Now open a notebook to start a Mathematica session. In order to run a session in parallel
at the least the following commands must be invoked from your notebook:
LaunchKernels[]; or LaunchKernels[8]; or any other number reflecting the number of cores you can address.
$KernelCount
Needs["TUG`coop`CooperativeGames`"];
Needs["TUG`TuGames`"];
Needs["TUG`TuGamesAux`"];
$ParaMode="True";
ParallelNeeds["TUG`coop`CooperativeGames`"];
ParallelNeeds["TUG`TuGames`"];
ParallelNeeds["TUG`TuGamesAux`"];
To be sure that everything is distributed correctly, we distribute the definitions of the packages
to all SubKernels.
DistributeDefinitions["TUG`coop`CooperativeGames`*"];
Then define your game using Set[] rather than SetDelayed[], let us say ExpGame, and invoke in addition:
SetSharedVariable[ExpGame];
Moreover, if some of the Mathematica packages which are used by TuGames are located on a different
folder, you probably have to invoke in addition
LaunchKernels[];
....
....
ParallelEvaluate[AppendTo[$Path,"/Path/to/the/required/Packages"]];
ParallelNeeds["TUG`coop`CooperativeGames`"];
ParallelNeeds["TUG`TuGames`"];
....
....
For more information have also a look on the notebook file TUG/Guides/TuGamesParallelMamaV11d3 from
the Documentation Center (cf. Section 6).
4.2 Running the Cddmathlink libraries in Parallel
======================================
If you plan to run even the Cddmathlink libraries in parallel, you have to set an additional variable
to the already set variable $ParaMode in the Kernel init.m file. For doing so, open again the init.m
file under "~/.Mathematica/Kernel" by an editor. Then copy the variable $NotebookMode below with its
assigned value at the end of your Kernel init.m file, that is,
# init.m
$ParaMode="False";
$NotebookMode="True";
Here, we assumed that most people want to use the parallel mode within a notebook. In case that you
mostly use Mathematica from the command line or even on a compute node, then set the value of
the variable $NotebookMode to "False".
In the second step open now a notebook and put to the above commands under 4.1 the additional commands
in between, hence
LaunchKernels[];
.....
.....
Needs["TuGames`"];
ParallelNeeds[$ParaMode="True"];
ParallelNeeds[$NotebookMode="True"];
ParallelNeeds["TUG`coop`CooperativeGames`"];
ParallelNeeds["TUG`TuGames`"];
.....
.....
SetSharedVariable[YourDefinedGame];
In case that you intend to run Cddmathlink libraries in parallel on a compute node or from the command
line, then you have to put into your input file the following commands:
LaunchKernels[];
.....
.....
Needs["TuGames`"] ;
ParallelNeeds[$ParaMode="True"];
ParallelNeeds[$NotebookMode="False"];
ParallelNeeds["TUG`coop`CooperativeGames`"];
ParallelNeeds["TUG`TuGames`"];
.....
.....
SetSharedVariable[YourDefinedGame];
If you encounter problems with the Cddmathlink libraries in parallel, then the following site might also be helpful
http://mathematica.stackexchange.com/questions/25561/how-to-run-an-external-program-in-parallel-with-a-mathematica-package/25818#25818
As an example, also consult the documentation TUG/Guides/TuGamesMovieParaModeV6 from the Documentation Center (cf. Section 6).
5. MATLink and MATtug
=====================
If you want to use MATtug it is necessary to install MATLink from
http://matlink.org
that allows to open a Matlab connection from a running Mathematica session in order to be able
to use the Matlab toolbox MatTuGames that is available under
http://www.mathworks.de/matlabcentral/fileexchange/35933-mattugames
For more information consult TUG/Guides/MATtug from the Documentation Center (cf. Section 6).
6. Documentation
================
Open the Mathematica Documentation Center, and enter into the panel just TUG or guide/InstalledAddOns,
or scroll down, and click at the end of the page at the right corner on the field "Add-ons and Packages". This directs
you to the Documentation of the package from which several examples can be called up, or more detailed information
can be retrieved. From there, one has access to about 230 pages of documentation.
7. Graphics
===========
There are also some graphical capabilities available, which should work under all platforms
whenever the Cddmathlink libraries are installed. Features are for instance: plotting the
core and strong epsilon core skeleton together with the nucleolus, kernel and Shapley value
up to four players.
Consult for more information TUG/Guides/TuGamesView2dV6 or TUG/Guides/TuGamesView3dV6 from
the Documentation Center.
8. Acknowledgment
=================
We are very thankful to Szabolcs Horvát for his helpful support, suggestion of improvements,
and of his piece of advice to follow best practice of publicizing a Mathematica package
that allows a custom installation for everyone. Moreover, we owe him executables for
MacOSX, which ship with this version.
The author acknowledges support by the state of Baden-Württemberg through bwHPC.
Of course, the usual disclaimer applies.
9. License
==========
This project is licensed under the MIT License - see the LICENSE.txt file for details or
https://choosealicense.com/licenses/mit/
Author:
========
Holger I. Meinhardt
Institute of Operations Research
University of Karlsruhe (KIT)
E-mail: Holger.Meinhardt ät wiwi.uni-karlsruhe.de
holger.meinhardt ät partner.kit.edu