I think I'm starting to get it. Alice's work gets ignored if Bob solves his block first, regardless of who has the faster hash rate? I had thought both sets of transactions could be merged into the blockchain, but I guess Alice has to include the hash of the newest block if she wants to get a reward+fees.
Well it isn't so much "ignored" as worthless. How much are losing lottery tickets worth? Just about as much as Alice hashes which don't solve a block. I guess because the idea of mining for day, months, years without solving a block is depressing sometimes people have a tough time realizing there is no "progress" towards a block. You either solve it or you don't.
If you attempt 1 trillion hashes and none of them solve a block you are no closer to solving a block then before you started.
Still you are right there is no concept of "merging" transactions. Even if there was Alice would be better served still going for the highest fee tx (no matter how painfully slow she is). If Bob solves a block, Alice validates the block and removes all the included tx from the memory pool. Alice then reselects the "best" tx, builds the merkle tree, and starts hashing a new block. The amount of effort in constructing the blockheader is negligible compared to the trillions upon trillions of hashes (proof of work) it takes on average to solve the block. It doesn't save Alice any time or energy to NOT include the most profitable txs.
Thanks very much for the explanation. It now makes sense that Alice should include the highest fees that she can, but doesn't she have to trade off waiting for higher fees to appear before she can start hashing? The longer she waits for higher fees to come in, the more likely it is someone else will solve the next block before she does, right? By not waiting for higher fees, she's effectively lowering the range of tx fees she can accept. EDIT: if that's true, it also means Bob can afford to wait for higher fees before he starts work. If Bob solves his block it will contain newer txs with higher fees, while Alice's block contains older txs with lower fees. So it is as though Alice and Bob are competing over different tx fee ranges. The market will still end up pricing confirmation times as I'd hoped, but for different reasons