EC 2024 Workshop
INFORMS Workshop on Market Design

July 8th, 2024 at Yale University in New Haven

About this Workshop

The 2024 INFORMS Workshop on Market Design will be held on July 8th, 2024 in conjunction with the EC 2024 conference. The workshop will bring together researchers and practitioners that work on market design, and will represent a broad range of perspectives from more theoretical to more applied and empirical work. As with previous iterations, the workshop is sponsored and organized by the INFORMS Section on Auctions and Market Design, i.e., the workshop is a successor of

Workshop Theme

Market design is a field of applied and theoretical research that sits comfortably on the intersection of computer science, economics, and operations research. In recent decades, the theory and applications of market design have blossomed. In this workshop, we will focus on a set of promising, new applications of market design. In particular, we are interested in applications of market design which involve optimization with complex allocation constraints, vast datasets and machine learning, and dynamic pricing issues. We also want to explore research areas which, despite receiving theoretical attention, have not yet made an impact on practice. We are also interested in empirical work on evaluating mechanisms and approaches in practice. Topics include but are not limited to:

Machine learning and generative AI in market design
Mathematical optimization in markets
Pricing and competitive equilibria in markets
Iterative multi-object auctions
Matching with constraints and complex preferences

Workshop Format

The workshop will be held in conjunction with EC 2024 at Yale University in New Haven. Please see the main EC website for details on how to register for the conference and the workshop.

The workshop will consist of 6-8 invited talks, from academics and practitioners in Computer Science, Economics, and Operations Research. Speakers and program will be posted on this website soon.

In addition to the invited talks, there will be a contributed poster session. Please see the rubric "Call for Posters" below on instructions how to submit your work.

Confirmed Speakers

Shuchi Chawla

The University of Texas at Austin

Negin Golrezaei

MIT

Yannai Gonczarowski

Harvard University

Thodoris Lykouris

MIT

Aranyak Mehta

Google Research

Zhuoran Yang

Yale University

Program (in Progress)

8:00-8:30 Breakfast

8:30-9:15 Zhuoran Yang (Yale)

STRIDE: A Tool-Assisted LLM Agent Framework for Strategic and Interactive Decision-Making

Large Language Models (LLMs) like GPT-4 have revolutionized natural language processing, showing remarkable linguistic proficiency and reasoning capabilities. However, their application in strategic multi-agent decision-making environments is hampered by significant limitations including poor mathematical reasoning, difficulty in following instructions, and a tendency to generate incorrect information. These deficiencies hinder their performance in strategic and interactive tasks that demand adherence to nuanced game rules, long-term planning, exploration in unknown environments, and anticipation of opponents' moves. To overcome these obstacles, this paper presents a novel LLM agent framework equipped with memory and specialized tools to enhance their strategic decision-making capabilities. We deploy the tools in a number of economically important environments, in particular bilateral bargaining and multi-agent and dynamic mechanism design. We employ quantitative metrics to assess the framework's performance in various strategic decision-making problems. Our findings establish that our enhanced framework significantly improves the strategic decision-making capability of LLMs. While we highlight the inherent limitations of current LLM models, we demonstrate the improvements through targeted enhancements, suggesting a promising direction for future developments in LLM applications for interactive environments.

Joint work with Chuanhao Li, Runhan Yang, Tiankai Li, Milad Bafarassat, Dirk Bergemann

Link to paper: https://arxiv.org/abs/2405.16376

9:15-10:00 Yannai Gonczarowski (Harvard)

Zero-Knowledge Mechanisms

A powerful feature in mechanism design is the ability to irrevocably commit to the rules of a mechanism. Commitment is achieved by public declaration, which enables players to verify incentive properties in advance and the outcome in retrospect. However, public declaration can reveal superfluous information that the mechanism designer might prefer not to disclose, such as her target function or private costs. Avoiding this may be possible via a trusted mediator; however, the availability of a trust\emph{worthy} mediator, especially if mechanism secrecy must be maintained for years, might be unrealistic. We propose a new approach to commitment, and show how to commit to, and run, \emph{any given mechanism} without disclosing it, while enabling the verification of incentive properties and the outcome---all without the need for any mediators. Our framework is based on zero-knowledge proofs---a cornerstone of modern cryptographic theory. Applications include non-mediated bargaining with hidden yet binding offers.

Joint work with Ran Canetti and Amos Fiat.

