Workshop

What can we understand about probability spaces on "nice" partitions of a geometric region?  Can we design efficient samplers? Can we at least detect extreme outliers?  These questions have become particularly salient in the past several years as the techniques developed by mathematicians are now applied to conduct statistical analyses of things like U.S. political districtings.  We will discuss some recent developments on probability spaces defined by geometric constraints, including positive and negative results on the mixing times of relevant Markov chains, Markov chain methods which eschew mixing-time requirements, and direct sampling methods.

Machine learning models often include group attributes like sex, age, and HIV status for the sake of personalization – i.e., to assign more accurate predictions to heterogeneous subpopulations. In this talk, I will describe how such practices inadvertently lead to worsenalization, by assigning unnecessarily inaccurate predictions to minority groups. I will discuss how these effects violate our basic expectations from personalization and describe how these violations arise due to standard practices in model development. I will end by highlighting recent work on how to address these issues in practice – first, by setting "personalization budgets" to test for worsenalization; second, by developing models where individuals can consent to personalization at prediction time.

In many applied matching problems, indivisible goods that are in unit demand have to be assigned without monetary transfers. One of the most prominent such problems is modeled by classical Shapley-Scarf housing markets (Shapley and Scarf, 1974). Shapley and Scarf (1974) consider an exchange economy in which each agent owns an indivisible object (say, a house); each agent has preferences over houses and wishes to consume exactly one house. The objective of the market designer then is to reallocate houses among agents. When preferences are strict, Shapley and Scarf (1974) show that the strict core (defined by a weak blocking notion) has remarkable features: it is non-empty, and can be easily calculated by the so-called top-trading-cycles (TTC) algorithm (due to David Gale). Moreover, the TTC mechanism that assigns the unique strict core allocation satisfies important incentive properties, strategy-proofness (Roth, 1982) as well as the stronger property of group strategy-proofness (Bird, 1984). Furthermore, Ma (1994) and Svensson (1999) show that the TTC mechanism is the unique mechanism satisfying Pareto efficiency, individual rationality, and strategy-proofness.

After giving a short survey over the wonderful properties the top-trading cycles mechanism has, I’ll consider an extension of Shapley-Scarf housing markets to object allocation problems with coalitional endowments (housing markets with existing tenants are an example). For this relatively new class of problems, I present recent results obtained together with Di Feng during our current stay at the Simons Laufer Mathematical Sciences Institute (formerly MSRI). Our main result is the characterization of sequential priorities-augmented top trading cycles mechanisms.

In a carbon auction, licenses for CO2 emissions are allocated among multiple interested players. Inspired by this setting, we consider repeated multi-unit auctions with uniform pricing, which are widely used in practice. Our contribution is to analyze the bidding strategies and properties of these auctions in both the offline and online settings. We also analyze the quality of the equilibria through the lens of the core solution concept. Based on joint work with Mahsa Derakhshan, Negin Golrezaei, and Yanjun Han.

Fair division is the problem of dividing a set of items among $n$ agents in a fair manner. When the items are indivisible, the classical fairness solution concepts of {\em envy-freeness} and {\em proportionality} are rendered inapplicable. In this talk, I will survey recent advances on some of the strongest relaxations of these two concepts, namely EFX and MMS/APS, and their connections to other areas of theory CS, such as extremal combinatorics, probabilistic methods, and the Santa Clause problem.

The Schelling model of segregation was introduced in economics to show how micromotives can drive macrobehavior. Agents on a lattice have two colors and try to move to a different location if the number of their neighbors with a different color exceeds some threshold. Simulations reveal that even such mild local color preferences, or homophily, are sufficient to cause segregation. We propose a stochastic generalization of the Schelling model, based on both race and wealth, to understand how carefully architected placement of incentives, such as urban infrastructure, might enhance or mitigate segregation over time.