It's my company's problem that the market is flooded with foreign nationals with advanced degrees, who work for less money and have poor English skills?

It's your company's problem that your legally valid hiring opinions are being overridden by other departments to cut costs. Especially when there are tons of American citizen CS grads from non-target schools that would probably take the $20k hit (or even more) to get their foot in the door. Your company is acting absolutely stupid.