Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each player is not allowed to pick the item picked before by oneself and the opponent. The game lasts $k(2k\leq n)$ rounds, and both players seek to maximize the sum of values of his/her picked items minus the sum of values of opponent's picked items. What is outcome of the game, if both players pick the optimal strategy? Is there an efficient algorithm for this?
The case when $2k=n$ is trivial: two players alternately take the item with the maximum $a_i+b_i$. However, for general $k$ this strategy doesn't work: when $B$ picks element at the last round, he/she would pick the item with the maximum $b_i$ instead of maximum $a_i+b_i$. I have trouble solving the case for general $k$, and even don't know if it is tractable for the case of general $k$. I guess this problem is well-studied because this formulation sounds natural. In fact, I think of this problem from the process of ban/pick in MOBA games. Any help would be appreciated. Thanks in advance.
