As the title says, who is most deserving? This obviously only means 3rd party characters. In my opinion, I'd go with Ezio. Though many tend to disagree just because Ezio is 3rd party, I worded the question correctly so if others suggest him, they won't got scolded into oblivion.
prince of Persia moveset: http://community.us.playstation.com/t5/PlayStation-All-Stars-Battle/Prince-of-Persia-in-all-stars/m-p/38273897#M125640
Assassins Creed = more preorders on xbox, he shouls be in xbox allstars
Oh come on now. I associate AC with PlayStation much more on Xbox. Ubisoft has a great partnership with Sony, we get some extra exclusive goodies, the graphics are slightly better, and the average review score for all games are the highest on PS3. Stupid points, yes. But I don't see how you can associate it with Xbox more than PS3.
I don't think Ezio would be a good fit because all the Assassin Creed's were on multiple systems to me the deserving ones are those that had at least 1 exclusive game/debuted on the Playstation, or had an impact on Playstation's success. One of the only reason's Big Daddy got in is the same why Snake was in Brawl, a deal was made.