1 //
2 // This file is part of Gambit
3 // Copyright (c) 1994-2016, The Gambit Project (http://www.gambit-project.org)
4 //
5 // FILE: src/tools/enummixed/enummixed.cc
6 // Compute Nash equilibria via Mangasarian's algorithm
7 //
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 2 of the License, or
11 // (at your option) any later version.
12 //
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 // GNU General Public License for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 //
22
23 #include <cstdlib>
24 #include <unistd.h>
25 #include <getopt.h>
26 #include <iostream>
27 #include <fstream>
28 #include <cerrno>
29 #include <iomanip>
30
31 #include "gambit/gambit.h"
32 #include "gambit/nash/enummixed.h"
33
34 using namespace Gambit;
35 using namespace Gambit::Nash;
36
37 template <class T> void
PrintCliques(const List<List<MixedStrategyProfile<T>>> & p_cliques,shared_ptr<StrategyProfileRenderer<T>> p_renderer)38 PrintCliques(const List<List<MixedStrategyProfile<T> > > &p_cliques,
39 shared_ptr<StrategyProfileRenderer<T> > p_renderer)
40 {
41 for (int cl = 1; cl <= p_cliques.size(); cl++) {
42 for (int i = 1; i <= p_cliques[cl].size(); i++) {
43 p_renderer->Render(p_cliques[cl][i],
44 "convex-" + lexical_cast<std::string>(cl));
45 }
46 }
47 }
48
PrintBanner(std::ostream & p_stream)49 void PrintBanner(std::ostream &p_stream)
50 {
51 p_stream << "Compute Nash equilibria by enumerating extreme points\n";
52 p_stream << "Gambit version " VERSION ", Copyright (C) 1994-2016, The Gambit Project\n";
53 p_stream << "Enumeration code based on lrslib 6.2,\n";
54 p_stream << "Copyright (C) 1995-2016 by David Avis (avis@cs.mcgill.ca)\n";
55 p_stream << "This is free software, distributed under the GNU GPL\n\n";
56 }
57
PrintHelp(char * progname)58 void PrintHelp(char *progname)
59 {
60 PrintBanner(std::cerr);
61 std::cerr << "Usage: " << progname << " [OPTIONS] [file]\n";
62 std::cerr << "If file is not specified, attempts to read game from standard input.\n";
63 std::cerr << "With no options, reports all Nash equilibria found.\n\n";
64
65 std::cerr << "Options:\n";
66 std::cerr << " -d DECIMALS compute using floating-point arithmetic;\n";
67 std::cerr << " display results with DECIMALS digits\n";
68 std::cerr << " -D don't eliminate dominated strategies first\n";
69 std::cerr << " -L use lrslib for enumeration (experimental!)\n";
70 std::cerr << " -c output connectedness information\n";
71 std::cerr << " -h, --help print this help message\n";
72 std::cerr << " -q quiet mode (suppresses banner)\n";
73 std::cerr << " -v, --version print version information\n";
74 exit(1);
75 }
76
main(int argc,char * argv[])77 int main(int argc, char *argv[])
78 {
79 int c;
80 bool useFloat = false, uselrs = false, quiet = false, eliminate = true;
81 bool showConnect = false;
82 int numDecimals = 6;
83
84 int long_opt_index = 0;
85 struct option long_options[] = {
86 { "help", 0, NULL, 'h' },
87 { "version", 0, NULL, 'v' },
88 { 0, 0, 0, 0 }
89 };
90 while ((c = getopt_long(argc, argv, "d:DvhqcSL", long_options, &long_opt_index)) != -1) {
91 switch (c) {
92 case 'v':
93 PrintBanner(std::cerr); exit(1);
94 case 'd':
95 useFloat = true;
96 numDecimals = atoi(optarg);
97 break;
98 case 'D':
99 eliminate = false;
100 break;
101 case 'L':
102 uselrs = true;
103 break;
104 case 'h':
105 PrintHelp(argv[0]);
106 break;
107 case 'c':
108 showConnect = true;
109 break;
110 case 'S':
111 break;
112 case 'q':
113 quiet = true;
114 break;
115 case '?':
116 if (isprint(optopt)) {
117 std::cerr << argv[0] << ": Unknown option `-" << ((char) optopt) << "'.\n";
118 }
119 else {
120 std::cerr << argv[0] << ": Unknown option character `\\x" << optopt << "`.\n";
121 }
122 return 1;
123 default:
124 abort();
125 }
126 }
127
128 if (!quiet) {
129 PrintBanner(std::cerr);
130 }
131
132 std::istream* input_stream = &std::cin;
133 std::ifstream file_stream;
134 if (optind < argc) {
135 file_stream.open(argv[optind]);
136 if (!file_stream.is_open()) {
137 std::ostringstream error_message;
138 error_message << argv[0] << ": " << argv[optind];
139 perror(error_message.str().c_str());
140 exit(1);
141 }
142 input_stream = &file_stream;
143 }
144
145 try {
146 Game game = ReadGame(*input_stream);
147 if (uselrs) {
148 shared_ptr<StrategyProfileRenderer<Rational> > renderer;
149 renderer = new MixedStrategyCSVRenderer<Rational>(std::cout);
150 EnumMixedLrsStrategySolver solver(renderer);
151 solver.Solve(game);
152 }
153 else if (useFloat) {
154 shared_ptr<StrategyProfileRenderer<double> > renderer;
155 renderer = new MixedStrategyCSVRenderer<double>(std::cout,
156 numDecimals);
157 EnumMixedStrategySolver<double> solver(renderer);
158 shared_ptr<EnumMixedStrategySolution<double> > solution =
159 solver.SolveDetailed(game);
160 if (showConnect) {
161 List<List<MixedStrategyProfile<double> > > cliques =
162 solution->GetCliques();
163 PrintCliques(cliques, renderer);
164 }
165 }
166 else {
167 shared_ptr<StrategyProfileRenderer<Rational> > renderer;
168 renderer = new MixedStrategyCSVRenderer<Rational>(std::cout);
169 EnumMixedStrategySolver<Rational> solver(renderer);
170 shared_ptr<EnumMixedStrategySolution<Rational> > solution =
171 solver.SolveDetailed(game);
172 if (showConnect) {
173 List<List<MixedStrategyProfile<Rational> > > cliques =
174 solution->GetCliques();
175 PrintCliques(cliques, renderer);
176 }
177 }
178 return 0;
179 }
180 catch (std::runtime_error &e) {
181 std::cerr << "Error: " << e.what() << std::endl;
182 return 1;
183 }
184 }
185
186
187
188
189
190
191
192
193
194
195