[theory students] Fwd: CS+Econ Quarterly Workshop: Mechanism Design with Non-linear Utility

[Shuchi Chawla <shuchi@xxxxxxxxxxx>]

FYI. I'm driving to Evanston on early Friday morning to be at these workshops, and happy to give a ride to 2-3 others if you are interested. (I can't give a ride on the way back, but you can take the bus.)

Shuchi

---------- Forwarded message ---------
From: Jason Hartline <hartline@xxxxxxxxxxxxxxxxxxxxx>
Date: Tue, May 21, 2019 at 11:44 AM
Subject: CS+Econ Quarterly Workshop: Mechanism Design with Non-linear Utility
To: Shuchi Chawla <shuchi@xxxxxxxxxxx>

Hi Shuchi,

Reminder for your colleagues: ÂThe spring CS+Econ Quarterly workshop is this week on Friday. We have a double-header as the Quarterly Theory Workshop happens to be Friday afternoon and Saturday. Â(Details for the QTW are here:Âhttps://theory.cs.northwestern.edu/events/embeddings/)

Best,

Jason

==================================================

Northwestern CS+Econ Quarterly Workshop
Mechanism Design with Non-linear Utility
Kellogg Global Hub 5101, Northwestern U, 2211 Campus Dr, Evanston, IL 60208.
9:00am-12:35pm, Friday, May 24, 2019
https://sites.northwestern.edu/csecon/events/mechanism-design-with-non-linear-utility/

==================================================


About the Series

The Quarterly CS+Econ Workshop brings in three or four experts at the interface between computer science and economics to present their perspective and research on a common theme. Chicago area researchers with interest in economics and computer science are invited to attend. The technical program is in the morning and includes coffee and lunch. The afternoon of the workshop will allow for continued discussion between attendees and the speakers.Â

The the workshop series is organized by Ronen Gradwohl (Kellogg, MEDS), Jason Hartline (Computer Science), and Marciano Siniscalchi (Economics). Funding for the series is provided by the Shaw Family Supporting Organization CS+X Fund.


Synopsis

The second edition of this workshop will be on the theme of Mechanism Design for Non-linear Utility. Much of the literature on mechanism design focuses on settings where agents have quasi-linear utilities where there are elegant closed-form characterizations of optimal mechanisms. In more general settings where agents have non-linear utility, crisp closed-form characterizations are few and far between. This workshop aims showcases recent progress in this challenging domain. The speakers are Brian Baisa, Shuchi Chawla, Kamesh Munagala, and Sergei Severinov.



Logistics

â Date: Friday, May 24, 2019.
â Location: Kellogg Global Hub 5101 (map), Northwestern U, Evanston, IL 60208.
â Transit: Noyes St. Purple Line (map).
â Parking: Validation for North Campus Parking Garage (map) available at workshop.
â Registration: None required. Please bring your own name badge from past conference.


Schedule

â 8:30-9:00: Continental Breakfast
â 9:00-9:05: Opening Remarks
â 9:05-9:45: Sergei Severinov (UBC):
Optimal and Efficient Mechanisms with Asymmetrically Budget Constrained Buyers
â 9:45-9:50: Sergei Severinov Q/A
â 9:50-10:30: Kamesh Munagala (Duke U):
A Simple Mechanism for a Budget-Constrained Buyer
â 10:30-10:35: Kamesh Munagala Q/A
â 10:35-11:05: Coffee Break
â 11:05-11:45: Brian Baisa (Amherst):
Efficient Multi-Unit Auctions for Normal Goods
â 11:45-11:50: Brian Baisa Q/A
â 11:50-12:30: Shuchi Chawla (UW-Madison):
Revenue maximization with an uncertainty-averse buyer
â 12:30-12:35: Shuchi Chawla Q/A
â 12:35-1:30: Lunch


Titles and Abstracts

Speaker: Sergei Severinov
Title: Optimal and Efficient Mechanisms with Asymmetrically Budget Constrained Buyers
Abstract: The paper characterizes both the optimal (revenue-maximizing) and constrained-efficient (surplus maximizing) mechanisms for allocating a good to buyers who face asymmetric budget constraints. Both the optimal and efficient mechanisms belong to one of two classes. When the budget differences between the buyers are small, the mechanism discriminates only between high-valuation types for whom the budget constraint is binding. All low valuations buyers are treated symmetrically despite budget differences. When budget differences are sufficiently large, the mechanism discriminates in favor of buyers with small budgets when the valuations are low, and in favor of buyers with larger budgets when the valuations are high

Joint work with Alexei Boulatov.

Speaker: Kamesh Munagala
Title: A Simple Mechanism for a Budget-Constrained Buyer
Abstract: We study a classic Bayesian mechanism design setting for an additive buyer in the presence of budgets. In this setting a monopolist seller with m heterogeneous items faces a single buyer and seeks to maximize her revenue. The buyer has a budget and additive valuations drawn independently for each item from (non-identical) distributions. We show that when the buyerâs budget is publicly known, the better of selling each item separately and selling the grand bundle extracts a constant fraction of the optimal revenue. When the budget is private, we consider a standard Bayesian setting where buyerâs budget b is drawn from a known distribution B. We show that if b is independent of the valuations and distribution B satisfies the monotone hazard rate condition, then selling items separately or in a grand bundle is still approximately optimal. We give a complementary example showing that no constant approximation simple mechanism is possible if budget b can be interdependent with valuations.

Joint work with Yu Cheng, Nick Gravin, and Kangning Wang.

Speaker: Brian Baisa
Title: Efficient Multi-Unit Auctions for Normal Goods
Abstract: I study multi-unit auction design when bidders have private values, multi-unit demands, and non-quasilinear preferences. I give conditions under which we can design a mechanism that retains the Vickrey auctionâs desirable incentive and efficiency properties: (1) individual rationality, (2) dominant strategy incentive compatibility, and (3) Pareto efficiency. Without quasilinearity, the Vickrey auction loses its desired incentive and efficiency properties. Instead of assuming that bidders have quasilinear preferences, I assume that bidders have positive wealth effects. My model nests cases where bidders are risk averse, face financial constraints, or have budgets.

With two bidders, I show that there is a mechanism that retains the desired properties of the Vickrey auction if bidders have single-dimensional types. I present an impossibility theorem that shows that there is no mechanism that satisfies Vickreyâs desired properties and weak budget balance when bidders have multi-dimensional types. I also present a second impossibility theorem for the case where there are three or more bidders, even if bidders have single-dimensional types.

Speaker: Shuchi Chawla
Title: Revenue maximization with an uncertainty-averse buyer
Abstract: Most work in mechanism design assumes that buyers are risk neutral; some considers risk aversion arising due to a non-linear utility for money. Yet behavioral studies have established that real agents exhibit risk attitudes which cannot be captured by any expected utility model. We initiate the study of revenue-optimal mechanisms under buyer behavioral models beyond expected utility theory. We adopt a model from prospect theory which arose to explain these discrepancies and incorporates agents under-weighting uncertain outcomes. In our model, an event occurring with probability x<1 is worth strictly less to the agent than x times the value of the event when it occurs with certainty. In contrast to the risk-neutral setting, the optimal mechanism may be randomized and appears challenging to find, even for a single buyer and a single item for sale. Nevertheless, we give a characterization of the optimal mechanism which enables positive approximation results. In particular, we show that under a reasonable bounded-risk-aversion assumption, posted pricing obtains a constant approximation.

Joint work with Kira Goldner, Benjamin Miller, and Emmanouil Pountourakis.