Because it’s not the timing of the clock of either observer that is dilated but the other observer’s interpretation of their view of it. It’s really no more of a contradiction than the fact that if we are facing one another then when I ask you to raise your right hand you raise the one on my left. (Note: I didn’t say it’s the same, just “no more of a contradiction”. If it seems mysterious to us that’s just because our experience of comparing notes at low relative velocities leads us to wrongly guess that there is an absolute standard of simultaneity for spatially separated events.)
Note: It’s only when both observers are in fixed inertial frames that they both see the other’s time as dilated. In the travelling twin scenario (appended as a comment to the actual question) one or other of the twins must undergo acceleration (or impulse) in order for them to get back together, and whoever is accelerated (or jumps from one frame to another) sees much of the time of the other as very much compressed (or collapsed to a single point of his or her own time in the physically impossible case of an instantaneous turn-around).
This is a real asymmetry because in the absence of gravity (ie in Special Relativity), the twin who is accelerated actually feels a force which the other does not. So they do know which one was accelerated.
In General Relativity an observer in free fall can accelerate without feeling any forces (and if the traveler is turned around by a gravitational slingshot then the time difference is explained by the time spent at the bottom of a very deep gravitational potential well – or equivalently the proximity of a very large mass – which is again an asymmetry between their experiences); but that’s another matter form the question of whether it’s a “paradox” in SR. In SR one cannot accelerate without being pushed by something like the reaction forces of a rocket and one twin knows he or she is in a rocket ship and feels the force while the other does not.