# Tag Info

5

There is no algorithm that always beats all others in an IPD tournament. Proof: if your algorithm cooperates in round 1, then it gets last place in a tournament where all other bots always defect; if your algorithm defects in round 1, then it gets last place in a tournament where all other bots play unforgiving tit-for-tat (cooperate until the opponent ...

2

Let's assume the first strategy is the best until someone comes up with a better one, ok? So we set a threshold for value (between 0 and v). If the value of the candidate is higher than the threshold, try to hire that candidate. Otherwise, interview the next candidate. If we interview several candidates in a row whose value is below the threshold, decrease ...

7

For company $A$/the firm/giant corporation/"big pharma"/"THE MAN", the strategy does not change from the symmetric version: Consider a round where the probability of seeing only lesser candidates thereafter is $> .5$. If company $A$ keeps the candidate, then it has a chance of winning $> .5$. If $A$ does not keep the candidate, then company $B$ can ...

5

It may also be worthwhile to note that this problem was also solved in the 70's by Thomas Schaefer in ￼Complexity of decision problems based on finite two-person perfect-information games. In fact, he proves a slightly stronger result in that the language remains PSPACE-complete even when restricted to positive CNF formulas.

27

It is an Unordered Constraint Satisfaction game and it is PSPACE-complete and it has been proved to be PSPACE-complete only recently; a proof can be found in: Lauri Ahlroth and Pekka Orponen, Unordered Constraint Satisfaction Games. Lecture Notes in Computer Science Volume 7464, 2012, pp 64-75. Abstract: We consider two-player constraint satisfaction ...

Top 50 recent answers are included