No, they cannot. VZW tried this some years ago and FCC sued them.
VZW has to offer free tethering. Since then VZW started agressive policy on UDP users, no discounts on 2-year upgrade, you loose UDP if you accept subsidy. Customers found a way around, they opened additional 9.99 lines and transfer there upgrade eligibility, but not all of them. Now VZW has 15-22 with smartphones on UDP(not official info, I got it from forum, web sites and estimations). Also you cannot buy and transfer account with UDP on VZW, officially buyer should have at least one line with UDP. With Att you still can buy grandfather UDP for the price around 400-450 on eBay.
Att now is in a split situation:
On the one hand if they cancel UDP, they loose customers(rumors that 40-45 percent on UDP, I think a bit less). FCC pressures them to open hot spots on iphones. Apple also don't want to be in the confrontation with FCC, they can allow 3d party tethering apps, OP is correct here.
On the other hand Att physicly cannot allow official tethering, they are not in good shape with their LTE specrum, most of metro areas as of the end of 2014 had only 10MHz. They try to win some time to convert 1900 3g-HSDPA-HSPA to LTE. More and more regions get now LTE 2(some with aggregation, some without). If Att allows tethering officially, I cancel my FIOS , I put more pressure on Att network, but it will be not only me.
VZW and Att are loosing they "steem" right now, one more year and they come to the point of no return to hold customers anylonger. And this is not only about the internet price, but also roaming, vowifi... I think I know the solution for them, but I leave this part to the guys, who make millions and rule the companies. l don't want to give free advices here and may be I'm wrong since I don't have a full picture here.
I want to say here again, that this the info I heard, not verified, not from official sources, may be it is not a true/real info and may be I'm wrong here. I don't work for any of the telecommunication companies.