University of Cambridge > Talks.cam > Optimization and Incentives Seminar > Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

  Browse A-Z

Log in

Cambridge users (raven)details Other usersdetails No account?details

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

Pathways to Equilibria, Pretty Pictures and Diagrams (PPAD)

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Felix Fischer.

Existence of an equilibrium in various economic models can be shown by following a certain combinatorially defined path, for example of edges of a labeled polytope similar to the simplex algorithm for linear programming. In addition, such a path has a direction that defines the ``index’’ of an equilibrium. Examples include Sperner’s lemma about completely labeled simplices and Nash equilibria in games. We present a general model of “pivoting systems” that shows the essence of the path-following and the directedness argument. We also present a connection of bimatrix games where the paths are exponentially long with signed perfect matchings in Euler graphs, and an algorithm that gives a polynomial-time “shortcut” for these paths. We also present a concept of orientation for the “Euler complexes” recently introduced by Edmonds, which generalizes the orientability of abstract simplicial manifolds. Our exposition uses colorful pictures and examples wherever possible.

(Joint work with Marta Maria Casetti, Julian Merschen and Laszlo Vegh.)

This talk is part of the Optimization and Incentives Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Faculty of Music Colloquia Scott Polar Research Institute - Polar Physical Sciences Seminar Friday Morning Seminars, Dept of Veterinary Medicine Cambridge Neurological Society Humanitarian Centre Transition Cambridge

Other talks

Lunchtime Talk: Helen's Bedroom Statistical analysis of biotherapeutic datasets to facilitate early ‘Critical Quality Attribute’ characterization. Challenges to monetary policy in a global context Social Representations of Women who Live as Men in Northern Albania Martin Roth: »Widerrede!« Statistical Learning Theory Discovering regulators of insulin output with flies and human islets: implications for diabetes and pancreas cancer The Gopakumar-Vafa conjecture for symplectic manifolds 100 Problems around Scalar Curvature Throwing light on organocatalysis: new opportunities in enantioselective synthesis Coin Betting for Backprop without Learning Rates and More Emissions and Chemistry of air pollution in London and Beijing: a tale of two cities.
 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity