Monthly Archives: October 2017

Game Theory and Strategic Thinking

Game Theory and Me

“Game Theory”!? If you know what this is about, you are not alone. If you don’t, you are not alone either. When I tell people that my research is about game theory application in road-bridge transportation network. Reaction from most people are that their facial expression tells me they lost interest about my subject, or they still look at me, but I don’t have any response from them. Sometimes I get frustrated when people lose interest for my topic.  It is not a fun or hot topic like Artificial intelligence(AI) or Game of Thrones. I want to write something of game theory not about my research, but about how to apply game theory to our personal life.

In this field, eleven game-theorists have won the economics Nobel Prize. John Maynard Smith was awarded the Crafoord Prize for his application of game theory to biology. John Nash sets a milestone in the development of game theory.  His major contribution is the definition and properties of Nash equilibrium, which is a crucial concept of a non-cooperative game (and I will discuss below).

“A Beautiful Mind,” is a film based on John Nash life. This is a scene explaining game theory in which Russell Crowe, playing John Nash, is at a bar with three friends. A beautiful blond woman  walks in with four brunette friends. John and his friends are attracted by the blond,  and  his friends joke about which of them would successfully charm the blonde. Surprisely  John Nash concludes they should do the opposite: Ignore her. “If we all go for the blonde,” he says, “we block each other and not a single one of us is going to get her. So we go for her friends, but they will all give us the cold shoulder because nobody likes to be second choice. But what if no one goes to the blonde? We don’t get in each other’s way and we don’t insult the other girls. That’s the only way we win.” This episode gives us example how game theory exits in daily life.

Prisoner’s Dilemma

A simpler example is what is known as the Prisoner’s Dilemma. Two members of a criminal gang are arrested and offered a deal: “If you confess and testify against your accomplice, we’ll let you go and throw the book at the other guy — 20 years in prison.” If both remain quiet, the prosecutors cannot prove the more serious charges and both would spend just a year behind bars for lesser crimes. If both confess, the prosecutors would not need their testimony, and both would get five-year prison sentences.

At first glance, remaining silent might seem the best option. If both did so, both would get off fairly lightly. But as a rational person, which is a basic assumption of game theory, confess is best choice regardless what your accomplice chooses.

This type of problem is called a non-cooperative game, which means the two prisoners cannot communicate with each other. Without knowing what the other person is doing, each is faced with this choice: If he confesses, he could end up with freedom or five years in prison. If he stays quiet, he goes to prison for one year or 20 years.  Prisoner’s dilemma is a widely used example in most textbook of game theory to illustrate the calculation of Nash equilibrium. We will use this example to introduce some concepts of game theory.  In the Prisoner’s dilemma game, two members of a criminal gang are players. Two players game are common, but a game can have more than two players.

Another important concept is payoff. In a game, payoffs are numbers which represent the motivations of players. Payoffs can be in any quantifiable form, from dollar to “utility”. Confess and remain silence are strategies set. In game theory, player’s strategy is any of the options the player can choose in a setting where the outcome depends not only on his own actions but on the actions of others.

Ok, you probably have the question for a while: What is Nash equilibrium? It is the optimal outcome of a game where no player gains anything by unilaterally changing his own strategy, then current set of strategy and corresponding payoff forms a Nash equilibrium. In the Prisoner’s dilemma game, (confess,confess) is the Nash equilibrium, since it is the set of strategies that maximize each player’s payoff given the other prison’s strategy. Also confess is dominant strategy of the game. Rule of thumb: never play a dominated strategy in a game!

A little bit of Game Theory in my life… (to the hymn of Mambo Number 5)

Now we know the basic of game theory. What we can do for our personal life by using it? By wooing a girl in a bar? Or by getting less sentence when we get arrested? These two episodes likely for most people are never-happen-in-real-life. It is not easy to recognize strategic situation and change no-win situation to mutually beneficial outcomes. And you can’t  be a master of game theory with one-day’s lesson, but you don’t need a Ph.D to apply basic game theory in everyday life.

A political scientist and professor at NYU, Bruce Bueno de Meaquita, experimented to purchase car by applying game theory.

