# An Application of Linear Programming in Game Theory

I took the Combinatorial Optimization class at AIT Budapest (Aquincum Institute of Technology) with David Szeszler, a Professor at the Budapest University of Technology and Economics. We touched on some Graph Theory, Linear Programming, Integer Programming, the Assignment Problem, and the Hungarian method. My favorite class in the course was focused on applying Linear Programming in Game Theory. I’ll summarize the most important aspects of that class in this blog post. I hope this piques your interest in Game Theory (and in attending AIT).

### Basics of Linear Programming

First, I want to touch on some topics in Linear Programming for those who don’t know much about setting up a linear program (which is basically a system of linear inequalities with a maximization function or a minimization function). You can skip this section if you are confident about the subject.

Linear Programming is basically a field of mathematics that has to do with determining the optimum value in a feasible region. In determining the optimum value, one of two questions can be asked: find the minimum point/region or find the maximum point/region. The feasible region in a linear program is determined by a set of linear inequalities. For a feasible region to even exist, the set of linear inequalities must be solvable.

A typical linear program is given in this form: $max\{cx: Ax \leq b\}$. $c$ is a row vector of dimension $n$. $A$ is an $m \times n$ matrix called the incidence matrix. $x$ is a column vector of dimension $n$. This is called the primal program. The primal program is used to solve maximization problems. The dual of this primal program is of the form $min\{yb: yA = c, y \geq 0\}$. $b, A, c$ are the same as previously defined. $y$ is a row vector of dimension $m$. This is called the dual program. The dual is just a derivation of the primal program that is used to solve minimization problems.

Having introduced primal and dual programs, the next important theory in line is the duality theorem. The duality theorem states that $max\{cx: Ax \leq b\}$  = $min\{yb: yA=c, y \geq 0\}$. In other words, the maximum of the primal program is equal to the minimum of the dual program (provided that the primal program is solvable and bounded from above). Using this “tool”, every minimization problem can be converted to a maximization problem and vice versa (as long as the initial problem involves a system of linear inequalities that can be set up as a linear program with a finite amount of linear constraints and one objective function).

There are linear program solvers out there (both open-source and commercial). Most linear program solvers are based on the simplex method. I acknowledge that the summary of Linear Programming given here is devoid of some details. Linear programming is a large field that cannot be  wholly summarized in a few sentences. For more information on linear programming,  check out this wikipedia page.

### Sample Game Theory Problem

Suppose that I and my roommate Nick are playing a game called Yo!. The game rules are as follows: if we both say Yo!, I get $2. If I say Yo! but Nick says YoYo!, I lose$3. On the other hand, if we both say YoYo!, I get $4. If I say YoYo! but Nick says Yo!, I lose$3. The rules are summarized in the table below:

 Daniel Nick Yo! YoYo! Yo! $2$-3 YoYo! $-3$4

