Take a look at the Bitcoin wiki page on Transaction Fees.
First of all, a transaction fee is not always required. Miners decide whether to accept transactions without a fee and most miners follow the same decision protocol for that.
A transaction may be safely sent without fees if these conditions are met:
- It is smaller than 10,000 bytes.
- All outputs are 0.01 BTC or larger.
- Its priority is large enough (see the Technical Info section below)
The priority basically adds the notion of age. Outputs that are created some time ago can mostly be sent for free. Very young outputs cannot be spent free. This is to prevent someone from spamming the blockchain with consecutive transactions.
Otherwise, the reference implementation will round up the transaction size to the next thousand bytes and add a fee of 0.1 mBTC (0.0001 BTC) per thousand bytes. As an example, a fee of 0.1 mBTC (0.0001 BTC) would be added to a 746 byte transaction, and a fee of 0.2 mBTC (0.0002 BTC) would be added to a 1001 byte transaction. Users may increase the default 0.0001 BTC/kB fee setting, but cannot control transaction fees for each transaction. Bitcoin-Qt does prompt the user to accept the fee before the transaction is sent (they may cancel the transaction if they are not willing to pay the fee).
So this basically means that the fee increases as the transaction size increases. Considering this, it is not a good solution to add thousands of inputs and outputs to a transaction.
I believe the best solution for a service like a market is to try to make as much as possible free transactions. A typical single-input-single-output transaction is 500 bytes. When you always use the oldest outputs available in your hot wallet pool, you can try to always create 10KB transactions that are free.
