The growing success of predictive machine learning has made it appealing as a tool for informing decisions about humans. But humans are not your conventional input: they have goals, beliefs, and aspirations, and may act strategically to promote their own interests. Given that traditional learning methods are not designed to handle inputs that "behave", it is natural to ask: how should we design learning systems when we know they will be used in social settings with users that behave?

The goal of this talk is to initiate discussion regarding the part game theory can play in answering this question. As a starting point, I will present the problem of strategic classification, in which users can modify their features (at a cost) in response to a learned classifier in order to obtain favorable predictions. I will then describe some of our work in this field, demonstrating how various forms of strategic behavior -- even mild  --can dramatically transform the learning problem. Finally, I will argue for the need to inject more elaborate forms of economic modeling into learning -- and for game theory as a useful means for this.

A prevalent assumption in auction theory is that the auctioneer has full control over the market and that the allocation she dictates is final. In practice, however, agents might be able to resell acquired items in an aftermarket. A prominent example is the market for carbon emission allowances. These allowances are commonly allocated by the government using uniform-price auctions, and firms can typically trade these allowances among themselves in an aftermarket that may not be fully under the auctioneer's control. While the uniform-price auction is approximately efficient in isolation, we show that speculation and resale in aftermarkets might result in a significant welfare loss. Motivated by this issue, we consider three approaches, each ensuring high equilibrium welfare in the combined market. The first approach is to adopt smooth auctions such as discriminatory auctions. This approach is robust to correlated valuations and to participants acquiring information about others' types. However, discriminatory auctions have several downsides, notably that of charging bidders different prices for identical items, resulting in fairness concerns that make the format unpopular. Two other approaches we suggest are either using posted-pricing mechanisms, or using uniform-price auctions with anonymous reserves. We show that when using balanced prices, both these approaches ensure high equilibrium welfare in the combined market. The latter also inherits many of the benefits from uniform-price auctions such as price discovery, and can be introduced with a minor modification to auctions currently in use to sell carbon emission allowances.

Joint with Nicole Immorlica, Yingkai Li and Brendan Lucier.

Paper: https://arxiv.org/abs/2107.05853

When allocating indivisible goods to a number of selfish agents, both fairness and truthfulness are main concerns: the allocation should guarantee everyone a sense of fair treatment, while also incentivizing people to report their true, private preferences. Both are challenging goals, and together, there are strong results showing that achieving them is usually impossible.

Following previous work for agents with additive valuation functions, we demonstrate how to use variants of a very simple round-robin routine to get close to the above, impossible ideal: surprisingly, we show the existence of (approximate) equilibria for agents with complex, (up to) submodular valuation functions that exhibit fairness guarantees with respect to the true valuations of agents, although they might misreport those to the mechanism. 

The study of noise and the notions of noise sensitivity and stability, play a role in the study of voting games, and are related to Condorcet's paradox, Arrow's theorem, Condorcet's Jury theorem, power-measures, manipulations, and various forms of indeterminacy.  I will briefly mention some old and new results and pose the challenge of extending the study of noise stability and sensitivity to other notions of cooperative and non-cooperative games and to the study of markets. 

The interdependent value (IDV) model, introduced by Milgrom and Weber, has been pivotal in studying auctions with more realistic representation of agent valuations, where each bidder i has a private signal s_i for the item, and a public valuation function v_i(s_1,\ldots, s_n) which maps all bidders' private signals into a valuation function. Our work considers the more challenging setting where the valuation functions are private as well. We provide a new truthful mechanism that achieves O(1)-approximation to the optimal social welfare when the valuations are submodular-over-signals (SoS). Prior to our work, the best known approximation ratio was O(\log^2 n) by Eden, Goldner, Zheng for monotone SoS valuations. Moreover, we extend our results to obtain a constant factor approximation for the multi-unit auctions settings with unit-demand buyers.

I will also briefly discuss our work on interdependent public projects [SODA'23]. We show that no universally truthful mechanism guarantees better welfare than allocating a random project (in the public IDV model with SoS valuations); in strong contrast to the constant approximation in the combinatorial auctions setting. 

This talk is based on joint works with Avi Cohen, Alon Eden, Kira Goldner, Michal Feldman, Simon Mauras, Inbal Talgam-Cohen.