Market Algorithms Talks
On Wednesday, I heard a few talks on "market algorithms".
Christos Papadimitriou (think Che Guevara T-shirt, motorcycle leather jacket) described many results. First, departing from Nash equilibria of games, Christos focused on Arrow-Debreu market pricing and noted that it assumed convex production (hence, no economies of scale). Instead, the proposal is to consider "complexity equilibria". The main result was, "any poly bounded agents will be stuck in a dense market". This work is likely to have tentacles, even reaching into different measures for quantifying the density of markets. Second, Christos revisited Nash equilibria and focused on equilibria selection: Finding Nash equilibria by any of the standard known methods (eg., Lemke-Howson, Homotopy method) is PSPACE complete (also true for approximate equilibria to some extent). Then, continuing with Nash's theorem, Christos pointed out that it deals with maximizing expectations (E) and does not model risk, insurance, etc. He gave a general formulation of studying games with risk and defined a new concept of V-Nash equilibrium. When does Nash Theorem hold with this concept? Yes --- exists and as easy to compute as standard Nash equilibrium --- for E+Var, E+ Prob(X>c) and so on, and No --- may not exist, NP hard to tell if it does --- for E-Var, and others. Finally, he turned to auctions, and considered combining welfare and revenue. Contrary to conventional methods of considering linear combinations, the mentioned the result that the Pareto curve (deterministic auctions, independent, random values) is not convex and in general is intractable. This was, as usual, an inspiring talk from a maestro.
Sudipto Guha (who later regaled with stories of dusty travels in Peru and Nepal) gave a lecture, equally masterly, on ad allocation problems. It is tempting to see the ad allocation problems in a vast grid of offline vs online, weighted by CTR/Conversions, budgeted or not, or optimization vs explore-exploit a la multiarm bandit, and so on, and indeed it may be natural to navigate this vast space in that cell by cell manner. But Sudipto chose a many-layered presentation, first pointing out that a key is to consider the timing and via a series of examples, pointed out world was not "Here’s the input and the function, go …" but rather, "Unsure of the input, discover the input and the function as you proceed ..." Thereafter, Sudipto focused on a concrete example, Multiarm Bandit (MAB) type problems where playing an arm secured only a delayed response. There are nuances in setting up the benchmark to compare ones' algorithms, the techniques even more detailed as Sudipto described a series of transformations to make the problem LP-amenable. He finished with a host of MAB problems, even more complex, and yet to be tackled. MAB is a crowded space in CS beyond algorithms research, and algorithms researchers are bringing genuine insights. Mental note to follow this literature more.
There were other talks (Jason Hartline, Suchi Chawla, Mukund Sundarajan, Vahab Mirrokni, Aranyak Mehta, Andrea Montanari) as well, that alas I am not able to summarize here now.
ps: For those who dont know Che, he is the one who wears Bart Simpson T-shirt.
pps: Sudipto's awesome quote that needs some time to parse. "Diagonalize this!
* There is a prior (consistent) * There is no prior (is it self consistent?)".
Christos Papadimitriou (think Che Guevara T-shirt, motorcycle leather jacket) described many results. First, departing from Nash equilibria of games, Christos focused on Arrow-Debreu market pricing and noted that it assumed convex production (hence, no economies of scale). Instead, the proposal is to consider "complexity equilibria". The main result was, "any poly bounded agents will be stuck in a dense market". This work is likely to have tentacles, even reaching into different measures for quantifying the density of markets. Second, Christos revisited Nash equilibria and focused on equilibria selection: Finding Nash equilibria by any of the standard known methods (eg., Lemke-Howson, Homotopy method) is PSPACE complete (also true for approximate equilibria to some extent). Then, continuing with Nash's theorem, Christos pointed out that it deals with maximizing expectations (E) and does not model risk, insurance, etc. He gave a general formulation of studying games with risk and defined a new concept of V-Nash equilibrium. When does Nash Theorem hold with this concept? Yes --- exists and as easy to compute as standard Nash equilibrium --- for E+Var, E+ Prob(X>c) and so on, and No --- may not exist, NP hard to tell if it does --- for E-Var, and others. Finally, he turned to auctions, and considered combining welfare and revenue. Contrary to conventional methods of considering linear combinations, the mentioned the result that the Pareto curve (deterministic auctions, independent, random values) is not convex and in general is intractable. This was, as usual, an inspiring talk from a maestro.
Sudipto Guha (who later regaled with stories of dusty travels in Peru and Nepal) gave a lecture, equally masterly, on ad allocation problems. It is tempting to see the ad allocation problems in a vast grid of offline vs online, weighted by CTR/Conversions, budgeted or not, or optimization vs explore-exploit a la multiarm bandit, and so on, and indeed it may be natural to navigate this vast space in that cell by cell manner. But Sudipto chose a many-layered presentation, first pointing out that a key is to consider the timing and via a series of examples, pointed out world was not "Here’s the input and the function, go …" but rather, "Unsure of the input, discover the input and the function as you proceed ..." Thereafter, Sudipto focused on a concrete example, Multiarm Bandit (MAB) type problems where playing an arm secured only a delayed response. There are nuances in setting up the benchmark to compare ones' algorithms, the techniques even more detailed as Sudipto described a series of transformations to make the problem LP-amenable. He finished with a host of MAB problems, even more complex, and yet to be tackled. MAB is a crowded space in CS beyond algorithms research, and algorithms researchers are bringing genuine insights. Mental note to follow this literature more.
There were other talks (Jason Hartline, Suchi Chawla, Mukund Sundarajan, Vahab Mirrokni, Aranyak Mehta, Andrea Montanari) as well, that alas I am not able to summarize here now.
ps: For those who dont know Che, he is the one who wears Bart Simpson T-shirt.
pps: Sudipto's awesome quote that needs some time to parse. "Diagonalize this!
* There is a prior (consistent) * There is no prior (is it self consistent?)".
Labels: aggregator
posted by metoo at 4:18 AM
0 Comments:
Post a Comment
<< Home