Problem solving

From Santa Fe Institute Events Wiki

CSSS Santa Fe 2009


Basic representation of problems and solutions

Please email Wendy Ham at for the Netlogo code.

Summary of this baseline model:

  • There are two breeds: problems and solutions
  • Each problem has x components (slider)
  • Each solution has y bits (slider) - y always matches the number of bits in each problem component
  • Match level percentage (slider) is the minimum percentage of bits that must exactly match between each problem component and its solution
  • Solutions search for problems locally (within a spatial region) - if the region switch is on

What will be added to this baseline model:

  • Solutions that have successfully found problem components will be replicated

Mechanisms to be incorporated

Evolution of problems and solutions when there is imperfect match

Dave Brooks:

Problem solving life cycle

Dave Brooks:

Perspective a la Scott Page

Jacopo Tagliabue:

Relationship to disease models

Mahyar Malekpour:


Nathan Hodas:

Diffusion of ideas, learning from neighbors

Nathan Hodas:

Imperfect matching

Margreth Keiler:

Wendy Ham:

Problem solving as a delayed process

Roozbeh Daneshvar: I am in favor of reaching the first results. This is the reason I suggested a simplified (or even an over-simplified) version of the problem. In this version, each problem is one bit (either zero or one) and each solution is also one bit. Hence the sizes of our problem space and solution space are each two.

There is a relation between each problem and each solution. A simple example can be that the solution's value should be the same as problems value. Hence the only solution for 0 is 0 and for 1 is 1. So, my suggestion is to write the first program that finds the relevant solution for each problem.

When we evaluate a solution for a problem, the output is either TRUE or FALSE (or in an extended case, something in between). This process of evaluation does not necessarily show the result immediately. In that case, we have a delayed process. Now, if you want to search in the solution space, you need to take into account that you have some time frames delay. Or if you want to setup a learning process, you need to consider that the relevant effects of your actions are seen in some time steps later.

Knowing when a problem is solved/Knowing which optima (local vs. global) has been reached

Tom Carter: blind alley; knowing when to back out of it

What makes a problem difficult

Tom Carter: When there are more solutions than can be exhaustively checked within a reasonable time limit.

Problems and solutions can combine to form a module (epistasis, "hitchhiking")

Jacopo Tagliabue:

Wendy Ham:

Bayesian learning

Brian Hollar:

Structure evolution and spectrum analysis

Guimei Zhu:

Random walk, Brownian motion

Liliana Salvador

Random thoughts (can be moved to the section above when sufficiently developed)

  • Heuristics
  • Interdependency among bits? (Some problems can be satisfactorily solved with partial solutions, while others require complete solutions. Also, the combination of solutions may matter.)
  • Dimensionalizing problems and solutions may be similar to dimensionalizing knowledge (tacit vs. codifiable, etc) because problems and solutions are just special configurations of knowledge
  • Usually solutions in one field are transplanted into another field as a metaphor rather than literally - how to represent this in the model?
  • Some problems (e.g., the Konigsberg bridge problem) are better solved analytically than through exhaustive search - how to represent this in the model?
  • There are many kinds of difficult problem; what is the difference between a difficult math problem (e.g., the Riemann hypothesis) and the problem of finding a cure for cancer
  • Diffusion as a means of solution broadcasting.
  • Death of solutions/problems.
  • Measuring rate of problems being solved.

Preliminary thoughts (this is an archive - should not be edited further)

I was intrigued by Tom's model of mating and began to wonder whether we can think of problem solving in a similar way. If we were to model problem solving, how would we do it? I'd like to think that problems and solutions are components that combine to generate an emergent property. (After a problem meets a solution--or a solution meets a problem--something new is allowed to emerge. While one instance of problem solving does not exactly create a complex system, many instances may.) That said, there are several questions/considerations to think about before/while we create a proper model of problem solving:

  • Given a population of information/knowledge, how can we identify what are problems and what are solutions?
  • Actually, which comes first: knowledge, information, problems, or solutions?
  • What are some important dimensions of problems and solutions? (These dimensions should inform some kind of a matching probability for problems and solutions.)
  • What is the difference between problems and solutions anyway?
  • What makes certain kinds of problems and solutions "hang out" in a cluster or neighboring clusters? Is this primarily due to path-dependence?
  • When there is a difficult problem (tentatively defined as a problem for which there is no nearby solutions), how can we tell which clusters have the greatest probability of containing the solution(s)? (Can some of the network stuff we learned be of help here?)
  • It is of course important to remember that a problem can have many solutions, and a solution can solve many problems, but that they may have different degrees of affinity (just like a ligand-receptor interaction in molecular biology). Also, occasionally a problem needs a combination of several solutions ("AND" as opposed to "OR").

