What is the incentive for Bitcoin miners to add transactions without fees to a block?

There actually is one incentive to include transactions without a transaction fee.  It may not be possible to find a nonce that meets the difficulty without those transactions. Most people know that the miners aggregate all the transactions for a block and search for a nonce which makes the hash start with a certain number of zeros.  What most people don't realize, is that for most merkle trees, there is no nonce that meets the difficulty level.  What the miners do, is add and remove transactions from the merkle tree or alter the coinbase transaction in some way, and then try all the nonces again. Let's say that your mining strategy is to only include transactions that include a transaction fee.  In this example, lets say that there are 100 transactions with fees since the last block.  Your mining pool tries all hashes and combinations for that group of transactions and finds that there is NO nonce that meets the difficulty requirements.  You can (a) remove one of the paying transactions, or (b) add one of the non-paying transactions.  Now you can try all the nonces again with either 99 transactions or 101 transactions.  Assuming you're equally likely to find the nonce by adding or removing transactions, you're actually giving away transaction fees by deciding NOT to include non-paying transactions. That said, miners include a lot more than the minimum transactions, so most of it is good will and the health of the network.  Think of it as a loss leader.  If people stop using the network, their mining has no value and the bitcoin they mined loses value.  The cost of including free transactions is negligible compared to the reward for finding a block at this point.  That may change as the rewards decline.

Bitcoin mining is a variation of the prisoner's dilemma. A miner can choose one of the 3 strategies : - mining always empty blocks - mining blocks including only paid transactions - mining blocks including paid and free transactions The less costly solution (in term of CPU/memory/bandwidth usage) is to always mine empty blocks. However if all the miners do this, the network stops, becomes useless, and then the value of one bitcoin will drop. Miners don't want this, so enough of them don't mine empty blocks. Between the two other strategies, the costs are very close, because the fee is only calculated after the transaction is processed. So a miner who only wants to include transactions with fees still has to process all incoming transactions. Only after scanning them can he decide to drop the non paying ones. Finally, most of the miners are pools, and they do not own their hashing power. If one pool is suspected to not play the game fairly, he risks loosing some or all of its hashing power when hashers switch from one pool to another. The result is that right now a paid transaction is included almost immediately, and a free transaction (as allowed by the default rules) is included as soon as the network is not under heavy load.