The values make up the payoff matrix. When Daniel gains, Nick loses. When Nick gains, Daniel loses. A negative value (e.g. $-3) indicates that Daniel loses but Nick gains. Now the question surfaces: is there a smart way of playing this game so that I always win? Of course, if I could predict Nick’s next move all the time, then I’ll certainly play to win. But I can’t. I must come up with a strategy that reduces the risk of me losing to a minimum and increases my chance of winning. In other words, I want to maximize my minimum expected value. So I wish to know how often I should say Yo! and how often I should say YoYo!. This problem is equivalent to trying to find a probability column vector of dimension 2 (for the two possible responses Yo!, YoYo!). Such a probability vector is called a mixed strategy. For example, a mixed strategy for Daniel could be the column vector: $(1/4 \ 3/4)^T$. This translates to saying YoYo! three-quarters of the time and saying Yo! a quarter of the time. My expected value is then $1/4*2 + 3/4*(-3) = -7/4$. This mixed strategy doesn’t seem optimal! In fact, it’s not as we’ll see later! This kind of Game Theory problem where we wish to obtain an optimal mixed strategy for the Column player (in this case, Daniel) and an optimal mixed strategy for the Row player (in this case, Nick) is called a Two-player, zero sum game. A mixed strategy for the Column player is an $n$-dimensional probability vector $x$; that is, a column vector with nonnegative entries that add up to 1. The $i^{th}$ entry of the mixed strategy measures the probability that the Column player will choose the $i^{th}$ column. In any Two-player, zero sum game, the problem is to maximize the worst-case gain of the Column player which is equivalent to finding $max\{min(Ax) : x$ is a probability vector $\}$ where $A$ represents the payoff matrix Analogously, the problem of minimizing the worst-case loss of the Row player is equivalent to finding $min\{max(yA) : y$ is a probability vector $\}$ where $A$ is the payoff matrix There’s a theorem that states that $max\{min(Ax) : x$ is a probability vector $\}$$min\{max(yA) : y$ is a probability vector $\}$ = $\mu$. We call $\mu$ the common value of the game. This theorem is called the Minimax Theorem. ### Minimax Theorem The Minimax Theorem was proved by John von Neumann (one of the greatest polymaths of all time, I think). It states that “For every two-player, zero sum game the maximum of the minimum expected gain of the Column player is equal to the minimum of the maximum expected losses of the Row player”. In other words, there exists the optimum mixed strategies $x$ and $y$ for the Column player and the Row player respectively and a common value $\mu$ such that 1. No matter how the Row player plays, $x$ guarantees an expected gain of at least $\mu$ to the Column player and 2. No matter how the Column player plays, $y$ guarantees an expected loss of at most $\mu$ to the Row player ### Solving the Two-Player, Zero Sum Game Now let’s try to solve the Yo! game. First, we aim to obtain the mixed strategy for the Column player. Let $x$ be the mixed strategy where $x = (x_1, x_2)^T$ for which $x_1, x_2 \geq 0$ and $x_1 + x_2 = 1$. We wish to find the maximum of $min(Ax)$ where $A$ is the payoff matrix. To make this into a linear program, we can say $\mu = min(Ax)$. So $\mu$ is worst-case gain of Daniel. We wish to maximize $\mu$. Since $\mu$ is the minimum possible value of $Ax$, we obtain the following linear constraints • $2x_1-3x_2-\mu \geq 0$ • $-3x_1+4x_2-\mu \geq 0$ • $x_1 + x_2 = 1$ • $x_1, x_2 \geq 0$ Solving the linear program gives us $x_1=7/12, x_2=5/12$ and $\mu = -1/12$. So the optimal mixed strategy for the Column player is $x = (7/12 \ 5/12)^T$. This translates to saying that if Daniel says Yo! $7/12$ of the time and YoYo! $5/12$ of the time, his worst-case gain will be $-1/12$. In other words, Daniel will lose at most $1/12$ the value of the game no matter how Nick plays. According to the minimax theorem, this is optimal. Note that this doesn’t mean that Daniel will always lose the game but that he can lose by at most $1/12$ the value of the game. If Nick doesn’t play optimally (Nick doesn’t use his optimal mixed strategy), Daniel will most likely win! Nick could obtain his optimal strategy by solving the dual of the primal program to obtain the vector $y$ which will be his optimal mixed strategy. The minimax theorem is an interesting and very useful application of Linear Programming in Game Theory. Two-player, zero sum games can also be solved using Nash Equilibrium which is very closely related to the minimax theorem but applies to two or more players. Nash Equilibrium was first proposed by John Nash. There are many Two-player games including Poker, Card games, Betting games, and so on. As a result, Linear Programming is used in the Casino! # HTML Parsers: The Journey to a More Semantic yet Forgiving Web HTML5 is the next major revision of the html standard. If all works well, it should become the dominant markup in the nearest future ousting both html4 and xhtml1 from their cozy locations. A lot of people say HTML5 is the next big thing. In some sense, yes. But in another no. HTML5 isn’t another different markup language. It’s a specification that adds on to and removes some features from the already existing specifications for html4. It’s the next big thing in that it’s going to change the way we markup our html pages; it’ll add more meaning to elements making html pages more semantic. Apart from making the web more semantic html5 will also standardize a lot of features across major browsers. Finally, there’s going to be some elements that all browsers will implement and it would hopefully function the same way across these browsers. No browser will be left out including IE. Now, the ie6 death count down might even run faster. Check out the ie6 count down website at: http://www.ie6countdown.com/. Ok, that’s html5. What of xhtml1 and html4? Do they still exist and will they still exist? They still hang around and will for a while until all the browsers are standardized and old browser start to weather off. All the html (and xhtml1) standards have parsers implemented in most non-trivial languages used frequently on the web to power web applications. There are xhtml1 and html4 parsers implemented in php, ruby, c++, and others. Most parsers use the libxml library in c to build and traverse the dom. It’s made for xml so the parser is very strict. The documentation and code for Libxml lives at: http://xmlsoft.org/. So libxml is appropriate for parsing xml but not for parsing the transitional versions of any html or xhtml. It’s not even appropriate for html5. HTML5 allows for some laxity on the side of the developer. That’s why there are parsers made specifically to parse HTML5 and no xhtml or html4 parser can appropriately parse HTML5. It’s different and COOL!! HTML5 includes some new tags in its spec: <article>, <aside>, <header>, <section>, to mention a few. All these tags make html pages more descriptive, correspondingly making the web more semantic. These new tags will make development and deployment of web bots easier because now web bots can identify the different parts of a page and know what the data contained within the different page elements represent. They’ll now know if a writing is an article (stand-alone), if it’s just tangentially related to it’s surrounding content, if it’s a header section, and even how to outline the headers (using hgroup), and so on. For more information on the semantics of the new html5 tags and their use, please see Dive into HTML5. I think it’s a really practical and non-trivial guide to the new and emerging HTML5 specification. These new tags alone could throw the already existing parsers for html4 and xhtml off the edge. But there’s more complication to the work html5 parsers must handle. HTML5 is so FORGIVING! The <head>, <html>, and <body> tags which were required in the previous html specifications are now IMPLIED! That means that your web html5 page need not use these pivotal tags at all. You can have a page that looks like this:  <li>My boy is coming  The above markup is represented the same way in dom as this: <html> <head> </head> <body><li>My boy is coming</li> </body> </html>  THOSE PIVOTAL ALL-IMPORTANT CAN’T-DO-WITHOUT TAGS ARE NOW IMPLIED. It seems like a mess but it’s not. Since every page will have to have these tags why not just help the author of the page define those tags as the page is read into the DOM? HTML5 parsers have to handle this situation. Soon, you’ll see how the HTML5 parsers handle these weirdo syntax. HTML5 parsing has been detailed by the WHATWG group to help authors of HTML5 parsers build effective parsers. The group explains how to parse html5 documents. This document is very important to html parser authors and should be used progressively since the html5 specification is still changing (will not fixed for some time I assure you). This document is so detailed. It veers into the input stream and even the character encodings that the html5 parser should be able to handle. That’s why it didn’t take long for html5 parsers to spring up. One prominent suite of html5 parsers implemented in multiple languages is the HTML5lib. There are currently python, php, and ruby implementations available for download. Only the python version, though, is still being actively developed. The ruby version is dead while the php version is still in it’s alpha release state, I think. On the other hand, the html5lib has been ported to javascript/node.js. But this seems to be an event-driven parser. So it might be a SAX (Simple API for XHML) and not a DOM parser (which most people use). The SAX Model is more compatible with node.js since node.js is also event-driven. But event-driven parsers usually stop when malformed syntax is encountered. Errors discourage html authors who most of the time don’t know what the standard is (might change tomorrow). And there’s another port for java programmers (expected, right?); it’s called Validator.nu HTML parser and it contains SAX, DOM, XOM API’s (jack of all trades). There’s no port to functional languages like clojure yet. Awwww… Maybe I’ll port it to clojure. You might ask: what about HTML5 validation? HTML5 validation isn’t really necessary anymore due to the most forgiving syntax of HTML5. What’s there to validate when your page does not even need a root tag? Some time ago, I was playing with some HTML Parsers and comparing how these parsers handle malformed html syntax. My tests were entirely written in php. I fed some malformed syntax to DOMDocument, HTML5lib, and the php simple dom parser. The PHP simple dom parser is basically the DOMDocument PHP parser on steroids. The Simple dom parser allows for easy traversal of the dom. For example, suppose, that you want to find all the image elements in an HTML page. Using DOMDocument library in php, you would write something like document.getElementsByTagName("img");  which returns a NodeList of the image Nodes in the DOM representation of your just created html document. Using the simple html dom, you can do this: $html->find('img') where $html is the root of your document as in document.documentElement ==$html

