To answer your question, we have to look at what The Lobster is doing and how it might have approached its message. Ultimately, this is a film about the cost of singleness, and the tension between social expectations and personal ones.
Any narrative form can strive to "make sense" in a literal way, i.e., in the way that our universe "makes sense". But many, if not most, tend to only "make sense" in an aesthetic way, i.e., a way that conveys artistic meaning and truth. This is because a literal "making sense" is often unsatisfying to the audience.
A common theme among single people (as represented in the media) is that they are made to feel inadequate by dint of their singularity. "What is wrong," society asks, "with someone who is not attached?" This, by the way, used to be more a reflection on society's promotion of traditional marriage and family units, but now floats as a disembodied value judgment.
A classic example is Steve Martin's "The Lonely Guy" where going into a restaurant alone causes a literal spotlight to be put on him:
This is literal, but in a comedy context.
This theme is usually played as a romantic comedy. The entire genre of RomCom, in fact, is centered around the idea of two often difficult people trying to work out some sort of arrangement. When it's played straight, it's usually to highlight some sort of dysfunction in the single character. Like, say, Breakfast at Tiffany's.
Holly is damaged. In Truman Capote's original story, there is no "happy ending". You can imagine how popular THAT would've been in movie form.
This theme of "dysfunctional singleness" has been prevalent the past, say, 30-40 years. As Loudon Wainwright sang about going out to eat by himself:
Well, you can put me at the table in the corner in the back
Unless you got one in the telephone booth
I'm here and I'm alone again
It's sad but it's the truth
No I'm not expecting anyone
Is that beyond belief?
In The Lobster we have the attitude taken to its extreme conclusion. It's literally criminal to not have a significant other, and the Police State has turned its tremendous scrutiny to eliminate all single people. Does it make literal sense? No. Does it make an aesthetic sense to show a man who is incapable of love thrust into a society where "love" (in some socially acceptable form) is mandatory? Absolutely.
Your objection about cheating misses the point: Some people can always find the next person, and they'll do it without regard for the feelings of anyone in their lives currently. You could say they "love easily" although this begs the whole question of the nature of love. Which brings us to our hero, David.
If we eschew David's literal defense for wanting to be turned into a lobster, what do we have? We have the desire to be a creature that cannot embrace. The posters for the movie are a little on-the-nose, even:
Everybody else wants to be a dog, representing the desire to have uncomplicated affection. Everyone loves dogs, dogs love everyone. Lobsters? Lobsters are delicious sea cockroaches.
David's problem, however, we learn is not so much that he's unable to love but that he wants the love to be real and not merely a social obligation. (Again, going back to that original idea of the anathema of singleness.) He sees others doing the relationship thing, and it's almost all bullshit (at worst) and delusion (at best). His desperation not to be forced into a fake relationship is at odds with his desire to not actually be turned into a lobster.
This is how extreme the pressures have to be to get David to move: Remember also that he has to witness the horror of being turned into an animal to realize how bad it is, too. Up until then, it's sort of an "I'd prefer not to" thing.
This makes his final decision profound: To what extremes will he go through to have this thing he so desires? (And here again, we have to set aside any concept of literalness when we consider the movie's notion of "compatibility".)
So, while the movie is not aggressively concerned literal truths, it's highly consistent in its internal logic...and that's why singles are persecuted.