The existence of rights is critical. The rights that utilitarianism allows for are rights that will maximize happiness. But isn't the whole idea of a right the idea that you are entitled to something no matter what, even if your having that right makes things worse for the sake of happiness. For example, do you only have the right to live if it would be best for the balance of pleasure over pain if you stayed alive?
