Google-opoly: Your first game

Your first game: Dangling

We are about ready to play Google-opoly. The object of this game is to earn the most money by collecting from a surfer who pays one dollar to the owner of each web page he visits. Before explaining how to own web pages, let’s take a closer look at a Google-opoly game board. A game board, such as the one seen in Figure 1, represents a collection of web pages often called a network. Two things about web pages will be represented on our networks: first, the set of web pages we are considering; and, second, which web pages have links to others. For instance, this web page that you are reading has links to the left. Clicking the link entitled "Introduction" would return you to the introductory page of this article. We will abstract things by representing each web page as a circle (or vertex). When a web page has a link that you could select to take you to another web page, we will draw an arrow (or directed edge) between the circles.

In particular, let's look at our first game board as seen in Figure 1. Our network has six web pages. The directed edges indicate how we could move between the web pages by following a link (or hyperlink) on each page. For example, we see that web page 1 has a link to page 4, and web page 4 has links to pages 2, 3, and 5.

Figure 1. The first Google-opoly game board.

As with any game we need to know the rules!

OBJECT Own the web page that is the first to collect $1,000 from the surfer.

SET-UP Each node in the graph represents a web page. Players (from 1 to 6) each choose a web page to own.

RULES

The surfer begins at web page 1. Note, the online game board will color the node that the surfer is currently visiting.
Each player in turn rolls the die. As determined by the number that appears on the die, move the surfer to the next web page according to the rules in Table 1 below.
Whenever the surfer lands on a web page, the page's owner receives $1. A bar chart will keep track of the total amount of money collected by each web page.
The game ends when a web page collects $1,000. If someone owns such a web page, that person wins the game. Note that it is possible for no one to win a given round of the game.

currently at page	roll a 1 visit page	roll a 2 visit page	roll a 3 visit page	roll a 4 visit page	roll a 5 visit page	roll a 6 visit page
1	4	4	4	4	4	4
2	1	1	1	1	1	1
3	1	1	1	1	1	1
4	2	2	3	3	5	5
5	3	3	3	6	6	6
6	6	6	6	6	6	6

Table 1. Rules of Google-opoly for the network in Figure 1.

Let's play the game for a little bit to get a sense of the game as it unfolds. First, let's select web page 1 to own. While the game starts at web page 1, we don't receive a dollar for this as it could be seen as an unfair advantage. A few rolls of the die direct the surfer over this network from web page 1 in the following sequence: 4, 2, 1, 4, 3, 1, 4, 5, 3. At this stage of the game, we have $2 but web page 4 has $3. Right now, web page 4 seems to have been a better choice to own, which is true for this set of rolls. Still, we have a long way to go for one of the web pages to collect $1,000.

Now, it is your turn to play on the interactive applet in Figure 2. Choose a web page to own. Next, begin rolling the die by clicking the roll button. The histogram to the right of the game board graphs the total number of dollars earned by each web page. After 20 rolls how is your web page doing? Do you think you will win? What about after 40 rolls?

Figure 2. The first Google-opoly applet.

Depending on your sequence of rolls, you might not have even needed 20 turns to know if you would win! At some point, every game on this board will result in a roll that moves the surfer to web page 6. Once the surfer visits this page, no other web page will be visited. Such a web page with no outlinks is called a dangling node. So, owning web page 6 essentially guarantees that you will win a round of Google-opoly for this game board. With a proper outlook, you could make this winning conclusion before a single roll of the die. In fact, we can choose a winning web page for any board that contains one dangling node. This is obviously something that needs to be fixed before Google-opoly is a fair (and even fun) game. Before we figure out how to fix it, let's look at another game board to see if there are any more problems.