A friend of mine did some consulting for a book binders/printers in Scotland in the late 90s and early 2000s. He would bring me bags of books that had an issue and couldn't be sold.
Amongst this mountain of books was a book of short stories, I presume by one author as I remember there being a number of stories with recurring characters.
The story I remember involved a barbarian character and his child/teenager male accomplice who would allow himself to be captured and the barbarian would then come and rescue him and release all the slaves. The setting was (I think) desert/scrub like North Africa and the technology level was around the level of the Roman Empire (I have a mild association with Byzantium, but that may have come from reading Guy Gavriel Kay's Sarantine Mosaic series at the same time!)
I think another story dealt with the same pair later, having fallen out over philosophical differences, now living in a city and involving themselves in politics.
I remember having a collection by Stephen R Donaldson, but not sure if this was it, having a look at his output doesn't ring any bells.