Stability in Tranding Networks

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,800
Published on ● Video Link: https://www.youtube.com/watch?v=h8fnzqAXX6E


Duration: 42:25
287 views
5

Zsuzsanna Jankó (Corvinus University of Budapest)
https://simons.berkeley.edu/talks/zsuzsanna-janko-corvinus-university-budapest-2023-10-27
Online and Matching-Based Market Design

We consider a model of matching in trading networks in which firms can enter into bilateral contracts. In trading networks, stable outcomes, which are immune to deviations of arbitrary sets of firms, may not exist. We define a solution concept called trail-stability. Trail-stable outcomes are immune to consecutive, pairwise deviations between linked firms. We show that any trading network with bilateral contracts has a trail-stable outcome whenever firms’ choice functions satisfy the full substitutability condition.

However, the existence of stable outcomes—immune to deviations by arbitrary sets of agents—is an NP-hard problem in trading networks. We also show that even verifying whether a given outcome is stable is NP-hard in trading networks.



Other Videos By Simons Institute for the Theory of Computing


2023-11-27Exploiting geometric structure in (matrix-valued) optimization
2023-11-21Towards Interpretable Data Science
2023-11-13Introduction and Program Highlights
2023-11-13Modern Paradigms in Generalization
2023-11-13Challenges in Research on Practical Algorithms
2023-11-13Well-Being, AI, and You
2023-11-13Quantum Algorithms, Complexity, and Fault Tolerance: Sandy Irani
2023-11-13How looking at a problem quantumly could solve it faster?
2023-11-01Streaming (Synchronous), Recursion, and Incremental Computation
2023-10-28Complementarities and Externalities
2023-10-28Stability in Tranding Networks
2023-10-28High Dimensional Calibration for Rational Decision Making
2023-10-28LP-Duality and the Cores of Games
2023-10-28Auto-bidding, Auctions, and Ad Allocation
2023-10-28Matching and Disclosure
2023-10-27Simple Proofs of Important Results in Market Design
2023-10-27Stable Matching by Optimal Transport
2023-10-27Revealed Preferences of One-Sided Matching
2023-10-27Strict Core Stability and Strategy-Proofness for Hedonic Games with Friend-Oriented Preferences
2023-10-27Market Design for Priority-Based Assignment with Distributional Objectives
2023-10-27Estimating Separable Matching Models


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Online and Matching-Based Market Design
Zsuzsanna Jankó