Link to paper: https://arxiv.org/abs/2302.05590

10:00-10:30 Coffee break

10:30-11:00 Lightning Talks (Poster session)

11:00-12:00 Poster Session

12:00-13:30 Lunch break

13:30-14:15 Thodoris Lykouris (MIT)

Learning to Defer in Content Moderation: The Human-AI Interplay

Ensuring successful content moderation is vital for a healthy online social platform where it is necessary to responsively remove harmful posts without jeopardizing non-harmful content. Due to the high-volume nature of online posts, human-only moderation is operationally challenging, and platforms often employ a human-AI collaboration approach. A typical heuristic estimates the expected harmfulness of incoming posts and uses fixed thresholds to decide whether to remove the post and whether to send it for human review. This disregards the uncertainty in the machine learning estimation, the time-varying element of human review capacity and post arrivals, and the selective sampling in the dataset (humans only review posts filtered by the admission algorithm). We introduce a model to capture this human-AI interplay. Our algorithm observes contextual information for posts, makes classification and admission decisions, and schedules posts for human review. Only admitted posts receive human reviews on their harmfulness. These reviews help educate the machine-learning algorithms but are delayed due to congestion in the human review system. We propose a near-optimal learning algorithm that balances the classification loss from a selectively sampled dataset, the idiosyncratic loss of non-reviewed posts, and the delay loss of having congestion in the human review system. To the best of our knowledge, this is the first result for online learning in contextual queueing systems and hence our analytical framework may be of independent interest.

Joint work with Wentao Weng.

Link to paper: https://arxiv.org/pdf/2402.12237

14:15-15:00 Negin Golrezaei (MIT)

Bidding in Uniform Price Auctions for Value Maximizing Buyers

We study the problem of bidding in uniform price auctions widely used in practice. Although these auctions are non-truthful for bidders with quasilinear utility functions, several empirical findings suggest that the auction format induces truthful bidding from the bidders. We attribute this difference in theory and practice to the assumption of the behavioral model of the bidders. In this pursuit, we study uniform price auctions in a repeated setting from the perspective of a value-maximizing buyer who aims to maximize their acquired cumulative value across T rounds, subject to per-round return-on-investment (RoI) constraints. For a RoI-constrained, value-maximizing buyer, we study a generalized version of the uniform bidding format, commonly used in practice, which we term as m-uniform bidding. To characterize the optimal m-uniform bid, we introduce and study the notion of universally feasible (UF) bidding policies, which are robust, meaning that RoI feasibility is obtained regardless of the competitors' bids. We show that the optimal class of UF bidding policies is essentially a generalization of truthful bidding policies, which depends only on the valuation curve of the bidder and target RoI. To measure the performance of UF bidding policies against the optimal bidding policy that is not necessarily UF, we introduce a metric called the Price of Universal Feasibility (PoUF) and establish that PoUF is at most 2, irrespective of m and the upper bound is tight. We further compare the generalized m-uniform bidding interface against the classical uniform bidding format under which m=1, showing the total value under m-uniform bidding increases at most by a factor of m. Numerical simulations on semi-synthetic data demonstrate that UF bidding policies perform significantly better than the derived theoretical bounds.

Joint work with Sourav Sahoo.

Link to paper: arxiv.org/abs/2406.03674

15:00-15:30 Coffee Break

15:30-16:15 Aranyak Mehta (Google)

AI/ML + Econ/Algos: Topics at the Intersection

We will overview a few recent research directions at the intersection of Machine Learning and Algorithms/Economics.

(1.) Can Machine Learning learn Algorithms? In [1, 2], we ask whether it is possible to train networks to discover "TCS-style" algorithms, those whose performance is measured in the worst-case. Can we train them tabula-rasa, and if so, how do the learned algorithms compare with known "human generated" algorithms? We investigate this in the context of a motivating algorithms problem -- the "Adwords" online allocation problem.

(2.) Auctions with LLM Summaries. In [3], we consider the question of how to run ad auctions when an LLM summarizes multiple ad assets into a commercial summary. We provide a feasible and generalizable scheme in which advertiser bids are inputs into the LLM based (RAG) allocation, with good auction incentives.

(3.) Low-regret dynamics in auction bidding. In [4] we study the equilibria among bidders playing low-regret bidding strategies in the context of simple second- or first-price auctions, and compare them to equilibria predicted by rational behavior in economic theory.

Talk based on:

