This gist tries to come up with a back-of-the-envelope estimate for how much it costs a miner to create larger, rather than smaller, blocks. An economically rational miner will only include transactions with enough fees to cover the cost to the miner of processing the transaction.
I hope this analysis helps solo miners and mining pool operators to reason about their transaction fee policies, and helps them estimate their 'charity cost' if they decide to include fee-free transactions in the blocks they create to promote more use of Bitcoin.
Uncertain numbers in this document are rounded to one digit of precision; this is meant to be an order-of-magnitude estimate; when I say that 100K of free transactions costs about $1, you should assume that the real number might be anywhere between 10 cents and 10 dollars.
The dominanting cost for a miner to include more transactions in their blocks is the risk that larger blocks are more likely to be orphaned. I estimate a current-worst-case "orphan cost" of an average 250-byte transaction is 0.0008 BTC, or, at today's $500/BTC price, $0.41 (forty-one cents).
Therefore, a rational miner should demand at fee of at least $0.41 per transaction. The default fee-per-kilobyte for the reference implementation is 0.0001 BTC/kb (5 cents).
Direct bandwidth, disk, and CPU costs to process a typical 250-byte transaction are negligible; the most expensive operation is checking the transaction input's ECDSA signature(s). Assuming it takes 0.002 CPU-seconds (2ms) to validate a transaction, and a server uses $0.03 per CPU-hour in electricity, validating one transaction takes 1.6 microdollars (millionths of a dollar).
A much bigger cost to the miner is the risk that by making their blocks larger they will take longer to be sent to other nodes, validated, and accepted; if another (smaller, faster propagating) block is found in that time, the miner's block will be orphaned and they will lose the 25BTC block subsidy and all transaction fees.
Given the 10-minute-per-block generation rate, the chance that a block will be found in the next X seconds is: 1 - e^(-(1/600)X)
According to measurements from Christin Decker and Roger Wattenhofer: "each kilobyte in size costs an additional 80ms delay until a majority knows about the block."
An 80ms delay increases the chances that the miner's block will be orphaned by 1-e^(-(1/600) x 0.080) = 0.00013. Multiply that by the 25BTC block subsidy, and we get the estimate that a typical 250-byte transaction must have a fee of at least 25 x 0.00013 x 250/1000 = 0.0008 BTC or its potential "orphan cost" outweighs the fee.
It would be nice to get real-word metrics on how long it actually takes smaller and larger blocks to propagate to miners; I suspect that most hashing power is not directly connected, but is protected behind "network facing" relay nodes.
It would also be nice to get real-world metrics on how quickly transactions propagate; if most of the network has already validated a transaction, then validating it is much faster (TODO: how fast is validation if the ECDSA signature is already cached? Its inputs must still be checked for double-spend when the block is created...)
As far as I know, miners are not doing much to minimize their orphan cost beyond trying to be well-connected so their blocks are seen by the network quickly. In the future, they might do things like prefer to relay marginal-fee transactions but not include them in their blocks until enough time has passed that they are certain most of the network has validated them.
Are there strategies miners might use to try to maximize their rival's orphan costs? (beyond the DDoS attacks we have already seen)
A question that is often asked is "what incentive do miners have to relay transactions? Why don't greedy miners simply keep high-fee transactions to themselves?" Under what conditions does the benefit of (trying to) keep the larger fee transaction outweigh the increased orphan cost?
If we imagine there is no limit to blocksize, and the block subsidy is zero, what is the transaction fee equilibrium? Every transaction with a fee added to the block increases the amount lost if the block is orphaned, and (slightly) increases the chances that it will be orphaned.
Does bandwidth eventually become a bottleneck or will CPU/validation time dominate? We should assume that miners will include only "pre-validated" transactions in their blocks, and that new block announcements consist of just the block header (with proof-of-work, merkle root, etc), the coinbase transaction, and then the list of already-broadcast-and-validated transaction ids. In that case, the maximum number of transactions that the network can support will be determined by either the bandwidth to broadcast the transaction data, or CPU power to keep up with validating them.
Given current trends, bandwidth will likely be the eventual limiting factor: http://www.nngroup.com/articles/nielsens-law-of-internet-bandwidth/
Consider two miners in the far future where the block reward subsidy has dropped to zero: A large miner that has 20% of network hashing power, and a small one that has 0.1% of network hashing power. The large miner will pay the cost of validating 5 transactions to be rewarded with 1 transaction fee. The small miner will have to validate 1,000 transactions to be rewarded with 1 transaction fee. What are the dynamics of that system? Will the small miner be driven out of business, or would it only validate/include higher-fee transactions in its blocks? Or will this simply never be an issue because the direct cost of validating a transaction is so small (and will become smaller, assuming computers/networks continue to get faster)?
Regarding "what incentive do miners have to relay transactions?", a good answer by Maged can be found here:
https://bitcointalk.org/index.php?topic=5024.10;wap2