After an early morning injection of much needed caffeine, Team Northwestern was ready for the next round of talks. Today's program consisted of talks more related to our interests than the previous days.
In the morning, 2 papers related to the computational complexity of equilibria. In the first one Xi Chen, Decheng Dai, Ye Du and Shang-Hua Teng consider Arrow-Debreu markets in which agents' utilities are additively separable and piecewise linear concave. In this context, via an interesting reduction from 2-player games, they were able to show that the problem is PPAD-complete, confirming the fact that even additively separable concave utilities are not easy to deal with. In another talk, Laura J. Poplawski et al. introduced a simple PPAD-complete game, claiming it is a natural candidate for PPAD-completeness reductions. To support their claim they show how it naturally reduces to known (and also to many unknown) PPAD-complete problems.
Also in the morning session an interesting paper by Andrea Montanari and Amin Saberi talked about coordination games and their relation to spread of news, technologies and other social phenomena on networks. They were able to show how convergence times directly depend on certain graph properties.
A bit later in the morning, the winning student papers were presented. Alexander Sherstov showed his work on strong improvements of the bounds for the degree of intersecting halfspaces. Jonah Sherman was next, presenting improvements on sparsest cut algorithms.
Bringing the day to a close, session 8B covered three of our favorite topics: social network formation, revenue maximization, and mechanism design. What more could we ask for in one session?
But when do we get to see pandas?
ReplyDeleteIn this context, via an interesting reduction from 2-player games, they were able to show that the problem is PPAD-complete
ReplyDeleteActually, they only show PPAD-hardness.