[1]: A new dog learns old tricks: RL finds classic optimization algorithms. Weiwei Kong, Christopher Liaw, Aranyak Mehta, D. Sivakumar (ICLR 2019)

https://openreview.net/pdf?id=rkluJ2R9KQ

[2]: Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training. (ICLR multiagent workshop 2022) Goran Zuzic, Di Wang, Aranyak Mehta, D. Sivakumar.

https://arxiv.org/abs/2010.08418

[3]: Auctions with LLM Summaries (KDD'24, to appear) Kumar A. Dubey, Zhe Feng, Rahul Kidambi, Aranyak Mehta, Di Wang

https://arxiv.org/abs/2404.08126

[4]: Convergence Analysis of No-Regret Bidding Algorithms in Repeated Auctions. (AAAI 2021) Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mehta, Abhishek Sethi. https://arxiv.org/abs/2009.06136

16:15-17:00 Shuchi Chawla (U Texas at Austin)

Revisiting revenue maximization for many buyers: buy-many mechanisms and sequential posted pricing

We study multi-buyer multi-item revenue maximization with the goal of approximating the optimal revenue via a simple mechanism such as a sequential item pricing. We assume that buyers' values are subadditive but make no assumptions on the value distributions. While the optimal revenue is inapproximable by any simple mechanism in this context, a recent line of work considers a simpler benchmark, namely the optimal revenue over "buy many" mechanisms. Buy many mechanisms essentially correspond to subadditive pricings and are the only revenue benchmark known to be approximable for general value distributions. Our work addresses a main open question from this literature -- approximating buy-many mechanisms for multiple buyers. We show that a sequential item pricing mechanism achieves an $O(\log m)$ approximation to the revenue of any buy-many mechanism when all buyers have gross substitute values over $m$ items, and an $O(\log^2 m)$ approximation when buyers have subadditive values.

Our approximations are achieved through the construction of a new multi-dimensional Online Contention Resolution Scheme (OCRS), that provides an online rounding of the optimal ex ante solution. Prior to our work, OCRSes have only been studied in the context of social welfare maximization for single-parameter buyers. For the welfare objective, constant-factor approximations have been demonstrated for a wide range of combinatorial constraints on item allocations and classes of buyer valuation functions. Our work opens up the possibility of a similar success story for revenue maximization.

Talk based on:

https://arxiv.org/abs/2204.01962

https://arxiv.org/abs/2404.14679

Call for Posters

Update: The submission deadline has passed. See list of accepted posters below.

Call for Posters: The 2024 INFORMS Workshop on Market Design (EC 2024, Yale)

The 2024 INFORMS Workshop on Market Design will be held on July 8th, 2024 in conjunction with the EC 2024 conference at Yale U, New Haven. The workshop is sponsored by the INFORMS Section on Auctions and Market Design.

In addition to invited talks the workshop will feature a one hour poster session on recent work broadly related to market design, including applied, theoretical and empirical work. To submit a poster for consideration, please send an abstract of no more than 300 words via email to informs-market-design-workshop@googlegroups.com

Submission deadline: 11:59 pm PT on Monday, June 24.
Accept/reject notifications: Wednesday, June 26.

For each author, please indicate if they are a PhD student or postdoc, and if they are on the academic job market. Job market candidates are especially encouraged to submit their work.

Accepted Posters

Jerry Anunrojwong, Columbia. Battery Operations in Electricity Markets: Strategic Behavior and Distortions. [link]
Giannis Fikioris, Cornell. Online Resource Sharing via Dynamic Max-Min Fairness: Efficiency, Robustness and Non-Stationarity. [arXiv]
Rigel Galgana, MIT. Learning in Repeated Multi-Unit Pay-As-Bid Auctions. [arXiv]
Anand Kalvit, Stanford. Incentivized Exploration via Filtered Posterior Sampling. [arXiv]
Soonbong Lee, Yale. Dynamic Matching with Post-allocation Service and its Application to Refugee Resettlement. [SSRN]
Andreas Maggiori, Columbia. Fair Secretaries with Unfair Predictions. [link]
Aniket Murhekar, University of Illinois Urbana-Champaign. Fair Division of Indivisible Chores via Earning Restricted Equilibria [arXiv]
Matias Romero, Columbia. Potential-Based Greedy Matching for Dynamic Pooling of Delivery Orders. [link]
Brian Zhang, Carnegie Mellon. Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games. [arXiv]