This question is not focussed on video games but games in general. I went to a boardgame trade fair yesterday and asked myself if there is a way to calculate the fairness of a game. Sure, some of them require a good portion of luck, but it might be possible to calculate if some character is overpowered. Especially in role-playing games and trading card games. How, for example, can the creators of "Magic: The Gathering" make sure that there isn't the "one card that beats them all", given the impressive number of available cards?
Yes, it's theoretically possible - that's a good part of the game theory which deals with this subject.
However, it's only rarely practical, and even then mostly just for games which don't involve a randomiser (Chess, Reversi, Go and so on). Combinatorial explosion ensures that the theoretical time needed for such proofs for more complex games like Magic the Gathering can easily be several orders of magnitude longer than the current age of the universe.
In the end, for any non-trivial game you'll likely have to abandon the notion of proving balance or fairness of a game and instead go with a combination of common sense, designer instincts, game system reuse and throughout testing.
Short answer: Any game with a finite, even if undefined, number of available moves thus has a finite number of possible games. Any game with a finite "game tree complexity" can theoretically have all possible games analyzed to determine if the number of games in which each player would win is equal.
Simply put: if Player 1 wins exactly half of all possible plays of a game, the game is balanced. If this is not true, the game is biased towards one player or the other.
However, this simple rule can be quite infeasible to put in practice. Go, for instance, has a game-tree-complexity on the order of 10^170 possible games, more than the number of atoms thought to exist in the known universe. It is thought to be impossible to compile an exhaustive game tree. However, the library of games played and recorded is in the millions, and suggest that the game has a "first-move advantage" (which is typically mitigated with 1.5 points of "komi" given to White).
Contrasting that, even given large overall game-tree-complexities, all M,N,K games (a grid board of M width, N height, in which the object is for a player to create a row of K pieces by placing and never moving/removing them) are solved, because there is a shortcut; entire "branches" of the game tree can be identified as always causing one player or the other to lose. The remaining branches follow a pattern that can be identified. Tic-Tac-Toe is the obvious example; in addition to having only 300,000-ish possible games, there are only 16 in which one player or the other doesn't make a move that will obviously let the other player win on the next move. So, the game-tree starts small and gets smaller when you consider the games the players are actually likely to make.
In games with an element of luck, the game-tree complexity is inflated beyond the number of decisions available to each player. Because the game is no longer played with "perfect information", as it is in chess, checkers, Go, Othello, etc, it is possible for a player who has played perfectly given the known information at the time to still lose to the game's random element. These games have no "solution"; however, there is usually still a finite game tree and so theoretically games could still be analyzed exhaustively. This is still usually not feasible; instead games involving probability are analyzed probabilistically to identify the "best-bet" strategies, and if these strategies are shown to favor the player that uses them, regardless of the strategy used by any other player (including the same strategy), the game can be shown to have bias.
In general, the following rule applies: if the design of the game inherently leads to inequality in one or more of the following, the game has a bias:
Now, the game's design may introduce one inequality but attempt to compensate with another. Or, the game's design may allow for randomness in areas that may produce bias, meaning one game might be biased while another is fairer (games with random starting boards can exhibit this). In these cases only empirical analysis of games between players of roughly equal strength over the long-term can demonstrate any bias.
For more discussion of bias in board games, try the forums of http://www.geekdo.com; there have been several discussions of demonstrated bias in games, and how to avoid said bias in game development in general.
I guess there is no pre-made mathematical formula to evaluate how fair a game is because of how every game is so different and complex.
You can't really compare different game parameters and make up some sort of power score of how good a character is (unless your game is very simple) because they all affect your gameplay differently and depend on how they are implemented (e.g. how can you evaluate how strength relates to vitality? How do you give a numerical value to a character's special attack?).
You have to test your game. A lot. Play your game by yourself and make others play it and store the battle/game results in a file in order to make statistics and evaluate how often certain characters win, under what circumstances, etc. Then, make sure you implement some way to check replays or analyse gameplay in order to see why such a character is overpowered and apply the changes accordingly.
Really, you have no other option than testing. That's one of the reasons why betas exist (e.g. Starcraft2 as a beta gave Blizzard the opportunity to balance the 3 races based on the game results).
To sum up, play your game, and make others play it (starting a beta is an option). See why the game is unbalanced through replays or automated analysis and change what needs to be changed accordingly. That's the only way you'll approach fairness.
To be able to prove a game was balanced or fair, you'd have to define what balanced or fair means first. These are rather vague terms that can encompass a range of things, for example game 'balance' is often taken to mean:
And so on.
In general I am a fan of mathematically proving things like this, but to prove anything through logic or testing you first need to define it clearly. Some aspects of balance are easy to test through mathematics if you're able to understand your game rules properly. Others are much harder to judge without simply conducting empirical tests. The main problem is that most game designers don't truly understand the mechanics of their game, since they usually end up merging game rules into a surrounding simulation, and the latter is very hard to model accurately.
Theoreticaly it is possible, but for most games it is extremely difficult so it can be considered impossible.
One approach: Convert game into normal form. Game in normal form is Set of strategies for each player and function that says how good result is when for given combination of choices. Random factor can be modeled as another player.
Then we can look for dominant/dominated strategies (things to ALWAYS do and things to NEVER do). Game is at lest somehow interesting, if it does not contain dominant strategies.
Then we can look at what each player can guarantee for himself. for each of "MY" choice, look at worst possible outcome and take choice that have this best.
If it differs a lot between players, there is somthing rotten in game.
There are other things to look at (dominant mixed strategy (choosing each choice with some probublity), nash equilibriums (combinations that once all players know others will do, are localy best for everyone)).
But the first step is so extremely complicated for most games, so it's usualy not so usefull. But it can be used if you can absract complicated details away/ replace strategies with recognizable sets of strategies (eg. initial build orders) and result with some statistical aproximation from actualy played games and it can tell you something about problems in game. I guess that something like this blizard does with SC.
Another form of game is game where players takes turns and know everything others do (chess). There you can try to search for dominat strategy by searching state tree of game (and it usualy is HUGE, so again, too complicated to use). And lot of games are without total knowladge and it complicates things a lot.
Another approach, look at things in game and try to compare them.
Another approach: For team combat (esp. with large ammounts participants) you can try to use force on force simulation (I never used it, and it requires high math (diferential equations) and hard work to convert game into aproprite model).
So my conclusion, lot of things can be done to balance subsystems of game, and when game is out (and during betatest), lot can be done by analyzing results, but unless you make everything same, its almost imposible to prove game is balanced.
PS: You can mask sameness by replacing one attribute by multiple that together can be used to compute initial attribute, and by making everything much more random, so players don't see that sameness (
Beware its easy to make mistake in doing so (eg fast small attacks vs big slow attacks), beacuse 18 throws by d6 -18 gives results 0-90, 10 throws by d10-10 gives results 0-90 1 throw by d91-1 gives results 0-90 but all of them have different distributions.
PS2: One wise man said, that actual balance is not important, Percieved balance is.
A lot of good answers about getting a mathematically correct answer, but I'll try a different angle: if your code allows for it, you could simulate a very large number of games and then check if there is a strategy (or strategies) that win too often.
You might be familiar with Monte-Carlo simulations or genetic algorithms. The idea here related. You need an AI to play the game and some key measurement. You let the AI go at each other in a large tournament, often enough, with different starting variables and you measure the results.
I've always wanted to try an approach like that to balances classes/weapons, it would be a ton of fun.
From a theory of computation perspective, it sounds like answering this is not possible in general. It's asking a question about a property of a program and Rice's Theorem may apply. My assumption is that game refers to a program written in a Turing Complete language like c++. I'm also assuming that to calculate or prove whether a game is fair means there exists a c++ program that reads a c++ program (the game program) and terminates in a finite amount of time for all possible inputs, with only two outputs, fair or unfair.
A quick search shows it is possible to have a deterministic yet undecidable game, see slide 7 here and from the International Journal of Game Theory: Some undecidable determined games:
"Computing machines using algorithms play games and even learn to play games. However, the inherent finiteness properties of algorithms impose limitations on the game playing abilities of machines. M. Rabin illustrated this limitation in 1957 by constructing a two-person win-lose game with decidable rules but no computable winning strategies."
The human brain is apparently more "powerful" than computers because we can gain and apply past knowledge and sometimes appear to contradict results like the Halting problem by finding infinite loops in programs. But how we do this is not well known and can't be written precisely and unambiguously in an algorithm.
I really wanted to comment on Martin Sojka's answer, but I don't have the reputation. He is correct that Game Theory includes calculating the fairness of a game (for example, it's an open question if in a chess game where both white and black played perfectly whether it would be a tie).
For MtG it could very well be that it's completely infeasible to calculate whether it's fair, but no one has proven mathematically that the computation would be infeasible.
It might be trivially possible to prove it's fair - if it's random who goes first and everyone plays by the same rules then it's fair. It might be that whoever goes first always wins, but if who goes first is decided fairly then the game is fair.
What is meant by "fair" is vague, let me explain :
Consider the game Rock-paper-cissors (http://en.wikipedia.org/wiki/Rock-paper-scissors) : according to you it is fair, I suppose (according to me as well).
Now, let's consider the game : Rock-paper-cissors-well where the well beats the rock and the paper and the well loses against the paper. Unbalanced, right ? The well seems pretty overpowered : it beats two weapons and loses against one.
But one could say that it is not overpowered at all : because if you know that your opponent is more likely to use the well because it beats two weapons, you can just act by picking the paper more often.
So there is an answer to the potential overpowered well : just choose more often the paper. But then you know that your opponent may know that and may use the paper quite often, so you think you should use the cissors more often. Etc. Not really overpowered, just a different game with different rules.
I would recommend reading about game theory and especially games with imperfect information (http://en.wikipedia.org/wiki/Game_theory).