One approach is to use tried-and-true statistical techniques to build models from user feedback. Often a player will be provided two variations of a game and asked which one was more fun. This input, combined with various other factors (how did the player perform? how many enemies were there in each version?) help construct some sort of classifier to automatically evaluate new game variations.
An alternate approach, which I explored during my Master's research on the topic, was to analyze existing levels in commercially released videogames to construct a model of fun from that, as opposed to considering subjective human feedback. I chose to analyse Super Mario Brothers. It turns out you can see a very characteristic pattern in how the difficult portions of the levels are arranged. This pattern of difficulty takes the form of a rhythmic interplay of difficult and easier portions, and can be nicely described in terms of Flow and the Yerkes-Dodson law. We used this a criterion for evaluating automatically generated levels as a part of a larger system.
The applications of this are pretty wide. Perhaps we could automatically evaluate web page interactions according to a certain model of fun to engage users? Perhaps we can detect when people are not having fun and automatically generate alternate designs?
Instead of proposing some metric for fun that is valid a-priori, we are going to look for the very grounded game-specific correlates of fun and optimize with respect to those. Satisfactorily capturing the entire fuzzy sense of human fun in a finite piece of code is silly, but cataloging the observed feedback for every popular combination of level elements (e.g. "goomba two blocks to the right of a coin block while the player has a fire flower") is both practical and useful for automating level design.
I think you could come up with metrics for interactivity, eg how much of it is 'goldfishing' vs choices that are notably different based on what the other player has done or will do. Dominion is an example where I think you could show that (for many configurations) an AI that ignores opponents actions would still win some significant portion of the time compared to an AI that takes it into account.
If you think of the error function as the combined output of a bunch of "obvious flaw" detectors instead of a "theory of fun", then speculative optimization where the initial conditions come from a human's design under consideration becomes a potentially interesting bit of design automation. Think of design rule checks in CAD with a bit of fuzziness and a default bias -- instead of saying just yes/no, it can say "X might be a better alternative according to the metrics you've enabled in the preference window, consider adopting some of its edits".
Based on this they picked the 16 best criteria and generated games. The fitness function is a score based on the criteria after n amount of automated playthroughs. These generated games tested by humans and they found that the aesthetics criteria and human judgements correlated significantly.
Besides these criteria (they do not describe all criteria in depth but I assume some might be leaning towards being subjective in regards to the programmers preferences) they also add a restriction to how long the planning of a move for a game can take (15 seconds) and discarding the game if it surpasses this. Which as you say can be seen as designing the search space, but the results indicate that they've come up with a way to effectively measure the "fun" factor of the games they came up with.
[1] http://www.cameronius.com/cv/publications/ciaig-browne-maire...
This kind of feedback extracts several more bits of information from the player than a single rating (making better use of them). However, it breaks the applicability of an evolutionary algorithm which treats both artifacts and fitness evaluation as black boxes. If you use a search algorithm that was aware of how the game was built from components, I'm guessing that component-level feedback (being both more objective and more specific) could provide more informative pressure to drive the algorithm than the standard interactive genetic algorithm setup gets.
Disclaimer: I've never used MT. Is this possible?
Unless you want to manually try every iteration and rate it from 1 to 10, this implies that it's possible to come up with a "funness" model of human game playing. That in itself is sort of a interesting thing, falling somewhere between philosophy and psychology, rather than computer science.