Here is his strategy: First, you establish a radius for how far you are willing to travel to buy a car. Then you call a dealer to ask best price. The dealer most of time tell you: You can’t buy a car over the phone.  You should elaborate the conversation to this way: “I know I can buy a car this way, because I know that many cars have been purchased this way. If you do not quote a price for me, I understand that you are telling me that you know you don’t have the best price, I appreciate you saving my time.”

Then you can explain that you will buy a car from whoever gives you the lowest price and you will show up with a check in hand without discussing the price.  A lot of people react by this way: “No way, it is not going to work.” In Bruce’s video, he said he has bought 11 cars using this strategy! One of his students and Irish reporter have uses his strategy and saved thousands on their purchase.

Let’s give a quick analysis for Bruce’s strategy. In this car-purchasing game, dealers you called on the phone are players. To simplify the problem, we assume that there are only two dealers compete in this game. Each leader has two strategies: a higher price or a lower price. If you buy car from dealer offering lower price, another dealer payoff is zero. In the bi-matrix, the first value of inside parenthesis is the payoff of dealer 1 and the second is payoff of dealer 2.  Apparently, if a dealer offers higher price, his incentive is zero. Low price is dominant strategy.

Of course, the reality of car purchasing involves many other factors, but Game theory demonstrates that getting multiple dealer involved is one of the most effective strategies for a car buyer!

If you end up using this approach to help yourself buy a car, please let all of us at the Analytics Lab @ OU know about it!

 

Multi-Drug Resistance in Cancer: Data Analysis for P-glycoprotein Inhibition

Drug efflux and P-glycoprotein

Over time, cancerous cells have the ability to become resistant to treatments such as chemotherapy through several mechanisms. One of them is drug efflux, an otherwise useful body mechanism that protects normal cells by ensuring the intracellular drug concentration stays below a cell-killing threshold. Drug efflux is possible thanks to proteins called transporters, whose function is to transport a variety of substances across cellular membranes.

However, in the case of cancer, drug efflux can become an issue: some transporters are able to carry chemotherapy drugs out of the cancerous cells, thus protecting the cells from being destroyed by the medication. The P-glycoprotein, or P-gp, is one of these transporters. What makes P-gp special is that it can transport many kinds of substrates, which is why an overexpression of P-gp causes multidrug resistance in cancerous cells.

P-gp, like all transporters, is an efflux pump situated on a cell’s membrane. Two kinds of binding domains can be found on P-gp: the Nucleotide Binding Domains, or NBDs, and the Drug Binding Domains, or DBDs (also called TransMembrane Domains, or TMDs). The role of the NBDs is to consume energy by absorbing an energy storage molecule, the Adenosine TriPhosphate, or ATP. This energy is used to power the DBDs, whose role is to pump drugs out of the cell.

Figure 1: P-glycoprotein (original picture from drugdiscoveryopinion.com)

When P-gp expulses drugs out of the cell, it rotates on itself in order to reposition its DBDs and NBDs. This rotation is called P-gp’s catalytic transition cycle. In the initial structure of the protein, the two NBDs (in yellow on the figure) are open to the energy molecules ATP. The DBDs (in blue and green on the figure) are open to the inside of the cell and ready for a substrate to bind to P-gp. When this happens, both the NBDs and the DBDs close in order to hold the ATP and the substrate inside the protein. The substrate is then pushed out of the cell when the DBDs open to the extracellular space. Finally, the energy stored in the ATP molecules is consumed so that P-gp can go back to its initial state. Each structure of the protein during this process is called a pose.

Figure 2: P-glycoprotein’s catalytic cycle

Combination drug therapy

An idea to sensitize cancerous cells to the drugs is to use combination drug therapy. This method consists in using inhibitory drugs to block the transporters’ activity, so that the drugs can remain inside of the cancerous cells long enough to destroy them. It involves looking for candidate molecules capable of blocking a target protein (for example, P-gp). These candidate molecules are those that show strong binding activity towards the target protein.

