Video games have been declined the 'Art' label for a long time, but from what I've learnt in those few modules in college, anything can be Art as long as you can explain it, photographs, films, literature, sculpture made up of ordinary objects.
For example if we take Mario.
Super Mario Brothers is a post modern deconstruction of the storytelling genre as a whole, it takes apart the idea of 'Hero' of Greek Origin and replaces it with a fat plumber whose main skill is to Jump.
Another interesting aspect is it's similarity to Buddhism, obviously an inspiration to the Japanese designer who created Mario. There are points, but they mean nothing to the player, you cannot buy anything with the points at most attaining another 'life'.
As Mario traverses through the levels seeking the ultimate goal 'The Princess', he realises that he is always one step behind, facing increasingly harder demons. Along the way he will die and as the player dies, they learn from their mistakes and start again at the beginning similar to the Buddhist concept of reincarnation. No matter how many 'lives' you get, the game never changes, players must constantly seek enlightenment through the endless cycle of 'playing' the game.
Eventually, after going through the existential angst and understanding that there is only one way to Nirvana, the player may finally rescue the Princess and is rewarded with a 'Game Over' screen adding another layer of endless rebirth and death played by millions of people all over the world. Is this really Nirvana? or just a Matrix within a Matrix so to say?
Also the pipes, Toad, the Koopas and Luigi represent repressed homoeroticism.
Go google "post modern MGS2" you'll understand how brilliant Kojima was.
Now go do one for Gears of War or Halo