いろんなレストランがパティオを出していますが、
そのほとんどが歩道にせりだしていますよね。
歩道が細くなり、正直迷惑なのですが、その分
税金って払っているんですかね？
１民間レストランが道路を営業目的で使用するのに
どうも納得ができないんですが・・・。

ただじゃないのよ。

どの都市のことを言ってるのか知りませんが、大抵の場合はレストランが使用料を市に払ってます。
（バンクーバーの例）
http://vancouver.ca/doing-business/sidewalk-patio-with-liquor-service-large-patio-permit.aspx

歩道にもちゃんとスペースを設けることが規則になってます。
Leave enough space on the sidewalk for pedestrians to move around it and any other obstacles, such as street lights, parking meters or trees. The minimum distance is 8’ or 2.5 metres to the nearest sidewalk obstruction (i.e. tree, parking meter post, bike rack, bench, bus shelter, etc.).

レストランがこれに違反しているようなら、市に電話してチェックしてもらったらいかがですか？

自治体によって違うので、トピ主さんの住まいにもよると思いますよ。
私が住んでる町は、パティオどころか看板も歩道には設置できません。道路に面した敷地内のみです。
で、どのレストランもストイックに規則を守っています。町が厳しいんで。

政治は国によって違います、国境をポリティカルバンダリーと呼ぶ。
無回答国の政治を調べましょう。