Filed under: Uncategorized | Tags: Correlated Equilibrium, Mediators, Nash Equilibrium, Network Effects, theory
[The following blog report on SAGT was written by my student George Saad – Ed]
The Sixth International Symposium on Algorithm Game Theory (SAGT) was held last week in Aachen, Germany. SAGT is an algorithmic game theory conference. This year, it provided seven sessions of talks about topics like Voting, Price of Anarchy, Congestion Games, Computational Aspect, Alternative Solution Concepts, Social Networks and Mechanism Design.
In sessions 3 and 6, there were two talks that I found particularly interesting. First, in session 3 (Congestion Games), there was an interesting presentation on the strict and non-strict equilibria in anti-coordination games, by Kun, Powers and Reyzin. An application of anti-coordination games concerns the economic relationship among countries, where a country would rather produce a commodity that neighboring countries do not.
This game is represented as a graph, in which the players are nodes and the desire for anti-coordination between players is represented by edges. In this research, Kun et al showed that finding whether or not there is a strict equilibrium in an undirected graph is NP-Hard. Also they proved that finding whether or not there is a non-strict equilibrium in a directed graph is NP-Hard. The reductions for undirected graphs were interesting and involved a reduction from 3-SAT using a certain type of gadget.
“Logic will get you from A to B. Imagination will take you everywhere.” – Albert Einstein.
In session 6 (Social Networks), there was an interesting talk about inefficiency in social context games. In this type of games, the players are not completely selfish, instead, they have preferences to cooperate with certain players. The authors provided bounds for the Price of Anarchy in several games. But they did not consider mediation. It may be interesting to be considered as a future work.
“If you can’t explain it simply, you don’t understand it well enough.” – Albert Einstein.
In session 2, I presented my paper “The Power of Mediation in an Extended El-Farol Game“. In the El-Farol game there are n players, and each player decides whether to “go” to a bar (called El-Farol) or to “stay” at home. Each player pays a cost corresponds to his action, where the cost of each player that stays is 1, while the cost of each player that goes is given by a function of the total number of players that go. In the traditional El Farol game, the cost function of the player that goes is linearly increasing with respect to the number of players that go (as the bar gets more crowded, it’s less enjoyable which corresponds more cost). However, in our variant, this function first decreases and then increases, having both positive and negative network effects. We showed that for such a function, a mediator – a trusted coordinator that gives advice to each player in such a way that implements a correlated equilibrium – can significantly decrease the overall social cost.
The subject of the paper seemed interesting for many students, and I had many offline discussions about further extensions of the El-Farol game. For instance, what would be the best-correlated equilibrium when the cost function is quadratic? Also what if there are different types of players and each type has a different cost function?
“The important thing is not to stop questioning.” – Albert Einstein
After the talks, I had an interesting discussion with German students about the design of roads in Aachen, Germany and in United States. When a foreigner goes from a source to a destination in Aachen, most probably, he gets lost even if he has a map. The question was why the roads in Aachen are designed like spaghetti. The roads in Aachen are basically designed as nested circles and straight lines from the center to these circles. However, in Albuquerque, the roads are mostly designed as a grid.
One argument in our discussion was measuring the expected walking distance from any two arbitrary points given that the two models have the same area. Also we discussed the traffic (crowd) load. We assumed that people in both models have powerful minds (processors) and infinite memory size to facilitate finding the shortest paths quickly.
Furthermore, we discussed slightly about the case where people don’t have infinitely powerful minds. This seems connected to the problem of making change. In currency systems, the currency units are issued in such a way that the people can compute change quickly, rather than necessarily always allowing for the minimum number of units exchanged in the purchase process.
This was the midterm for my grad algorithms class. It was inspired by binge watching seasons 1-4 of Breaking Bad (yes I’m a bit behind).