3 ms·

Even if you haven't maybe it is. I might be overly cocky here but it seems obvious what kinds of costs these are and why the simple model is the way it is. Why

by gmarx 12y ago

Even if you haven't maybe it is. I might be overly cocky here but it seems obvious what kinds of costs these are and why the simple model is the way it is. Why is the exponent on N greater than 1? Because otherwise coordination costs would decrease as you add more people, right? Are their complaints basically that the exact answer to this question should have been available in the notes and that they shouldn't have to apply past knowledge and techniques to an unfamiliar problem?

mturmon 12y ago
"Because otherwise coordination costs would decrease as you add more people, right?" Not so fast, or you might lose 10 points. ;-) Note that the coordination cost is given per-capita, and it is proportional to N^2. If the per-capita cost was O(N^a) for a < 1, the total cost would still be N*N^a = N^(1+a) which increases with N. If the (per-capita) coordination cost were proportional to N, that would indicate that (e.g.) to do something, you have to contend with "N" other people (everyone else in the population), which makes sense. The total coordination cost would be: (N people) X (per-capita cost of N) = N^2, which is familiar from various kind of networks, e.g., distributed computations in which total communication costs can rise like N^2 (where N is the number of processors). But if the per-capita cost is proportional to N^a for some a > 1, that's even stronger. I'm not sure how you justify that. I'm sure you can, I'm just not sure how the course did it. Maybe you say that you have to coordinate with all N other people, as well as all pairs of the N other people. The number of pairs of other people is proportional to N^2, giving you a per-capita coordination cost proportional to N^2.
- titanomachy 12y ago
  Without knowing what coordination cost is, that would be my guess. I'd probably phrase it vaguely like "the cost of coordinating N people is proportional to the number of connections between those people, i.e. proportional to N^2". But that might be less obvious to an econ student who's never studied complexity theory.
  - mturmon 12y ago
    But I fear, from what you wrote, that you fell into the same trap as @gmarx above. The claim in the exam is that the total coordination cost is above quadratic, i.e. proportional to N^b for some "b" strictly larger than 2. (Because per-capita cost is proportional to N^a for some "a" strictly larger than 1.) This is not what is typically assumed in complexity theory.

by gmarx 12y ago

mturmon 12y ago

"Because otherwise coordination costs would decrease as you add more people, right?" Not so fast, or you might lose 10 points. ;-) Note that the coordination cost is given per-capita, and it is proportional to N^2. If the per-capita cost was O(N^a) for a < 1, the total cost would still be N*N^a = N^(1+a) which increases with N. If the (per-capita) coordination cost were proportional to N, that would indicate that (e.g.) to do something, you have to contend with "N" other people (everyone else in the population), which makes sense. The total coordination cost would be: (N people) X (per-capita cost of N) = N^2, which is familiar from various kind of networks, e.g., distributed computations in which total communication costs can rise like N^2 (where N is the number of processors). But if the per-capita cost is proportional to N^a for some a > 1, that's even stronger. I'm not sure how you justify that. I'm sure you can, I'm just not sure how the course did it. Maybe you say that you have to coordinate with all N other people, as well as all pairs of the N other people. The number of pairs of other people is proportional to N^2, giving you a per-capita coordination cost proportional to N^2.

titanomachy 12y ago
Without knowing what coordination cost is, that would be my guess. I'd probably phrase it vaguely like "the cost of coordinating N people is proportional to the number of connections between those people, i.e. proportional to N^2". But that might be less obvious to an econ student who's never studied complexity theory.
- mturmon 12y ago
  But I fear, from what you wrote, that you fell into the same trap as @gmarx above. The claim in the exam is that the total coordination cost is above quadratic, i.e. proportional to N^b for some "b" strictly larger than 2. (Because per-capita cost is proportional to N^a for some "a" strictly larger than 1.) This is not what is typically assumed in complexity theory.