There is a finite (but positive) number of cases that I haven't solved yet.
General Case
Spoiler! :
When m and n are both big (other cases will be treated or mentionned below ; the condition on m here is always 
), Randall always has a winning strategy. This strategy consist in the construction of a barrier of blocked squares that cannot be the greatest of the row. A square which have to be blocked is said protected. The strategy is always :
-when Mike write a number in a protected square, Randall blocks this case by writing a greater number in an unprottected square in the same row,
-when M write a number in an unprotected square, but in a row that contains unblocked protected squares, R blocks any protected square of the row by writing a smaller number
-esle, if he can, R writes any number in any square which is not in the same row that an unblocked protected square
-and if he can't, it's more complicated.
Of course there is never more protected squares than unprotected squares in one row.
When Mike begins
n even,
The protected squares are :
_{1\leq i \leq \frac{n}{2}})
, )
, )
and _{\frac{n}{2}+1 \leq i \leq n})
For a 4*6 it is :
X X X _ _ _
_ _ X X _ _
_ _ _ X X X
_ _ _ _ _ _
This is the simplest case, just using the general strategy works.
n odd,
Let
.
The protected squares are :
_{1\leq i \leq k})
, )
, )
, )
and _{k+1 \leq i \leq n})
.
For a 3*9 it is :
X X X X _ _ _ _ _
_ _ _ X X X _ _ _
_ _ _ _ _ X X X X
When R cannot play with the general strategy, there are three possibilities :
-if all the squares are writen, R do nothing and win,
-if there is one empty protected square and a full unprotected square in the same row, R blocks the PS by writing a smaller number,
-else there is an empty row, R write any number in an unprotected square of this row. As n is odd, there is still more US than PS in this row.
When Randall begins
n odd
The strategy is exacly the same as before. The fisrt turn, R plays as if M has just play in a "normal" square.
n even,
Let n=2k. The protected squares are :
_{1\leq i \leq k-1})
, _{k-1 \leq i \leq k+2)
and _{k+2 \leq i \leq n})
.
For a 3*12 it's :
X X X X X _ _ _ _ _ _ _
_ _ _ _ X X X X _ _ _ _
_ _ _ _ _ _ _ X X X X X
This way, there are always stricly more unprotected square than protected in the same row, so we can use the general strategy.
-when Mike write a number in a protected square, Randall blocks this case by writing a greater number in an unprottected square in the same row,
-when M write a number in an unprotected square, but in a row that contains unblocked protected squares, R blocks any protected square of the row by writing a smaller number
-esle, if he can, R writes any number in any square which is not in the same row that an unblocked protected square
-and if he can't, it's more complicated.
Of course there is never more protected squares than unprotected squares in one row.
When Mike begins
n even,
The protected squares are :
For a 4*6 it is :
X X X _ _ _
_ _ X X _ _
_ _ _ X X X
_ _ _ _ _ _
This is the simplest case, just using the general strategy works.
n odd,
Let
The protected squares are :
For a 3*9 it is :
X X X X _ _ _ _ _
_ _ _ X X X _ _ _
_ _ _ _ _ X X X X
When R cannot play with the general strategy, there are three possibilities :
-if all the squares are writen, R do nothing and win,
-if there is one empty protected square and a full unprotected square in the same row, R blocks the PS by writing a smaller number,
-else there is an empty row, R write any number in an unprotected square of this row. As n is odd, there is still more US than PS in this row.
When Randall begins
n odd
The strategy is exacly the same as before. The fisrt turn, R plays as if M has just play in a "normal" square.
n even,
Let n=2k. The protected squares are :
For a 3*12 it's :
X X X X X _ _ _ _ _ _ _
_ _ _ _ X X X X _ _ _ _
_ _ _ _ _ _ _ X X X X X
This way, there are always stricly more unprotected square than protected in the same row, so we can use the general strategy.
Particular general cases
Spoiler! :
Some cases aren't in the general case but can still be solved with the same strategy :
m*5,
The protected squares are :
X X _ _ _
_ X X _ _
_ _ X X _
_ _ _ X X
Randall begins, m*8,
The protected squares are :
X X X _ _ _ _ _
_ _ X X X _ _ _
_ _ _ X X X _ _
_ _ _ _ _ X X X
Randall begins, m*6,
The protected squares are :
X X _ _ _ _
_ X X _ _ _
_ _ X X _ _
_ _ _ X X _
_ _ _ _ X X
Randall begins, m*4
This time, M wins. All he has to do is to protect the first and last column. For a 3*4 it is :
X _ _ X
X _ _ X
X _ _ X
m*3
Idem, but M has only 1 column to protect, so he wins even if he begins.
m*5,
The protected squares are :
X X _ _ _
_ X X _ _
_ _ X X _
_ _ _ X X
Randall begins, m*8,
The protected squares are :
X X X _ _ _ _ _
_ _ X X X _ _ _
_ _ _ X X X _ _
_ _ _ _ _ X X X
Randall begins, m*6,
The protected squares are :
X X _ _ _ _
_ X X _ _ _
_ _ X X _ _
_ _ _ X X _
_ _ _ _ X X
Randall begins, m*4
This time, M wins. All he has to do is to protect the first and last column. For a 3*4 it is :
X _ _ X
X _ _ X
X _ _ X
m*3
Idem, but M has only 1 column to protect, so he wins even if he begins.
Other cases
Spoiler! :
1*n, m*1 and m*2
M plays randomly and wins.
2*n, Randall begins
Whatever R plays, M write a number in the case just below or just above such that the order of the two rows are identicals. M wins.
2*n, Mike begins,
Let
such that  = 1, \sigma(n) = 2, \sigma(i) = i+1)
. When M plays in the square )
, R plays in ))
, and when M plays in the square )
, R plays in ))
, using the same principle as M just above. R wins.
3*6, 4*6 and 3*8 when Randall begins, and 3*5
To be done.
M plays randomly and wins.
2*n, Randall begins
Whatever R plays, M write a number in the case just below or just above such that the order of the two rows are identicals. M wins.
2*n, Mike begins,
Let
3*6, 4*6 and 3*8 when Randall begins, and 3*5
To be done.
