# Michael Schapira: Internet Routing, Distributed Computation, Game Dynamics and Mechanism Design I

This post is authored by Michael Schapira. (It is the first in a series of two posts.)

In this post, I’ll outline work on Internet routing and sketch important areas for future work, both on routing itself and, more broadly, on mechanism design, game theory and distributed computation.

The Internet comprises administrative domains known as Autonomous Systems (ASes), which vary in size, from large (multi)national networks to small networks servicing schools or small businesses. The task of establishing routes between ASes, called interdomain routing, is currently handled by the Border Gateway Protocol (BGP)—the core routing protocol of the Internet. BGP is one of the most critical pieces of the Internet’s infrastructure and can be regarded as the glue that holds the Internet together.

Over the past decade, routing with BGP has been studied from engineering, computational, game theoretic and economic perspectives. Combining algorithmic and economic considerations in the study of interdomain routing is natural, because the many separate domains that make up the Internet are independent economic agents that must jointly execute a distributed algorithm in order to route traffic. In addition, interdomain routing motivates exciting new questions in computer science, game theory, and economics.

A (Simplified) Model of Interdomain Routing

The following is a simplified model of interdomain routing, based on the seminal work of Thimothy Griffin and Gordon Wilfong, and on the game-theoretic model of Hagay Levin, Michael Schapira, and Aviv Zohar   Continue reading

# Impossibility Result for “Survivor”

Consider a set of $n$ agents and a directed graph where an edge $(i,j)$ means that agent $i$ supports or trusts agent $j$. We wish to choose a subset $C$ of size $k$ of trustworthy agents. Each agent’s first priority is to be included in $C$. We want to find a function from directed graphs of trust, to k-subsets $C$ of the vertices. We require two axioms

Axiom 1: If exactly one player is trusted by some other player then this player will be selected to the set $C$ of trustworthy players.

Axiom 2: A player cannot prevent not being selected to $C$ by misreporting his truthful judgement of his fellow players (even if he knows the way other players are going to vote).

Axiom 2 is referred to as “strategy proofness“.

Impossibility theorem (Alon, Fischer, Procaccia and Tennenholtz): For any $k$, $1\le k\le n-1$ there is no mechanism for choosing the $k$-subset $C$ of trustworthy agents that satisfies Axioms 1, 2.

A special case of the theorem, when $k=n-1$, can be described in terms of the TV reality game “survivor”. Continue reading

# Chess can be a Game of Luck

Can chess be a game of luck?

Let us consider the following two scenarios:

A) We have a chess tournament where each of forty chess players pay 50 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

B)  We have a chess tournament where each of forty chess players pay 20,000 dollars entrance fee and the winner takes the prize which is 80% of the the total entrance fees.

Before dealing with these two rather realistic scenarios let us consider the following more hypothetical situations.

C) Suppose that chess players have a quality measure that allows us to determine the probability that any one player will beat the other. Two players play and bet. The strong player bets 10 dollars  and the waek player bets according to the probability he will win. (So the expected gain of both player is zero.)

D)  Suppose again that chess players have a quality measure that allows us to determine the probability that any one players will beat the other. Two players play and bet. The strong player bets 100,000 dollars and the weak player bets according to the probability he will wins. (Again, the expected gain of both players is zero.)

When we analyze scenarios C and D the first question to ask is “What is the game?” In my opinion we need to consider the entire setting, so the “game” consists of both the chess itself and the betting around it. In cases C and D the betting aspects of the game are completely separated from the chess itself. We can suppose that the higher the stakes are, the higher the ingredient of luck of the combined game. It is reasonable to assume that version C) is mainly a game of skill and version D) is mainly a game of luck.

Now what about the following scenarios:

E) Two players play chess and bet 5 dollars.

Here the main ingredient is skill; the bet only adds a little spice to the game.

F) Two players play chess and bet 100,000 dollars.

Well, to the extent that such a game takes place at all, I would expect that the luck factor will be dominant. (Note that scenario F is not equivalent to the scenario where two players play, the winner gets 300,000 dollars and the loser gets 100,000 dollars.)

Let us go back to the original scenarios A) and B). Here too, I would consider the ingredients of luck and skill to be strongly dependant on the stakes. The setting of scenario A) can be quite compatible with a game of skill where the prizes give some extra incentives to participants (and rewards for the organizers), while in scenario B) it stands to reason that the luck/gambling factor will be dominant.

One critique against my opinion is: What about tennis tournaments where professional tennis players are playing on large amounts of prize money? Are professional tennis tournaments  games of luck? There is one major difference between this example and examples A and B above. In tennis tournaments there are very large prizes but the expected gain for a player is positive, all (or at least most) players can make a living by participating. This changes entirely the incentives. This is also the case for various high level professional chess tournaments.

For mathematicians there are a few things that sound strange in this analysis. The luck ingredient is not invariant under multiplying the stakes by a constant, and it is not invariant under giving (or taking) a fixed sum of money to the participants before the game starts. However, these aspects are crucial when we try to analyze the incentives and motives of players and, in my opinion,  it is a mistake to ignore them.

So my answer is: yes, chess can be a game of luck.

# Social Choice Talk

I took part in a workshop celebrating the publication of a new book on Social Choice by Shmuel Nitzan which took place at the Open University. (The book is in Hebrew, and an English version is forthcoming from Cambridge University Press.) It was a very interesting event and all the lectures were excellent. I thought of blogging about my lecture.

The main part of the lecture was about the four old theorems in the table above and about what should replace the two question marks. The left side of the table deals with properties of the majority voting rule for binary preferences. The right side of the table is about general voting rules. On the top tight is the famous Arrow Impossibility Theorem. The table is filled by two theorems I proved in 2002 (in this paper) and it now looks like this: Continue reading