I cannot show all but some part of the whole rundown and results of tests I ran on the html parsers. I wouldn’t show you in exact terms either. I had some strings containing some well-formed html4-transitional, xhtml-transitional, html5 as well as malformed versions of the aforementioned markups.
 $first = "<html> <body> <h1>My First Heading</h1> <p>My first paragraph.</p> </body> </html>";$second = "<li>Tell me all about ya!"; $third = "<body> <p>I was with you</p> </body>"; Then I ran these html markup through the html5 parser and the DOMDocument library in PHP like this: $dom1 = new DOMDocument("1.0", "utf-8"); $dom1->formatOutput = true;$dom1->loadXML($first); // did the same thing for$second and $third echo$dom1->saveXML(); echo "\n"; 

The above code creates a DOMDocument in XML so the $first and$third html strings pass the test since they are both
valid xml but the $second is malformed. Complains that the <li> tag isn’t matched by its closing tag. $dom3 = DOMImplementation::createDocument(null, 'html', DOMImplementation::createDocumentType("html", "-//W3C//DTD XHTML 1.0 Transitional//EN", "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd")); $dom3->formatOutput = true; $html = $dom3->documentElement; // set up$html strings $html->loadHTML($first); // did the same for $second and$third too. echo $html->saveHTML();  The above snippet creates a document in xhtml1 transitional. Results: $first is valid xhtml1
$second — helps close the <li> tag $third — valid xhtml1 transitional. Puts a <html>  tag but no <head>  tag present.

 $dom2 = DOMImplementation::createDocument(null, 'html', DOMImplementation::createDocumentType("html", "-//W3C//DTD HTML 4.01 Transitional//EN", "http://www.w3.org/TR/html4/loose.dtd"));$dom2->formatOutput = true;
 $html =$dom2->documentElement; // set up $html strings$html->loadHTML($first); // did the same for$second and $third too. echo$html4_document->saveHTML(); 

