For example, for a block to be valid, no more than half of the transactions in the block can have fees below the average fee for that block. So, if 10 transactions have a fee of 1BTC and 10 more have a fee of 0.5BTC the average is 0.75. Now half the fees are already below this so an additional transaction with a 0.5BTC fee cannot be accepted, but a 0.8BTC fee is okay.
'No more than half less than the average' will not maintain the transaction fees, without other factors pushing up the fees. The fee will progressively get lower as the low side will get attacked harder than the high side. In the above example a transaction fee of 0.751 will increase the average very slightly, then the next transaction fee of 0 will lower the average (relatively) much more.
Well that's just fine. if there are no other fee paying transactions, the generator can accept the 0.751 and the 0 and still satisfy the rule, but he can't accept another 0 fee tx. Though, I now believe it is flawed for other reasons.
The current breed of stock generators, generate continuously, and only ignore a block if it is deemed illegal.
When transaction fees become the main incentive to generate a new breed of generators will be developed that will maximize the profit made. One of the features of this bread of generator is that certain 'rules' will be voluntarily agreed upon, some will not accept blocks that have two many low fee transactions, and will wait for blocks that have only higher fee transactions.
The risk of a generator who accepts too many (new) low fee transactions is that the most of the network will ignore and orphan it's block.
This is an interesting, market based solution. Generators can stop competitors from undercutting them, by "voting" out blocks that don't adhere to their own customized rules. I'm not convinced that it is sustainable. It looks like a problem for game theory.
If generators get too greedy, accepting all transactions, They run the risk that most of their peers will reject their hard work generating a block. If they reject blocks that their peers have accepted, they'll waste time working on a smaller block chain.
If this sort of thing works, then miners should be doing it now! This will stop the spam problem: If miners start rejecting blocks that are too generous to spamers, we shouldn't need a block size limit. I suppose, though, that the block size limit IS an implementation of a voluntary rule. Though a rather primitive one, it's sufficient for now.
Perhaps miners will converge to using an optimal rule, similar to what I've described and I'm trying to preempt this development. This definitely looks like the problem of finding an "optimal strategy" in game theory.