NYCE III

NY Area CS and Economics day was on Friday, Oct 15th at the NY Academy of Sciences. Organizers Christian Borgs, Michael Kearns, Sebastien Lahaie and Vahab Mirrokni put together a great program. The Academy and in particular, Jamie Kass, did a fabulous job of coordinating and hosting the meeting. There were 136 attendees. Besides researchers from local neighborhood as far away as Chicago, IL and Redmond, WA, there were preregistered attendees from Opera Solutions, Deutsche Bank, Benedetto Laskay LLC, Knight Equity Markets LP, Analytical Synthesis, Mayera Software Solutions, Delta Vega LLC, SpeakToMe Inc., Bloomberg LP etc.

Mihalis Yannakakis gave an excellent overarching talk on games from existence of equilibrium, uniqueness/multiplicity/selection of equilibrium, dynamics and convergence to computational issues of finding them. He started with the simple example of neural networks in which each node takes \pm 1, and a node is stable if it agrees with weighted majority of neighbors (edges have weights.) Hopfield 82 shows that all undirected networks have one or more stable configurations. Further, asynchronous dynamics in which nodes individually adjust their label eventually reaches stable config that can be seen using the potential \sum_over_edges w(u,v)s(u)s(v). So, stable config = local optima under node flips. This motivates class PLS: poly local search from JPY85. Neural network stable config finding is PLS-complete. Dynamics takes exponential time for any pivoting (local improvement) rule. [SY] Further, PLS can't be NP hard unless NP=co-NP. This is a game in which stable config == pure nash equilibria. The second example was congestion games. strategy: subset of resources; cost is sum of all costs of resources in a strategy; cost of a resource is number of players using it. Rosenthal: all congestion games have one or more pure equilibria. Again potential argument. There are games in PLS, but don't know if they are in P. Simple stochastic games due to Condon. 2 player, random max/min game. Equilibrium is a pair of strategies that are best responses to each other, value of the game = prob (one wins). There is pure stationary dist. Open: is it in P? The next example: every finite game has mixed nash eq.; proof uses Brouwer's FPT. Fixed points == mixed equilibria. Message is that many games => FPT. Basically solve x=F(x). Challenge is computation: continuous prob, irrational numbers in solutions. Class FIXP [EY]: problems cast as FPT for Brouwer functions computed in poly number of steps in a restricted computing model. 3-player nash is FIXP complete. tech: equate FP to nash equilibrium by translation+scaling only. It is in PSPACE, proof uses existential theory of reals. Lower bound: NP? open. Related to square-root-sum problem, also power of unit-cost arithmetic model (even with exp word size). We know unit cost integer arith model == PSPACE. For P-time piecewise linear functions => there exists rational FP. Can be achieved by not allowing mult, div == linear FIXP == PPAD. Simple stochastic game, market eq with separable piecewise concave utilities, etc. are examples. For market dynamics, complexity of price adjustment mechanisms -> PY10. Bunch of prob, math understood, not algorithmics. (During question time: q [cole]: neural networks, weights should have large number of bits? Y: natural dynamics will converge in time proportional to weights. q: will synchronic updates work with random updates for neural networks? Y: yes. will break cycles. exp lower bound holds for all of them, no matter what. speed of convergence of MDP open for 25 years, exponential lower bound.) Mihalis is a Master, gliding easily between algorithms, structural complexity and game theory in his presentation and answers to questions!

Sham Kakade spoke about optimal dynamic mechanisms. The problem is, seller wants maximum revenue, they can do whatever. Ignore incentives => dynamic stochastic optimization problem. Static => Myerson. Dynamic: maximize social efficiency has been considered by Parkes+Singh, Eso and Szentes? The talk was about dynamic mechanisms that maximize revenue. Membership mechanism: buyer picks price p, pays membership M(p), then gets all items at price p. Not direct mechanism, Buyer still faces hard problem because the value may change with time. Privacy: only scalar values revealed by Buyer, so has some privacy. q: explicit construction of M(p)? yes. delicate. reduces to dynamic VCG! M(p) somehow translates revenue to efficiency. In general, designing optimal dynamic mechanism is a hard problem, Sham obviously has a feel for the nuances of the problem, and presented a lot of insights. Robert Almgren gave a nice talk about ranking portfolios. There are multiple rankings. There exists a set of linear inequalities to express a return vector r. There is a cone of satisfiable r. Compare portfolios 1: w_1 > w_2 for all possible r's. Then, portfolios not always comparable. Compare portfolios 2: w_1 > w_2 for more r's than the other, so, compare in measures. All performances are in ratios, so even if different units along directions, doesn't matter. Use centroids of cones to rank. This talk generated a lot of questions, including one by Boaz Barak exploring the robustness of these measures when one splits a portfolio into smaller units.

From Vahab and Sebastien:
The rump session featured short talks spanning many different areas including auction design, computational game theory, social networks, and recommendation systems. Azarakhsh Malekian talked about computing Walrasian equilibria with general non-quasi-linear utility functions; Vasilis Gkatzelis talked about coordination mechanisms for machine scheduling; Gagan Goel talked about revenue maximization in TV ad auctions with submodular utility functions; Sharad Goel talked about learning social influence functions; Xi Chen talked about computing market equilibria in the presence of network externalities; Sanmay Das discussed experimental design to compare prediction market structures; Bhaskar DasGupta talked about stochastic budget optimization in ad auctions; Mohammad Irfan talked about influence games over social networks; Beibei Li presented a personalized hotel recommendation system; Tanmoy Chakraborty discussed market making in mean reversion price models; and Sven Seuken talked about user interface design for markets.

Bobby Kleinberg presented work on modifying algorithms to make them incentive-compatible in Bayesian multi-parameter settings. He argued that in many situations, we may come up with a sophisticated allocation algorithm to maximize social welfare, and we would like to convert our algorithm to a mechanism with the right incentives and the same social welfare. If we insist on dominant strategy equilibria, this is not possible, but if we settle with Bayes-Nash equilibria, it might be possible. Bobby described joint work with Jason Hartline and Azaraksh Malekian in which they give a way to convert any approximation algorithm for maximizing social welfare to an incentive-compatible mechanism with the same approximation factor under Bayes-Nash equilibrium. He described how they built on earlier work of Hartline and Lucier for the single-parameter setting, and gave an approximate scheme for the multi-parameter setting. He had this take-away message: "Converting approximation algorithms to incentive compatible-mechanisms might be easier than we thought, if we are happy with Bayes-Nash equilibrium as a solution concept."

Hal Varian gave a two-part talk about two cute problems in ad auctions and general mechanism design. First he talked about reformulating the standard sponsored search auction so that in the event of a click, other than charging the clicked advertiser the next bid, the auctioneer pays a fixed amount to the bidders who are ranked higher than the advertiser. This turns out to be an ingenious way to implement the VCG payment rule, and removes the motivation for underbidding as advertisers get paid by clicks from advertisers below them. In the second half, Hal discussed optimal prior-free auctions and the idea of computing an optimal price based on the bids of other users. This was inspired by the auction by the work of Baliga and Vohra. Through a simple family of instances, Hal argued that this can give a simple prior-free auction that incurs the right incentives and optimal revenue in most scenarios.