  We study game-theoretically secure protocols for the classical ordinal
assignment problem (aka matching with one-sided preference), in which each
player has a total preference order on items. To achieve the fairness notion of
equal treatment of equals, conventionally the randomness necessary to resolve
conflicts between players is assumed to be generated by some trusted authority.
However, in a distributed setting, the mutually untrusted players are
responsible for generating the randomness themselves.
  In addition to standard desirable properties such as fairness and
Pareto-efficiency, we investigate the game-theoretic notion of maximin
security, which guarantees that an honest player following a protocol will not
be harmed even if corrupted players deviate from the protocol. Our main
contribution is an impossibility result that shows no maximin secure protocol
can achieve both fairness and ordinal efficiency. Specifically, this implies
that the well-known probabilistic serial (PS) mechanism by Bogomolnaia and
Moulin cannot be realized by any maximin secure protocol.
  On the other hand, we give a maximin secure protocol that achieves fairness
and stability (aka ex-post Pareto-efficiency). Moreover, inspired by the PS
mechanism, we show that a variant known as the OnlinePSVar (varying rates)
protocol can achieve fairness, stability and uniform dominance, which means
that an honest player is guaranteed to receive an item distribution that is at
least as good as a uniformly random item. In some sense, this is the best one
can hope for in the case when all players have the same preference order.
