Approximability and Parameterized Complexity of Minmax Values

TY - GEN

T1 - Approximability and Parameterized Complexity of Minmax Values

AU - Hansen, Kristoffer Arnsfelt

AU - Hansen, Thomas Dueholm

AU - Miltersen, Peter Bro

AU - Sørensen, Troels Bjerre

N1 - Conference code: 4

PY - 2008

Y1 - 2008

N2 - We consider approximating the minmax value of a multi player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of ε log n digits (for any constant ε > 0) is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits (for any constant c ≥ 1) can be done in quasi-polynomial time. We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k = 2 and there are only two possible rational payoffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated wigh any polynomial number of digits of accuracy in time n^O(k) . On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-C LIQUE requires time n^Ω(k) then so does minmas value computation.

AB - We consider approximating the minmax value of a multi player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precision of ε log n digits (for any constant ε > 0) is NP-hard, where n is the size of the game. On the other hand, approximating the value with a precision of c log log n digits (for any constant c ≥ 1) can be done in quasi-polynomial time. We consider the parameterized complexity of the problem, with the parameter being the number of pure strategies k of the player for which the minmax value is computed. We show that if there are three players, k = 2 and there are only two possible rational payoffs, the minmax value is a rational number and can be computed exactly in linear time. In the general case, we show that the value can be approximated wigh any polynomial number of digits of accuracy in time n^O(k) . On the other hand, we show that minmax value approximation is W[1]-hard and hence not likely to be fixed parameter tractable. Concretely, we show that if k-C LIQUE requires time n^Ω(k) then so does minmas value computation.

U2 - 10.1007/978-3-540-92185-1_74

DO - 10.1007/978-3-540-92185-1_74

M3 - Conference article

SN - 0302-9743

VL - 5385

SP - 684

EP - 695

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 4th International Workshop on Internet and Network Economics

Y2 - 17 December 2008 through 20 December 2008

ER -