Why would the batch auction need to be FIFO? What about something like this:

1) When opening a "new tick", release data about trades in last tick, and start accepting new orders. Information about orders submitted to this tick is kept secret. Allow setting order price to practically arbitrary accuracy. 2) After tick closes, match orders in _random order_. That is, it should not matter at all on at which point in time inside this tick order arrived 3) repeat

Allowing arbitrary accuracy would help turn the competition from speed or stuffing the order book with huge number of orders to "spoof" the random matching, towards competition of just providing lower spread. I understand that it would still advantageous to hold submitting trades until very end of the tick, to take into account as much outside information (other markets, etc.) as possible. To counter this, maybe the exact length of the tick could be randomized also. What do you think?