Homework 1 Q6

Homework 1 Q6

Jonathan_G 21 Apr 2017 11:04

I wanted to verify that I'm understanding the question correctly:

The strategies available to player i are only paths that have a length of exactly l_i from s (meaning the game is defined only on graphs for which there are such paths for each player), and each player is seeking to minimize his cost?

Re: Homework 1 Q6

KineretS 21 Apr 2017 21:05

1. Each agent indeed wishes to minimize her cost.
2. You are correct that the set of valid strategies for player i contains exactly the paths of length l_i. But note that, as was written in the question, an agent can use an edge multiple times. Meaning that if for example, l_i = 3, and there is a cycle of length 2: s -> v -> s for some node v in the graph, a valid strategy for that player would be s -> v -> s -> v (which contains only 2 edges, but uses (s,v) twice).