# Basic Open Research and Failed Institutions – Imagine

Imagine if in the last ten years before the collapse, the huge failed financial and insurance institutions had had independent research units devoted to doing basic, open, and critical research on matters of relevance to the business, ethics, and future of these institutions. Might it have made a small difference for the better regarding the fate of these institutions?

[Full disclosure:] I make my living by doing basic research.

# The Hex-Voting-Rule (Not Recommended)

Blue wins – if there is a right to left continuous path of blue regions

Red wins – if there is north to south continuous path of red regions

(A region is red or blue according to the majority of voters.)

This method is very noise-sensitive.

# Malawi

Malawi

Here are two additional sectionettes from my “Notices of the AMS” book review entitled “Economic and Common Sense” on Steven Landsburg’s book “More Sex is Safe Sex – the unconventional wisdom of economics”.  Both sectionettes deal with Government intervention in economics. The first is about fertilizer subsidies in Malawi. This was a move made by Malawi’s government against the advice of the world bank and against standard market economic teachings. Judging from the outcomes of the last couple of years it was a successful move. The second is an anecdote about administrative measures the US government took against inflation in the early 1970s, as told by Bob Aumann. I do not know if these measures were successful.

Current events, the financial crisis and the attempted bailout make the topics of these little sectionettes of some relevance. (And so is the issue of “what do firms want” and the larger issue of “economics and common sense”.) I do not think that the dramatic and sad current financial crisis by itself is definite evidence to support more liberal forms of market economy (which I tend to favour) rather than more conservative versions. (Or the other way around.) In other words, I tend to think that a crisis of this nature can occur (and perhaps cannot even be avoided) under both economic systems. The issue of governmental intervention is also far from being clear.  The case for subsidies for fertilizers in a hunger-stricken country seems much clearer than (humongous) subsidies for financial institutions; both in terms of effectiveness and in terms of basic values of fairness and human dignity.   Continue reading

# The Prisoner’s Dilemma, Sympathy, and Yaari’s Challenge

### Correlation and Cooperation

In our spring school devoted to Arrow’s economics, Menahem Yaari gave a talk  entitled “correlation and cooperation.” It was about games as a model of people’s behavior, and Yaari made the following points:

It is an empirical fact that people (players in a game)  act in a correlated way,

It is unscientific not to take this into account (although this is not taken into account in game theory and economics).

### The prisoner’s dilemma

A basic example in game theory (which also played a central part in Yaari’s lecture) is the Prisoner’s dilemma. Let’s talk about this example a little, before getting to Yaari’s claims. Continue reading

# Arrow’s Economics 1

The annual Summer School in Economics at HU was directed until last year by Kenneth Arrow, along with Eyal Winter. Arrow decided this year to step down as a director and Eric Maskin is replacing him. The 2008 Summer School was devoted to Arrow’s economics. The list of speakers was quite impressive, with six lecturers who are Nobel Laureates. (Our local Institute for Advanced Study runs five schools every year, in Physics, Economics, Life Sciences, Jewish Studies, and Mathematics.)

## Economic puzzles told by Arrow

Let me tell you about three economics puzzles mentioned by Arrow in an earlier summer school. I doublechecked some details with Arrow himself; still, if my description contains errors I will be happy to be corrected. (Arrow spent a considerable amount of time talking with the workshop students. Another remarkable thing about him: he takes lecture notes! Is it a good idea to take detailed lecture notes at lectures? Let’s return to this question sometime.)

### Puzzle 1: Why is there unemployment?

Why is this even a puzzle? Because the economics teaching that “the market will clear” means that all people who can work will. A person who can work and is not working represents inefficiency, which is not supposed to exist in a competitive economy. Part of the issue is referred to as “friction” and accounts for economics processes being slow rather than instantaneous. But it appears to be true that there is more to unemployment than that. What can explain the 30% unemployment that was witnessed in the US in the 1930s?

Is this puzzle a scientific problem? You bet it is! And it is a fairly clear-cut scientific problem. I suppose there are several answers to this puzzle in the literature but we are far from a definite understanding of the issue.

### Puzzle 2: What is the reason for high volatility of prices in markets, say in stock markets?

The price of a stock, according to economics theory, represents the long-term value of the company. What accounts for the fact that the overall value of the entire stock market may fluctuate by more than 1% on a typical day? What accounts for fluctuations (more often drops) of 3-5% in one day? (Such fluctuations are not rare.) A famous question is to explain the one-day drop of 20% in October 1987. Continue reading

# What do Firms Want?

Here is another little sectionette from my book review  “Economics and Common Sense” on Steven Landsburg’s book “More sex is Safe Sex: The Unconventional Wisdom of Economics”, that just appeared on the AMS Notices site. Of course this topic can lead to a lovely discussion. Update (March 2011): Here is a related discussion on Noam Nisan’s blog in the context of research grants offered by Google.

What do firms want? Reading Landsburg’s book, one gets the impression that firms and their owners and executives just want to maximize their profits. They will avoid polluting the environment if and only if this is good for business. They will obey the law if and only if the cost/benefit tradeoff in violating the law are unfavorable.

It is not clear if this characterization of what firms want is just an assumption essential for developing the theory (which is reasonable), or an approximation of reality (which also sounds reasonable), or perhaps a solid precise description of reality (which as such sounds unreasonable), or maybe a normative teaching of economics theory (which sounds unfortunate), or perhaps even a representation of moral values (which also sounds unreasonable).

This description is simplistic even in the context of classical economic theory, Continue reading