MarkMH.github.io/comp.html at main · MarkMH/MarkMH.github.io · GitHub

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
<!DOCTYPE HTML>
<!--
	Basic structure of Strata from HTML5 UP html5up.net | @ajlkn
	Free for private and commercial use under CCA 3.0 license (html5up.net/license)
	Significant customizations by Mark Marner-Hausen
-->
<html>
	<head>
		<title>Webpage Marner-Hausen</title>
		<meta charset="utf-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no" />
		<link rel="stylesheet" href="assets/css/main.css" />
	</head>
	<body class="is-preload">

		<!-- Header -->
			<header id="header">
				<div class="inner">
					<a class="image avatar"><img src="images/IMG_9947.jpg" alt="" /></a>
					<h1><strong>Hi 👋, I'm Mark,<br />
						a Senior ML Engineer <br />
						with scientific background</strong></a></h1>
				</div>
			</header>

		<!-- Main -->
			<div id="main">

				<!-- One -->
					<section id="one">
						<header class="major">
							<h1>Homotopy Methods for solving Non-Degenerate Bimatrix Games</h1>

							<p align="justify" style="text-align:justify"><b>This project explores the homotopy methods described in [Herings, P. J.-J. and Peeters, R. (2010).
								Homotopy methods to compute equilibria in game theory. <i>Economic Theory</i>, 42(1):119–156.], which are
								applied to solve for Nash equilibria in non-degenerate bimatrix games. The homotopy method defines
							    a path that eventually leads to a Nash equilibrium. This path coincides with the
								Lemke-Howson algorithm, which can be implemented by pivoting, i.e.,
								the change of basis for a given system of linear equations. Thus, the search
								for a Nash equilibrium can be represented as a linear complementarity problem, which is solvable.
							</b></p>

							<p align="justify" style="text-align:justify"><b><span class="image left"><img src="images/fulls/comp_01.png" alt="" /></span>
								Consider these two non-degenerate bimatrix games. There are two players, 1 and 2, who can both choose between
								strategy A or B. The entries in the matrices are the players' payoffs for each possible outcome, where
								Player 1's payoff is always on the left side of the comma, while Player 2's payoff is on the right
							    side. The algorithm requires a starting point, which can be an arbitrary strategy of any player. These games
								can be represented by a polyhedron. Traversing its edges leads to a Nash equilibrium. Next let us consider the
								graphical representation of the polyhedron for the simple examples Game 1 and Game 2.
							</b></p>

							<p align="justify" style="text-align:justify"><b><span class="image right"><img src="images/fulls/comp_02.png"  /></span>
								This graph shows the homotopy path after the initial choice of strategy A by Player 1, represented by the blue
								marked line (I). After each step, we must switch between the left side, representing Player 1, and the right side,
								representing Player 2. Therefore, the second step is located on the right side, also in blue and marked (II). After
								six steps, Sigma 1 and Sigma 2 are reached, the Nash equilibrium of Game 1, with Sigma 1 representing Player 1's
								strategy and vice versa. In this example, the mixed strategy Nash equilibrium ((2/3,1/3),(3/4,1/4)) is reached.
								This means that Player 1 plays A 2/3 of the time and B 1/3 of the time, while Player 2 plays A 3/4 of the time and
								B 1/4 of the time. Note that this is the unique Nash equilibrium of Game 1.
							</b></p>

							<p align="justify" style="text-align:justify"><b>
								In contrast, Game 2 has three Nash equilibria, two in pure strategies ((1,0),(1,0)), ((0,1),(0,1)) and one in
								mixed strategies ((1/2,1/2),(1/2,1/2)). If you visit my GitHub repository, you will be able to observe which of
								these Nash equilibria is achieved by the homotopy methods. In fact, it is path-dependent, or more precisely
								initial-stratey-dependent, which Nash equilibrium is reached. The homotopy method, however, is only useful to find
								one Nash equilibrium, but it is insufficient to find all. For example, the mixed strategy equilibrium of Game 2
								is never reached, regardless of the initial strategy chosen. If you would like to try this out for yourself, please
								click Github below and fork the repository. By the way, the algorithm used there is also capable of solving
								more complex games.
							</b></p>
						</header>
					</section>

					<section>
								<ul class="actions fit">
									<li><a href="https://drive.google.com/file/d/1X8aKd9i0quxDz7ok7G2yCvO-xLX3SiUQ/preview" class="button fit">Seminar Paper</a></li>
									<li><a href="https://github.com/MarkMH/homotopy_methods" class="button fit"><i class="icon brands fa-github"></i> Browse Code
									</a></li>
									<li><a href="index.html" class="button fit">Portfolio</a></li>
								</ul>
					</section>
			</div>

				<footer id="footer">
					<div class="inner">
						<ul class="icons">
							<br>
							<li><a href="https://github.com/MarkMH" class="icon brands fa-github"><span class="label">Github</span></a></li>
							<li><a href="https://www.linkedin.com/in/mark-marner-hausen-854a3a117/" class="icon brands fa-linkedin"><span class="label">LinkedIn</span></a></li>
						</ul>
						<ul
						<li><br> Mark Marner-Hausen <br />
							</p>
						</ul>
					</div>
				</footer>

		<!-- Scripts -->
			<script src="assets/js/jquery.min.js"></script>
			<script src="assets/js/jquery.poptrox.min.js"></script>
			<script src="assets/js/browser.min.js"></script>
			<script src="assets/js/breakpoints.min.js"></script>
			<script src="assets/js/util.js"></script>
			<script src="assets/js/main.js"></script>

	</body>
</html>