I'm a biology amateur, but it seems like sexual selection is almost always performed based on physical characteristics, the outcome of physical contests, or some sort elaborate courtship. But do any non Homo-Sapiens perform sexual selection based on intelligence factors, like problem solving abilities? If so, how does the species accomplish this? I know natural selection as a whole would definitely favor intelligent individuals, but I'm curious if any species actually takes this into account when choosing mates.
Very intresting question. The problem is that animal intelligence is hard to measure not only for scientists, but probably also for the potential mate. Paradoxically, that is why selection for intelligence, if it occurred, may be very strong. One has to be smart in order to recognise smart behaviour, so preference and preferred feature are strongly connected. But that's only my opinion.
Boogert et al., 2011 1 reviews the current knowledge about animal preferences for cognition skills. They conclude that there is very little data on this subject. The given examples are:
1) Preference for elaborating birds songs (as songs are not inborn and have to be learned)
2) Spatial abilities:
In meadow voles (Microtus pennsylvanicus), males with better spatial learning and memory abilities were not only found to have larger home ranges and to locate more females in the field (Spritzer, Solomon, et al. 2005 2) but were also preferred by females in mate-choice tests, even though the females did not observe males’ performance on spatial tests (Spritzer, Meikle, et al. 2005 3).
In guppies (Poecilia reticulata), males that learned faster to swim through mazes to gain a food reward were found to be more attractive to females (Shohet and Watt 2009 4). However, females were not able to see the males’ performance in the mazes. Although male learning ability was weakly correlated with saturation of the orange patches on his body (a sexually selected trait (...)), orange saturation surprisingly did not correlate with female preferences. Thus, the cues leading female guppies to prefer faster learners are unknown.
It is possible, that females base their choose on some factors that correlates with cognitive skills or on total wellness, what may depend on intelligence.
3) bowerbird's abilities to build bowers (courtship constructions):
Comparative studies across bowerbird species have shown that relative brain size is larger in species that build bowers than in closely related nonbuilding species (Madden 2001 5). In addition, relative brain size increases with the species-typical complexity of the bower (Madden 2001 5), and a comparative study on the relative size of specific brain regions showed that species with more complex bowers have a relatively larger cerebellum (Day et al. 2005 6).
4) foraging performance
A recent experiment by Snowberg and Benkman (2009) 7 using red crossbills (Loxia curvirostra) showed that, after observing 2 males extracting seeds from conifer cones, females associated preferentially with the more efficient forager of the 2. The authors were able to exclude female choice for correlated traits by experimentally manipulating foraging efficiency, such that fewer seeds were available in the cones of one of the males. The males were also swapped between treatments (i.e., slow vs. fast forager) so that male identity could not explain the females’ preferences for the most efficient forager.
Another way that intelligence may be favored by sexual selection is "cheating" during courtship. For example most frog species call to attract females. But this signal may also attract aggresive rivals or predators. Some males, especially the weaker ones, do not call but stay near calling individual. This allows them to avoid confrontation and wait for approaching females . The successfulness of this strategy may depend on how "smart" the individual is (only my opinion).
 Bateson P. 1985. Mate choice. Cambridge University Press. 181-210
I know nothing about biology however I did watch an amazing PBS documentary on cuttlefish that I think is fairly relevent.
NARRATOR: During mating, males outnumber the females, sometimes 10 to one. And they're all looking for the chance to pass on their genes. While a female lays eggs beneath a rock, a big male tries to monopolize her, staving off the other hopeful suitors.
Sometimes intimidation alone won't work, and the competitors hurl themselves into a violent and bizarre looking wrestling match.
Like an octopus, they'll squirt out an inky smokescreen when it's time for a hasty retreat.
But size and strength aren't the only ways to impress the ladies.
Thanks to the cuttlefish's skin morphing talents, the smaller males have a clever trick up their sleeve.
MARK NORMAN: The really interesting thing in this system is actually far less obvious, and when you first dive with them, you don't see it. It takes a while before you realize what's going on.
The small males, who have no chance in a contest with a big male, are actually doing something completely different. They're effectively cross-dressing. They're dressing up as a female, by pulling in their webs and putting on this mottled color pattern and gliding past these big, aggressive male, pretending to be a female, and will come in to the female underneath.
And what happens is, as another big male comes in and a potential conflict between these big guys starts up, the sneaker males start mating with her, successfully mate with the female, while the big guy isn't even aware of it.
NARRATOR: The cross-dressers' success is all the more impressive because the females often play hard to get, as Roger Hanlon has seen firsthand.
ROGER HANLON: These females are very picky. They reject 70 percent of approaches for mating. Yet they only reject 30 percent of the cross-dressing males. So this trick gets them in the door, so to speak, past the fighting male, and they're accepted by the female.