Regardless of what the load bearing material is be it air, hard rubber, steel, or even stone, the softer rubber still is caught between it and the ground. It still will be compressed and create rolling resistance by increasing the contact patch area.
Lets take the the tire flex out of the equation entirely. Roll a large ball bearing on a large sheet of soft rubber and a large sheet of hard rubber. The soft sheet of rubber will induce a higher rolling resistance on the ball bearing.
__________________
|