I get what you mean and you're right, I was simply overcomplicating things and thinking about maximising the overall upward force the tire receives. The lift is determined by the volume the tire is occupying. Depending how much pressure you take away, you could actually increase the resulting, overall upward force the tire will receive, even if it's incredibly minor due to the small mass of air. But if you take it too far, the outside pressure would just lessen the volume of the tire which means less buoyancy. That means you need to have the information about how many meters it's under water too. That being said, I don't even know how firm a tire is. Which means the theoretics here are way too complex - unless you have an accurate formula for the tire deformation handy - and you're better off experimenting. And then perhaps developing a formula for it afterwards.
If any of you have ever tried to check a medium truck tire in water to see if there is a leak anywhere on it would know that it will float... hard as hell to keep down. As for a doughnut... it would probably still float... but no where near as buoyant... As for the tires at the bottom of the river, perhaps they had a leak in them... I mean why would they have thrown a good tire in the river? Even still, with the buoyant forces from four tires... as I stated earlier, if they aren't Monster truck wheels, they wont float a vehicle.