Well, you want an honest answer? Raw compute "guts" award would go to the RX 580, but it also has much greater power-consumption.
If you have an OEM pre-built system, and CAN'T, for some reason, change out the PSU to a 500-600W one, then stick with the "safe" option, of the 1050ti 4GB.
But for pure gaming FPS, power-consumption-be-damned, the RX 580 is a notch better.
If you ARE going to go with the RX 580, and you're buying new, consider an 8GB model, if it's not more than $20-25 more.
Also, you can mine ETH with the RX 580, way better than the 1050ti 4GB can. If that matters to you.
Edit: I'm basing this on HardwareUnboxed videos, from a year or so ago, comparing RX 570 with GTX 1050 ti 4GB. The RX 570 was their recommendation, because although it had higher power consumption, it was the same price or cheaper, and had higher FPS in games.
The RX 580 is yet another notch above, in FPS, and slightly higher in power consumption (though not much, most Polaris cards are in the same ball-park, power-consumption-wise, except for the "little Polaris" cards, like the RX 550.)
Edit: I missed the part about "both are overkill". Is this for a HTPC? Go with the 1050 ti 4GB. For gaming? Go with the RX 580.
If they're both overkill, though, consider going with whichever card is cheaper?