Having watched another episode of Puella Magi Madoka Magica, I think a similar situation could become an interesting challenge. It would probably work best in a visual novel format, focusing on the effects of the player character's interactions and their effects. The many possible bad ends would loop the player back to the start of the novel, with some new information about their enemies and their allies. Combat would be similar to the early Final Fantasy games, with the player controlling their character and any characters they have high enough friendship with. Other characters would be A.I controlled. The main feature off the game would be the possibilities for Interaction with other characters, which should track the endings achieved by the player, using the new information to add new options for dialouge.