A chemical compound that binds to the NBD hinders its activities by blocking the access for the energy molecules, thus preventing P-gp from consuming energy. A compound that binds to the DBD can be transported out of the cell by Pg-p. In order to prevent drug efflux, an ideal compound is thus one that binds strongly to the NBDs but weakly to the DBDs.

The role of data analytics

High-Throughput Screening, or HTS, consists in the screening of an entire compound library against the target protein: it is a “real screening” method. HTS allows scientists to test hundreds of thousands of compounds a day by using complex laboratory automation. However, performing HTS is expensive. The solution to this problem is to perform “virtual screening” before performing HTS. Virtual screening is cheaper than real screening, because it does not require access to a laboratory and because it allows compounds that have not been purchased or synthesized yet to be tested. It cannot replace real screening, but it helps to reduce the number of compounds to be tested by real screening. Virtual screening can be performed by software such as AutoDock Vina.

Both the virtual screening and the real screening of compounds generate a large amount of data. While it would be possible to manually select the best compounds among a few tested compounds, this approach seems unconceivable when we know that compound libraries can contain dozens of thousands of compounds. By using data analytics methods to perform a pertinent selection, biologists can save time and money.

The process of identifying promising compounds

The first step towards accomplishing this is to perform virtual screening on a large compound library. The result of this screening is a set of features, such as the binding strength to some specific areas of the target protein, and the value each compound takes for each feature – according to the virtual testing.

A list of promising compounds can be manually extracted from the result of the virtual screening: this selection is done by biologists using their professional knowledge. For example, compounds that seem to bind exceptionally strongly to the NBDs can be selected because they are believed to be effective against P-gp, for the reasons detailed previously. These promising compounds can then be purchased in order to perform real screening and obtain more reliable values and more features, such as the actual efficacy of the compounds against P-gp.

This is where data analytics come into play. The goal here is to build a reliable model, capable of predicting the efficacy of a compound against P-gp using the information contained in the other features. Finally, this model can be applied to the dataset originally obtained by virtual screening. Instead of selecting promising compounds by hand, the biologists can make a decision supported by the model, which predicts as accurately as possible which compounds might be the most effective against P-gp.

Figure 3: Steps of the process

Sources

  1. A Chapron, O.L., Introduction to Drug Discovery. Combinatorial Chemistry Review, 2004-2016.
  2. JP Hughes, S.R., SB Kalindjian and KL Philpott, Principles of early drug discovery. British Journal of Pharmacology, 2011. 162: p. 1239-1249.
  3. G Housman, S.B., S Heerboth, K Lapinska, M Longacre, N Snyder, S Sarkar, Drug Resistance in Cancer: An Overview. Cancers, 2014. 6: p. 1769-1792.
  4. Luqmani, Y., Mechanisms of Drug Resistance in Cancer Chemotherapy. Medical Principles and Practice, 2005. 14: p. 35-48.
  5. Wen Li, H.Z., Yehuda G. Assaraf, Kun Zhaod, Xiaojun Xue, Jinbing Xie, Dong-Hua Yang, Zhe-Sheng Chen, Overcoming ABC transporter-mediated multidrug resistance: Molecular mechanisms and novel therapeutic drug strategies. Drug Resistance Updates, 2016. 27: p. 14-29.
  6. Naqa, I.E., Perspectives on making big data analytics work for oncology. Methods, 2016. 111: p. 32-44.

NSGA-II explained!

Non-dominated sorting genetic algorithm II (NSGA-II)

In this post, I will attempt to explain some basic ideas of multi-objective optimization and the non-dominated sorting genetic algorithm II (known as NSGA-II to it’s friends).  I will also provide an example in Python using the library “inspyred”.

But first let’s talk multiple objectives…

Multi-objective optimization problems deals with conflicting objectives, i.e. while one objective increases the other decreases. There is no a unique global solution but a set of solutions.

In general we are interested in the following mathematical problem type:

\text{ minimize/maximize: } f_m(\textbf x), m = 1,2,\ldots , M
\text{Subject to: } g_j(\textbf x) \geq 0 ,j = 1,2, \ldots , J
h_k(\textbf x) = 0, k=1,2, \ldots , K
x_i^{(L)} \leq x_i \leq x_i^{(U)} ,i=1,2,\ldots , n

