Infinity in Game Theory

Yes, I agree that people don’t regard this as a serious question, since modeling infinity is a tricky and boring issue. Game theory is unlike other sub-fields of CS; it is where people use inappropriate models but are still happy to base on them and talk. The following question does seriously question my faith of doing game theory research.

The question is about how to model player’s types (or even strategies) e.g. in single-good auction context. Are they infinite or finite? As a computer scientist I initially only support the latter, but to my surprise, the former survives but the latter “dies”, resulting in a paradox. Details follow.

Background

Most economists use continuous ways to analyze for example the second price auction; while computer scientists believe that the world is finite so everything should be finite. The two settings behave differently indeed. For instance in the second price auction if one breaks tie lexicographically, the first player might underbid by one, and the last player might overbid by one – this gives an additive one loss in the social welfare. In the continuous case, because one can always choose between [A,B] some real number C, such that A<C<B, then everything is fine. (** Please remember this property which I will use later).

As a (potential) computer scientists, I do believe that things are finite. There should be only finite number of pure strategies, and finite number of types, because the number of atoms in the universe is upper bounded. Are finite game settings are justifiable? How about continuous ones? Why do people still look into continuous case? Some theoretical computer scientists hold strong opinion that continuous cases never exist in the real world, so what is wrong here? Also how about other infinite cases that are weaker than the continuous ones, like all rational numbers?

The Paradox

Starting from the finite case, players come to a second price auction, and they write (finite) bids on a piece of paper. However, if a player himself has two different types A<B, both in finite digits and able to be written down. It is reasonable to assume that there always exists some other A<C<B such that some other player has type C or plays strategy C. Notice that C can also be finite and of the number of bits of A or B plus one bits (e.g. (A+B)/2), still finite. If I could write down 100 bits, why can’t I imagine that some other player can write down 101 bits? However, I have now arrived at the same property (**) mentioned earlier, which is what the infinite case tells us.

The paradox arises. From the finite assumption, how did I arrive at the infinite one!!! The reason is, if everything is finite, among the numbers that a player can write down, there is an upper bound on the number of bits, and therefore halving it is impossible. Direct questions then follow. How do players necessarily know this upper bound? How does the designer know this upper bound? How could a player know that his upper bound is larger than his opponent’s upper bound (so can stop halving in his reasoning)? Many ugly things also follow, and a safest way might be to analyze everything based on multiples of 2^{-K}, where K is the number of atoms in the world. This looks reasonable but also brings technical difficulty – how could a player know this K? If none of the players can actually reach a strategy as small as 2^{-K}, (which is likely the case), isn’t this equivalent to the continuous case?

Infinite World Assumption?

I do believe that the game theory community needs to bring up an assumption that models intervals: players have valuations [0,B], and possible bids in [0,B]. Though being widely used by economists, and NOT accepted by computer scientists, it is a reasonable assumption that captures the paradox I mentioned above. We can understand it as follows. Even though not all values or strategies are possible, however, we should allow players to reason in ways like the property (**). Some more works might be needed to build up the connection between the real finite world and the infinite appearance I admit.

Finite World “Dies”?

Not only because of the paradox I mentioned earlier, there is some uglier thing that makes me unable to believe in finite type space. One can for sure analyze a (direct) mechanism assuming that players have types {0,1,...,B} and strategies also in {0,1,...,B}. But this suddenly becomes unrealistic and not meaningful. Yes, the prices are finite (e.g. up to multiples of cents), however, you cannot control a player’s mind and force him to have only integer values. For the same reason as the paradox, as only as a player is allowed to think of two types A and B, it is reasonable for him to think of (A+B)/2 in his mind too. If there is an upper bound here (which is the largest number of atoms in the universe again), then the same trouble comes out, how large is it, who knows it, and how to define it before the mechanism starts, etc. This means that finite assumptions are really untrustworthy.

“Conclusion” or Worry

The purpose of this discussion is that I really fall into a deep quandary which I cannot convince myself that the world is finite, and I also believe that “rational” people in the real-world game are thinking like me believing in property (**). If so, why shouldn’t we analyze things that model the real world, using the Infinite World Assumption? But this is itself an incorrect assumption because the world is finite… I hope that someone can provide a convincing argument against me (or supporting me is also welcome).

Advertisements
This entry was posted in Game Theory. Bookmark the permalink.

5 Responses to Infinity in Game Theory

  1. Lunarmony says:

    “Game theory is unlike other sub-fields of CS; it is where people use inappropriate models but are still happy to base on them and talk.”

    What about machine learning?

    • Machine learning is another story, where people can assume an (almost arbitrary) model and it is correct with probabilities. I think, in machine learning, everything is reasonable and justifiable, but there is no model in machine learning that could perfectly justify everything, because the actual human brain is functioning completely differently.

  2. Yajun says:

    Some random thoughts. As a computer scientist, (self claimed), I see the world as infinite. Finite discretization is our rescue when things breaks down in practice. In theory, I always prefer infinite over finite.

    For your question about limit on the precision, there is one simple answer in real world economy, i.e., there is a limit on the precision on the currency system. You cannot really pay 0.5 cent practically. In theory, of course, as long as the IT system in the banks are okay with that, 0.5 cent makes sense as well.

    • But the fact is the world is not infinite. Especially in real world economy, it is finite. Even if the IT system is powerful, it can allow 0.00001 cent, then how about 1/pi or half of the smallest precision that you support? The interesting thing is that, once you assume it to be finite, some of the things start to break down. We had found interesting examples about that, but couldn’t really make it a nice story or nice paper coz people don’t really care. We’ve abandoned that in the end as it’s too philosophic.

  3. Abhinaba says:

    Just a thought. The world is not necessarily finite. What we know about the world till today is finite.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s