Complexity and Simplicity in Economics (Simons Institute workshop, 2015)
2015-10-12..2015-10-16
Berkeley, United States
| title | author | length |
|---|---|---|
| The Emergent Structure of Simple Behaviors in Complex Networks | Nicole Immorlica | 51m |
Co-evolving network-plus-behavior models yield concrete, testable claims: a bounded-outdegree PD model with directed sponsored links (outdegree ≤ K)… | ||
| Revenue Maximization in Interdependent Value Settings | Shuchi Chawla | 33m |
Shows that a simple modification—reject each bidder with constant probability (here 1/2) then run Vickrey with reserves computed from survivors’ reported… | ||
| Timing “Versus” Matching: Thickness and Information in Dynamic Markets | Mohammad Akbarpour | 34m |
Model uses Poisson arrivals (rate m), independent edges with probability p and D = m·p as the expected degree, and agents hit an exponential “critical” clock… | ||
| On Maximizing Revenue for Multi-Item Auctions | Andrew Yao | 38m |
Proves a concrete constant-factor approximation for revenue in independent multi-item, multi-buyer auctions by decomposing the problem via an N-to-one… | ||
| Simple Mechanisms for a (Sub)Additive Buyer | Matt Weinberg | 35m |
Shows that for independent-item distributions the better of selling items separately or as one bundle gives a six approximation for additive buyers and a… | ||
| Algorithmic Bayesian Mechanism Design | Yang Cai | 35m |
Provides an algorithmic framework that computes exact Bayesian revenue-optimal mechanisms for multi-item additive bidders (items may be correlated) by solving… | ||
| The Substitution Metric and the Performance of Clock Auctions | Paul Milgrom | 49m |
Design for the U.S. incentive auction treats market clearing as a hard production problem: NP‑complete channel‑assignment (graph‑coloring/SAT with ~600,000… | ||
| Privacy, Substitutes, and Optimization in Deferred-Acceptance Clock Auctions | Ilya Segal | 33m |
Deferred-acceptance clock auctions are presented as a practical design: implemented for the FCC’s reverse incentive auction with ~2,500 stations and about… | ||
| Obviously Strategy-Proof Mechanisms | Shengwu Li | 33m |
Proposes obviously strategy-proof (OSP) as a stricter concept than weak dominance: a strategy is OSP if at any earliest divergence point the deviation’s best… | ||
| Non-Revelation Mechanism Design: Inference, Optimization, and Approximation | Jason Hartline | 45m |
Shows that the first-price position auction has a unique symmetric Bayes–Nash equilibrium that is efficient, and uses the revenue equivalence/payment-identity… | ||
| Econometrics for Learning Agents | Vasilis Syrgkanis | 27m |
Claim: bidders are best-modeled as vanishing-regret learning agents, not Nash equilibria, so values can be inferred from bid histories. Method: convert regret… | ||
| Smoothness and Pricing: Near-Optimal Outcomes in Markets Large and Small | Brendan Lucier | 47m |
Shows that simple posted prices achieve a constant (about 1/2) of optimal expected welfare for Bayes settings with XOS/submodular valuations by reading prices… | ||
| Complexity in AGT Update: Nash Approximability and Simultaneous Auctions | Christos Papadimitriou | 35m |
Christos Papadimitriou, UC Berkeley
Complexity and Simplicity in Economics
https://simons.berkeley.edu/talks/christos-papadimitriou-10-14 | ||
| Competition and Simple Auctions | Mallesh M. Pai | 33m |
Shows necessary conditions for a seller’s best response when competing against M−1 rivals who commit to second‑price, zero‑reserve auctions: optimality… | ||
| Consensus Expectations and Conventions | Ben Golub | 48m |
Shows that iterated expectations x_i^n (taken as Cesàro averages) converge to a nonrandom consensus under a joint connectedness condition and that consensus… | ||
| Dynamics of Evolving Social Groups | Sigal Oren | 29m |
Model uses opinions in [0,1], two uniformly drawn candidates per round, members vote for the closer candidate (homophily). Under consensus rule the… | ||
| Decision Making at Scale: Algorithms, Mechanisms, and Platforms | Ashish Goel | 37m |
An algorithm called triadic consensus repeatedly samples random triads, asks each triad to pick its one-median, replaces the three sampled participants with… | ||
| First Price Auctions with General Information Structures: Implications for Bidding and Revenue | Ben Brooks | 46m |
Derives tight worst‑case bounds on seller revenue in first‑price auctions when the information structure is unknown, proving a global lower bound and… | ||
| The Query Complexity of Correlated Equilibria | Sergiu Hart | 27m |
Correlated equilibria with two actions per player admit randomized algorithms find ε-CE with poly(n) queries, produced by regret‑based dynamics that run O((log… | ||
| On the Borders of Border’s Theorem | Noam Nisan | 35m |
Explains when the Border theorem gives a full reduced-form LP characterization and when it cannot be extended: shows computing exact optimal revenue for a… | ||
| Strong Duality for a Multiple Good Monopolist | Christos Tzamos | 32m |
Proves strong duality for the single-buyer multi-item revenue problem by mapping the primal (maximize a convex 1-Lipschitz utility functional) to an… | ||
| Robustness and Separation in Multidimensional Mechanism Design | Gabriel Carroll | 32m |
Claim: when only marginal type distributions are known and correlation is unknown, the worst-case revenue guarantee equals the sum of single-item optimal… | ||
| Selling Experiments | Dirk Bergemann | 48m |
Model frames information sales as Blackwell experiments, seller maximizes revenue subject to incentive and participation constraints by offering a menu of… | ||
| The Sample Complexity of Revenue Maximization | Tim Roughgarden | 35m |
Proposes using the statistical learning notion pseudo-dimension to measure mechanism complexity and shows low pseudo-dimension implies polynomial sample… | ||
| How Well Do Prices Coordinate Markets | Aaron Roth | 33m |
Price vectors are tested as coordinators: minimal Walrasian prices can leave many buyers indifferent, so a genericity condition (valuations linearly… | ||
| Multi-dimensional Virtual Values and Second-degree Price Discrimination | Nima Haghpanah | 34m |
Claims that posting a single price for the favorite outcome is revenue-optimal whenever the high-value and discount factor are positively correlated… | ||
| Computational Efficiency Requires Simple Taxation | Shahar Dobzinski | 35m |
Main claim: for broad multi-parameter domains the taxation indexing complexity ≤ communication complexity + 1, so the number of different menus a truthful… | ||
| nothing matches | ||