A solution is a vector of n decision variables :

\textbf{x}  =  (  x_1 , x_2 ,  \ldots ,  x_n )^T
Furthermore,  the problem is subjected to J inequality constraints and K equality constraints.  Additionally, each variable has an upper and/or lower bound associated with it.

A solution that satisfies all constraints and variable bounds is called a feasible solution. The set of all feasible solutions is called the feasible region, or S.  The term “search space” is also used as a synonym to feasible region. The objective space is constituted by the possible values of the M objectives functions for all solutions in S.

More definitions

Domination 

A solution x(1) is said to dominate the other solution x(2) if both condition 1 and 2 below are true:

  • Condition 1: x(1) is no worse than x(2) for all objectives
  • Condition 2: x(1) is strictly better than x(2) in at least one objective

The mathematical notation for x(1) dominates x(2) is:
x^{(1)} \preceq x^{(2)}

Non-Dominated set:

Among a set of solutions P, the non-dominated set of solutions P are those that are not dominated by any member of the set P

Globally Pareto-optimal set:

The non-dominated set of the entire feasible search space S is the globally Pareto-optimal set.

An example from civil engineering: the design of a cantilever beam. Minimization is performed on the deflection and weight, the decision variables are length and diameter.  The diagram shows the associated objective space: values for deflection and values for weight for different settings of length and diameter.

Figure 1: Weight vs Deflection. Source [1]

From this plot, it is easy to observe the tradeoff between deflection and weight in the Global Pareto-optimal set.

Figure 2: The left plot is the feasible decision variable space and the right is the feasible objective space. Source [1]

In the objective space near the origin in figure 2, a curve is formed, it is the Pareto-optimal front.  No feasible solutions can produce objectives any closer to the origin.  This pareto front represents the best tradeoffs possible.

Now for NSGA-II

NSGA-II is an evolutionary algorithm. Evolutionary algorithms where developed because the classical direct and gradient-based techniques have the following problems when leading with non-linearities and complex interactions:

  • The convergence to an optimal solution depends on the chosen initial solution
  • Most algorithms tend to get stuck to a suboptimal solution.

To understand NSGA-II. It is important to have a fundamental knowledge of genetic algorithms. See the following link https://www.analyticsvidhya.com/blog/2017/07/introduction-to-genetic-algorithm/.

NSGA-II is one evolutionary algorithm that has the following three features:

  1. It uses an elitist principle , i.e. the elites of a population are given the opportunity to be carried to the next generation.
  2. Is uses an explicit diversity preserving mechanism (Crowding distance )
  3. It emphasizes the non-dominated solutions.

It has the following procedure:

  1. Perform a non-dominated sorting in the combination of parent and offspring populations and classify them by fronts , i.e. they are sorted according to an ascending level of non-domination:

Figure 3 : Minimizing f1, f2. Three front levels. Source: [4]

  1. Fill new population according to front raking.
  2. If one front is taking partially like F3, perform Crowding-sort that uses crowding distance that is related with the density of solutions around each solution. The less dense are preferred
  3. Create offspring population from this new population using crowded tournament selection (It compares by front ranking, if equal then by crowding distance), crossover and mutation operators.

Figure 4: Schematic of the NSGA-II procedure. Source [1]

A code using the library “inspyred” will be explained.

Sources:

  1. Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
  2. Chapter 15. Burke, Edmund K., and Graham Kendall. Search methodologies. Springer Science+ Business Media, Incorporated, 2005.
  3. Chapter 6. Deb, Kalyanmoy. Multi-objective optimization using evolutionary algorithms. Vol. 16. John Wiley & Sons, 2001.
  4. Seah, Chun-Wei, Yew-Soon Ong, Ivor W. Tsang, and Siwei Jiang. “Pareto rank learning in multi-objective evolutionary algorithms.” In Evolutionary Computation (CEC), 2012 IEEE Congress on, pp. 1-8. IEEE, 2012.