Algorithmic Mechanism Design with Investment

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


Duration: 48:43
523 views
17

Paul Milgrom (Stanford University)
https://simons.berkeley.edu/talks/paul-milgrom-stanford-university-2023-10-26
Online and Matching-Based Market Design

Some approximation algorithms guarantee nearly 100% of the optimal welfare in the allocation problem but guarantee only 0% when accounting for investment incentives. An algorithm’s allocative and investment guarantees coincide if and only if its confirming negative externalities are sufficiently small. We introduce fast approximation algorithms for the knapsack problem that have no confirming negative externalities and guarantee close to 100% for both allocation and investment.



Other Videos By Simons Institute for the Theory of Computing


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
2023-10-27The Intractability of Hylland-Zeckhauser and its Aftermath
2023-10-27Endogenous Market Formation: Theory and Evidence from Chilean College Admissions
2023-10-26Algorithmic Mechanism Design with Investment
2023-10-20Utilizing Structure in Combinatorial Solving and Reasoning
2023-10-20Approximating the TV Distance Between Two Product Distributions
2023-10-20Tractable Control for Autoregressive Language Generation
2023-10-20On Finding Modes of Gaussian Sum-Product Networks
2023-10-20Marginal Determinism in Structured Decomposable Circuits
2023-10-19Weighted Model Integration
2023-10-19An Approximate Skolem Function Counter
2023-10-19Subtractive Mixture Models: Representation and Learning
2023-10-19The Rise of Tractable Circuits: From Cryptography to Continuous Generative Models
2023-10-19Decision Diagrams for Efficient Inference and Optimization in Expressive Discrete+Continuous Domains


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