It would be helpful to know the sector.

I would try and start hyper local. That way you can easily and quickly get deals with small local businesses. You can then grow to small chains and then larger chains for a wider coverage.

Small local business are in my experience very up for these kinds of programmes which might drive more sales or footfall.

If you're looking at bigger corps or online brands then you should start with reselling an existing affiliate programme e.g affilinet in Europe.

Happy to give more specific advice on a call.