Must there be teams? Yes. While you can have a few roles that play individually (SK, survivor) the way to catch Mafia resides primarily in analyzing interactions between players. The only true impediment to “acting town” for a mafioso is the idea that they cannot honestly look for scum, as they already know who the scum are. Without that basic tell, you cannot infer affiliation.
Must there be sides?* Yes, in that there must be at least two exclusive win conditions for the game to be non-trivial. The only alternative I can see is if all the mafia were sock puppets run by the mod, and all the human players are town…or something. That doesn’t seem very interesting.
Must there be roles? Beyond win condition? No. You could have a flavorless vanilla game, sure. 8-9 town versus 2 scum as a baseline. It would get old fast, but you could do it.
*Must there be rules? *Yes, although most rules can be tweaked or ignored. The existence of rules is the definition of a game. Even Fluxx has rules.
*How far can things be pushed away from the norm before it stops being mafia? * There is a great deal of design space available, and much of it has not been mined here. I think one key element is to limit exploration to one or two areas, and keep the rest par with expectations.
And how far can they be pushed before it stops being a fun game? Fun has to be an overriding concern. A guy named Milos ran a game which pitted 4 mafias against each other, no town or SK. By the dawn of day two, it was apparent what was going on, and it was massively unfun. Another guy ran a game where he unexpectedly reanimated every dead player on day 5. With several confirmed townies and 3 auto-lynches, the rest of the game was trivial to solve.
You have to give serious consideration to the effect of a big change like that from a player perspective. My attitude lately is that each mafia game is so varied just from flavor and having different players involved, that making sweeping changes is unnecessary, and actually detracts from the overall experience. Examples:
Recruitment - I am against recruitment. Fundamentally, it is unfun, as it punishes good play. Consider a townie who has been instrumental in the lynches of two scum. They get recruited, but by a side which by definition is close to losing, and now that townie is punished for all their accurate reads.
Multiple scum groups: Unfun. Why? Because you remove the town’s best weapon of analysis. If there are two scum groups, each can hunt the other and be truly, honestly townie. It is very, very difficult to pick out scum from a town perspective in that scenario.
Excess abilities: Unfun. It’s critical to include a large number of lynchable townie, at least equal to the number fo scum, and probably higher. It doesn’t matter how much you buff the mafia if it’s nearly impossible to lynch anyone but scum.
I’d be happy to talk privately about your ideas if you want a sanity check. There’s also another mafia-eque game called clans that a friend of mine invented. You might find it interesting.