-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathpure_Nash.wxm
238 lines (169 loc) · 8.2 KB
/
pure_Nash.wxm
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
/* [wxMaxima batch file version 1] [ DO NOT EDIT BY HAND! ]*/
/* [ Created with wxMaxima version 22.04.0 ] */
/* [wxMaxima: comment start ]
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
[wxMaxima: comment end ] */
/* [wxMaxima: title start ]
Reading data
[wxMaxima: title end ] */
/* [wxMaxima: comment start ]
Read from NashData.csv in comma seperated format. (Alter pathname if needed.)
The first row records number of players and their actions. The count of actions starts from 1.
n, a(1), a(2), ...,a(n)
where n is the number of players and a(i) > 0, the number of actions that i_th player may chose.
Rest rows records player, a profile and his reward for that profile. So, it constists of n+2 numbers.
5,8,2,1,3,4,22
Means that the 5th player, when 1st choses his 8th action, 2nd chooses his 2nd, 3nd his first action, forth his 3nd
and himself, as 5th player, his 4th, gets a reward of 22.
So, with n players with a(i) the number of actions of i_th player, the NashData.csv file consists of 1+a(1)*a(2)*...*a(n) rows.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
L:read_nested_list("~/NashData.csv", ",")$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
N:L[1][1]$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
for i:1 thru N do n[i]:L[1][i+1]$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
L:rest(L,1)$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
eval_string(L[1][1])$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
L:rest(L,1)$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
for i in L do block([tmp, last_tmp],
tmp:pop(L),
last_tmp::last(tmp),
tmp:rest(tmp, -1),
arraysetapply (e, tmp, if stringp(last_tmp) then eval_string(last_tmp) else last_tmp)
)$
/* [wxMaxima: input end ] */
/* [wxMaxima: title start ]
Calculations
[wxMaxima: title end ] */
/* [wxMaxima: input start ] */
/* Calculations */
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
The arguments of 'create_list' command vary depending on the number of players. So, the command is evaluated, looping through N, as 'loopE' string that is executed after its creation.
The next loop creates a list of rewards for every player and the profiles he is facing. So, every element of R consist of two lists
[list1, [r1,...,r_ak]]
where list1 as [k, s1,s2, ... (-sk) ...,sn] means that when player k is facing the si_th action of ith other player, (-sk) means the profile that does not include the actions of the player himself, gets reward r1 for his 1st action, r2 for his 2nd and so on till the reward for his last available action ak.
So, [[2,1,2],[17,22]] is from a 3 players game. It means that the player 2 chooses from 2 actions. When he is facing the 1 action of player 1 and action 2 of player 2 [2,1,2], he gets reward 17 for his 1st action and 22 for his 2nd.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
R:[]$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
for ar:1 thru N do (
arguments:[], for i:1 thru N do arguments:append(arguments, [[sconcat(s,i),1,n[i]]]), arguments[ar]:k, arguments:delete(k, arguments),
list_args:[], for i:1 thru N-1 do list_args:append(list_args,arguments[i]), list_vars:makelist(i[1], i, arguments),
smp_args:simplode(list_args,", "),
list_vars:makelist(sconcat("s", i), i, N), list_vars[ar]:k,
smp_vars:simplode(delete(k,list_vars), ", "),
list_vars:append([ar],list_vars),
smp_all_vars:simplode(list_vars, ", "),
mainE:sconcat("[[",ar,",",smp_vars,"],","makelist(e[",smp_all_vars,"], k, 1, n[ar])]"),
loopE:sconcat("create_list(",mainE,", ",smp_args,")"),
R:append(R, eval_string(loopE))
)$
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
For the Best Responses, BR has the same format as list R [list1, list2].
list1 is the same [k, s1,s2, ... (-sk) ...,sn] .
However, list2 consists of the list of indexes of actions that gives the maximum reward.
For example if the rewards [r1,...,r_ak] was [1,3,-2,3] then list2=[2,4].
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
BR:create_list([i[1],sublist_indices(i[2], lambda([x], x = lmax(i[2])))], i, R)$
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
In order to find pure Nash equilibriums 'Nash_find' string is created from 'Nash_loop' and 'member_loop' strings.
[wxMaxima: comment end ] */
/* [wxMaxima: comment start ]
Every profile, so every combination of actions, is checked against Nash equilibrium criteria. So,
'Nash_loop' string is the series of
'for si: 1 thru n[i]' loops for every player from 1 to n.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
Nash:[]$ Nash_loop:""$ member_loop:[]$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
list_vars_0:makelist(concat(s, i), i, N)$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
for ar: 1 thru N do (list_vars:copylist(list_vars_0),
Nash_loop:sconcat(Nash_loop, "for s",ar,": ", 1, " thru n[", ar,"] do
"),
tmp_vars: list_vars,
tmp_vars[ar]: k,
tmp_vars: simplode(delete(k, tmp_vars), ", "),
member_loop: append(member_loop, [sconcat("member(", list_vars_0[ar], ", assoc([",ar, ", ",tmp_vars, "], BR))")])
);
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
For n players, there are needed n checks to see if an action of every players belongs to his best responses.
The 'member_loop' string constracts the nessesary n conditions of the 'if' statement.
Each condition checks if an action of a particular player belongs to the set of his best responses against particular actions of the other players. For examble, member(s2, assoc([2, s1, s3], BR)) condition checks if the s2 action of player 2 belongs to his best responses given that player 1 choses his s1 action and player 3 his s3 action.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
member_loop: concat("if ", simplode(member_loop, " and "), " then
")$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
Nash_find:concat(Nash_loop, member_loop, " ",
" push([",simplode(list_vars_0, ", "),"], Nash)");
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
The calculations end with the evaluation of 'Nash_find' as command and its execution.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
eval_string(Nash_find)$
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Pure Nash equilibriums
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
Nash_rw:[]$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
for x in Nash do (rw:[],
for player: 1 thru N do (
action:x[player],
Rkey:append([player], firstn(x,player-1),lastn(x,N-player)),
Rw:assoc(Rkey,R),rw:append(rw,[Rw[action]])
),
push([x,rw],Nash_rw)
);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
equilibrium:0$
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
equilibrium as [list of actions, list of rewards]
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
for x in Nash_rw do(
equilibrium:equilibrium+1,
disp(" "),display(equilibrium),
disp(x[1], "rewards are "),
for ar:1 thru length(x[2]) do disp(sconcat("player's ", ar ," = ", x[2][ar])),
disp("----------------------------------------------------------------------------")
)$
/* [wxMaxima: input end ] */
/* Old versions of Maxima abort on loading files that end in a comment. */
"Created with wxMaxima 22.04.0"$