I would love to hear your thoughts and comments, and I'm hoping that someone may actually share some of my interests in figuring out the answers to the questions above! Wendy Ham

Murad Mithani: We can look at problem solving as a special case of idea generation. See if you find any parallels between what you have in mind to what is written in the creative process.

David Brooks: This matching of past solutions or components to new problems leads to several interesting topics of discussion: (1) Shouldn't the process of developing a solution path be treated as a potentially complex system, (2) How do we describe the process without providing a falsely formulaic structure (3) When is the problem, the set of goals, and the process considered to be identified and what elements of the description may hint to the fragility of understanding? I have quite a bit of experience researching and addressing these issues and can help if this becomes a project.

Bjh singles map.png

Brian Hollar: I've been doing some research for my dissertation on the effects of gender-imbalances on marriage markets and think this would be a fun project to try to model in NetLogo and something that would tie in nicely with Wendy's idea. The basic concept is to try to model the effects of "marriage markets" with more men in them than women or vice-versa, with possible extension to see if this same concept could be expanded to problem-solution matching. Examples of social groups which experience a gender imbalances in marriage markets include: most religious groups, college campuses, some large cities (such as New York and Washington, DC), the African-American community, and some nations (notably China). I am interested in how these gender imbalances affect social norms, marriage and divorce rates, and dating/matching behavior in each of these various groups. Other problem-solution matchings might include: employer-employee, entrepreneur-investor, buyer-seller, etc. If we make the model robust enough, we might be able to extend it to these and other contexts as well.

Some thoughts I have of what to incorporate into the model include:

  • The effects of social capital.
  • Vision (limited ability to see other agents).
  • Open vs. closed groups. (Adjusting rate of entry/exit of agents.)
  • Slider-switch for adjusting sex-ratios.
  • "Tainting effects" for failure.
  • Heterogeneous "attraction" characteristics of each agent.

I'd love to hear ideas anyone might have for this. Nathan Hodas: Brian, don't forget that the minor party has an incentive to wait for the best possible match, and for the majority party, their may not be more fish in the sea, so they must grab what they can get. This will likely produce some skew in the "optimality" of pairing. You could create some measure of compatibility between individuals and see how this measure varies with system parameters.

Wendy Ham: Jacopo Tagliabue shared some interesting thoughts on how to define problems and solutions --> 1) The first one is to define a problem as a lack of knowledge (where knowledge may be theoretical, knowing that, or applied, knowing how) and then use a doxastic logic approach to clarify the notion. The idea is that there is a set of possible states of the world, so-called possible worlds in formal semantic, and our world is one of them: the more you know about the world, the more worlds you can rule out (in the end, with perfect knowledge you will find out which is our world among the infinite set of possibility). You may represent a world as a long description: the set of possible worlds is thus the set pf possible descriptions. Just one of them happens to be THE TRUE description of our world: our tricky task is to find out which one is. For example, since we know that gravity is inversely proportional to distance, we know that all the description saying that gravity is not inversely proportional to distance are false, and cannot be the description of our world. The idea that increasing knowledge means reducing possibilities is analogous to the idea that acquiring information decrease the uncertainties. A problem can be modeled by a set of possible worlds, where each world in the set may actually be the world we live in. A solution is a function from this set to a sub-set of the set (or something similar, I haven't think in depth about this). 2) A second approach may be incorporating some notion from formal learning theorem, where the scientific enterprise is modeled using result from recursion theory (look at this:

Wendy Ham: My thought originally was to use ABM to model a population of problems and solutions by: 1) determining what counts as problems and as solutions, 2) assigning dimensions to problems and solutions, which determine how they subsequently form a cluster in someone's head, and 3) determining how these heads subsequently form a larger cluster of disciplines, 4) demonstrating that compatible problems and solutions can occasionally end up in faraway clusters (such that they need to be brought back together to generate innovation - possibly using random shortcuts a la those found in small world networks). Jacopo's ideas are making me reevaluate these thoughts...

Wendy Ham: (Credit to Nathan Hodas) To be a bit more empirical, it would be interesting to examine a major innovative problem solving event in history that involve the cross-pollination of ideas from several disciplines, e.g., the discovery of the double helix structure, and ask: what kind of structure or system could we have put in place to make such event occur sooner? In other words, what can be done - structurally speaking - to expedite the 'mating' of problems and solutions from traditionally separate fields?

Nathan Hodas: I really like this problem, because it can be attacked in so many ways. Consider the following two problems, which we should also be able to explain: 1) I just got locked out of my room. (a mundane problem) and 2) How do I build a time machine (an impossible problem)?. PS. I'm no longer locked out of my room. problem solved.