The above snippet creates a document in html4 transitional.
Results:
$first is valid. $second – since it’s transitional it just helps close the <li> tag
$third – puts the <html> (root) element in the dom but does not put the <head> element. Valid html4 transitional $dom1 = HTML5_Parser::parse($first); // do the same for$ echo $dom1->saveHTML(); echo "\n"; The above snippet uses the HTML5 parser to parse the html strings:$first, $second,$third.
Results:
$first ,$second, \$third passes.
It closes the <li> tag as needed and puts in the <html>, <head>,<body> elements in the DOM when absent.
Nice!

The tests I ran were a more than this and more complex. I stripped some details to make the tests I ran easier to comprehend. Plus, I ran it on the command line. That’s why I use new lines to demarcate individual tests instead of <br> tags.

So we love html5. It’s forgiving. It’s modern. It might eventually replace flash. It’s already on our iphones and smart phones and is implemented in all recent versions of major browsers (including ie). We don’t need to validate our pages again because we know the built-in browser parsers won’t spew out errors (good or bad thing? You be the judge…). We can start using it right away even on older browsers (we can just use modernizr and HTML5shivs to detect if some html5 features are present in a browser). There are tools out there to help us handle old browser! Ain’t that great? We’ve already started our tortuous journey to a more semantic yet forgiving web!

# Most Important Regular Expression for parsing HTML

The usefulness of Regexes (Regular Expressions) is ineffable. Especially in parsing documents, it’s a well-suited and indispensable tool. All good HTML and XML Parsers basically use Regexes to extract cardinal information in HTML documents like names of tags, whether the tag being examined is well-formed, empty, or even malformed by checking the tags against a bunch of rules. Of all the regular expressions needed by a HTML parser, the most important/complex is the one that matches the start tag of an element.

There are a lot of Regular Expression solutions on how to parse HTML tags and attributes. The most popular one (on the Internet that I’ve seen so far) is something like this: "<(\/?)(\w+)[^>]*(\/?)>." This is a non-greedy regular expression that matches both a start and an end tag. For example, it will match a "<pre>" and a "</pre>." It will also match a "<br/>" which is an Empty element. This Regex is so inefficient because it fails to consider a bunch of cases: How would the parser know if the tag is an empty, block, or inline element? How would it know if the tag has attributes and how would it handle these attributes? These questions cannot be answered by using this overly simplistic Regex.

I found a very efficient Regular Expression to parse HTML tags and attributes: /^<(\w+)((?:\s+\w+(?:\s*=\s*(?:(?:"[^"]*")|(?:'[^']*')|[^>\s]+))?)*)\s*(\/?)>/. This Regex makes it easier to not only identify empty tags but also parse the attributes in these tags.This intelligent piece of Regex was in John Resig’s “HTMLparser.js”–a simple HTML parser made by John Resig. At first sight, it seems complicated. But if you look more closely into this Regex, you will notice it simply extracts necessary information about the tag: its tag name, its attributes, and its type (empty or not).

### BREAK DOWN OF THE REGEX

There are three main groups:

• The first group – (\w+) – captures the name of the tag being examined.
• The second group is the largest of the three. It contains sub-groups, most of which are non-matching (groups with ?: are non-matching which means that information about the group wouldn’t be available after the group is matched). This second group matches the attributes in a tag (if there exists any). The group checks for quotes (double or single) around an attribute’s value. It also handles the case where there are  no quotes around the attribute’s value: [^>\s]+ . This also makes sure that the regular expression matching is non-greedy ([^>]* prevents capturing more than one right-angled bracket).
• The third group is (\/?) and it simply checks if the tag being examined is an empty element (like <br/>’s and <hr/>’s).