Hi Witold,
for the orders that are in the same block, this is fairly doable - we do know how to generate shared randomness cheaply, so we could generate a random number after the block is scheduled and use that to sort the orders inside that block. Being somewhat randomized about which block a transaction ends up in is a bit more tricky to do in a way that can’t be manipulated, but should be possible (within reason).