Seminar
| Parent Program: | |
|---|---|
| Location: | SLMath: Eisenbud Auditorium, Online/Virtual |
Simple Approximation Algorithms for Maximum Size Stable and Popular Matching Problems
Automated Market Makers in Prediction Markets and Decentralized Finance
"Simple Approximation Algorithms for Maximum Size Stable and Popular Matching Problems" - Gergely Csáji
Abstract:
We give simple approximation algorithms for common generalizations of many previously studied extensions of the stable and popular matching problems with ties. These generalizations include the existence of critical agents, amongst whom we must match as much as possible, free edges, that cannot be blocking edges and Δ-stabilities, which mean that for an edge to block, the improvement should be large enough on one or both sides and many more. We give a 3/2-approximation algorithm for finding a maximum size stable matching in our general model and a 4/3-approximation algorithm for finding a maximum size popular matching. We also show that these ratios are best possible under known complexity theoretic assumptions. This also answers an open question by Askalidis et al. (2013) about the existence of a 3/2-approximation algorithm for the Max-SMTI problem with free edges.
This demonstrates well that our edge duplication technique can grasp the underlying essence of these problems quite well and have the potential to be able to solve many future applications too.
"Automated Market Makers in Prediction Markets and Decentralized Finance" - Rafael Frongillo
Abstract: Prediction markets are those designed to elicit probabilities of future events by allowing traders to buy and sell securities whose payoffs are tied to those events. Automated market makers were first proposed by Hanson (2003) to solve thin market problems in prediction markets. Recently, they have also become a popular tool in decentralized finance, to run exchanges for cryptocurrencies and other assets. The stark contrasts between these two settings led to the impression that these algorithms were only loosely related. We will see that, in fact, they are exactly the same algorithms. This observation also shows that desirable market-making axioms are equivalent to desirable information-elicitation axioms, i.e., markets are good at facilitating trade if and only if they are good at revealing beliefs. It also gives a useful tool to translate results between the two fields.
We will illustrate this latter point with the practice of liquidity provisioning, wherein external parties provide liquidity to the market in exchange for a cut of the trading fees. Thus far, only a handful of specific protocols for liquidity provisioning have been proposed, such as Uniswap V2 and V3, but the design space from which one could choose a different protocol has been far from clear. Using the duality above, we show that one can view liquidity provisioning very broadly as the practice of running several market makers "in parallel": each market maker provides its own liquidity, yet the combined group can operate as a single coherent market. This general protocol recovers Uniswap V2 and V3 as special cases, and opens the door to new protocols which may have advantages in practice.
No Notes/Supplements Uploaded