Market Design Seminar

We are running a regular seminar in Market Design, around the topics of our project.

2023

When: August 16, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Boris Epstein, GSB, Columbia University

Title: Selection and Ordering Policies for Hiring Pipelines via Linear Programming

Abstract: Motivated by hiring pipelines, we study three selection and ordering problems in which applicants for a finite set of positions must be interviewed or made offers to. There is a finite time budget for interviewing or making offers, and a stochastic realization after each decision, leading to computationally-challenging problems. In the first problem, we study sequential interviewing and show that a computationally-tractable, non-adaptive policy that must make offers immediately after interviewing is near-optimal, assuming offerees always accept their offers. In the second problem, we assume that applicants have already been interviewed but only accept offers with some probability; we develop a computationally-tractable policy that makes offers for the different positions in parallel, which can be used even if positions are heterogeneous and is approximately optimal relative to a policy that can make the same amount of offers not in parallel. In the third problem, we introduce a model where the hiring firm is tightly time constrained and must send all offers simultaneously in a single time step, with the possibility of hiring over capacity at a cost; we provide nearly-tight bounds for the performance of practically motivated value-ordered policies. All in all, our paper takes a unified approach to three different hiring problems, based on linear programming.  Our results in the first two problems generalize and improve the existing guarantees in the literature that were between 1/8 and 1/2 to new guarantees that are at least 1-1/e ≈ 63.2%.

When: June 22, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Paul Gölz, Harvard University

Title: In this apportionment lottery, the House always wins

Abstract: Apportionment is the problem of distributing h indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggested to apportion seats in a randomized way such that each state receives exactly their proportional share qᵢ of seats in expectation (ex ante proportionality) and receives either ⌊qᵢ⌋ or ⌈qᵢ⌉ many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity — a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

When: June 14, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Sebastián Perez-Salazar, Rice University

Title: The IID Prophet Inequality with Limited Flexibility 

Abstract: In online sales, sellers usually offer each potential buyer a posted price in a take-it-or-leave fashion. Buyers can sometimes see posted prices faced by other buyers, and changing the price frequently could be considered unfair. The literature on posted price mechanisms and prophet inequality problems has studied the two extremes of pricing policies, the fixed price policy and fully dynamic pricing. The former is suboptimal in revenue but is perceived as fairer than the latter. This work examines the middle situation, where there are at most 𝑘 distinct prices over the selling horizon. Using the framework of prophet inequalities with independent and identically distributed random variables, we propose a new prophet inequality for strategies that use at most 𝑘 thresholds. We present asymptotic results in 𝑘 and results for small values of 𝑘. For 𝑘 = 2 prices, we show an improvement of at least 11% over the best fixed-price solution. Moreover, 𝑘 = 5 prices suffice to guarantee almost 99% of the approximation factor obtained by a fully dynamic policy that uses an arbitrary number of prices. From a technical standpoint, we use an infinite-dimensional linear program in our analysis; this formulation could be of independent interest to other online selection problems.

When: May 24, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Andrés Cristi, CMM, U Chile

Title: A Constant Factor Prophet Inequality for Online Combinatorial Auctions

Abstract: In online combinatorial auctions m indivisible items are to be allocated to n agents who arrive online. Agents have random valuations for the different subsets of items and the goal is to allocate the items on the fly so as to maximize the total value of the assignment. A prophet inequality in this setting refers to the existence of an online algorithm guaranteed to obtain, in expectation, a certain fraction of the expected value obtained by an optimal solution in hindsight. The study of prophet inequalities for online combinatorial auctions has been an intensive area of research in recent years, and constant factor prophet inequalities are known when the agents' valuation functions are submodular or fractionally subadditive. Despite many efforts, for the more general case of subadditive valuations, the best-known prophet inequality has an approximation guarantee of O(log log m).

We prove the existence of a constant factor prophet inequality for the subadditive case, resolving a central open problem in the area.

Our prophet inequality is achieved by a novel, but elementary, sampling idea which we call the Mirror Lemma. This lemma is essentially concerned with understanding algorithms for which the set of items that are allocated and those that are not, distribute equally. The other main ingredient is a nonstandard application of Kakutani's fixed point theorem.

When: May 10, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Tjark Vredeveld, Maastricht University

Title: Learning in scheduling: simple policies for Bayesian scheduling

Abstract: We consider the problem of scheduling jobs on a single machine, non-preemptively. The goal is to minimize the total completion time of the jobs. It is well known that this problem is solved by scheduling the jobs in order of shortest processing times (SPT) when the jobs’ processing times are known or shortest expected processing times (SEPT), when we have full knowledge on the true expected values.

In this talk, we consider the stochastic scheduling problem in which we have additional uncertainty about the parameters of the distribution of the jobs’ processing times. We assume that jobs appear in $m$ classes and the processing times of jobs in one class are independently and identically distributed. By processing a job from one class one can learn about the true parameters of the distribution. The initial beliefs on these parameters are modelled as a prior distribution and after processing a job the posterior distribution models the updated beliefs on the parameter. When the processing times are exponentially distributed with an unknown parameter that is gamma distributed, optimal policies based on Gittins-indices exist (see, e.g., Hamada and Glazebrook, 1993). However, computing these indices may be computationally challenging. In this talk, we consider two simple policies, based on SEPT. The first policy processes the jobs based on the initial beliefs of the expected processing time. This implies that all jobs of one class are processed consecutively. The second policy, always processes a job from a class with shortest expected processing time according to the updated beliefs. We can show that both policies have a (worst-case) approximation ratio of $m$, the number of classes, and that this ratio is tight.

This talk is based on (updated beliefs of) joint work with Sebastian Marban and Cyriel Rutten.

When: April 19, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Evangelia Gergatsouli, University of Wisconsin - Madison

Title: Opening Pandora's Box: the Correlated Case

Abstract: Pandora's Box models optimization problems where the input consists of stochastic random variables, but the uncertainty can be removed (i.e. reveal the exact value of a variable) by paying an extra price. Our goal is to maximize (or minimize) the price of the variable chosen minus (resp. plus) the cost we paid to learn the exact instantiations of the variables. All previous work on this class of problems assumes that different random variables in the input are distributed independently. Until recently, nothing was known for the case of correlated input.

In this talk, I will introduce Pandora's Box problem and describe the first constant approximation algorithm for Pandora's Box with correlated distributions. I will also briefly mention a newer, simpler algorithm that directly generalizes the independent case algorithm while also improving on the approximation factor.

This is based on joint work with Shuchi Chawla, Yifeng Teng, Christos Tzamos and Ruimin Zhang.

When: January 25, 15:00 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Paul Duetting, Google Research

Title: Combinatorial Contracts

Abstract: An emerging frontier in Algorithmic Game Theory is Algorithmic Contract Theory, which studies the classic hidden-action principal-agent problem of contract theory through the computational lens. In this talk, I will present three basic ways in which the problem can be combinatorial and survey both hardness and poly-time (approximation) results. The analysis will uncover some surprising connections (but also fundamental differences) to combinatorial auctions.

2022

When: December 15, 14:30 hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Gabriel Weintraub, Stanford Graduate School of Business

Title: Experimentation in Two-Sided Marketplaces: The Impact of Interference

Abstract: Marketplace platforms use experiments (also known as “A/B tests”) as a method for making data-driven decisions about which changes to make on the platform. When platforms consider introducing a new feature, they often first run an experiment to test the feature on a subset of users and then use this data to decide whether to launch the feature platform-wide. However, it is well documented that estimates of the treatment effect arising from these experiments may be biased due to the presence of interference driven by the substitution effects on the demand and supply sides of the market.  

In this work, we develop an analytical framework to study experimental design in two-sided marketplaces. We develop a stochastic market model and associated mean field limit to capture dynamics in such experiments. Notably, we use our model to show how the bias of commonly used experimental designs and associated estimators depend on market balance. We also propose novel experimental designs that reduce bias for a wide range of market balance regimes. We also discuss a simpler model to study the bias-variance trade-off among different experimental choices. Finally, we present results on calibrated models and live implementations on two real-world platforms. Overall, our  work shows the potential of structural modeling to yield insight on experimental design for practitioners.

Based on joint work with Ramesh Johari, Hannah Li, Inessa Liskovich, and Geng Zhao.

When: December 14, 15:00hrs.

Where: Sala de Seminario von Neuman, CMM, Beauchef 851, torre norte.  

Speaker: Nick Arnosti, U Minnesota.

Title: Explainable Affirmative Action.

Abstract: When organizations select from a set of applicants, they often use a priority ranking in tandem with policies designed to ensure diversity or boost the chances of applicants from certain groups. These policies add significant complexity to the selection process, and examples from around the world show that they often do not have the intended effect, or are accompanied by unintended consequences.

Motivated by a desire to make these rules more transparent, we provide three axioms intended to capture explainability: monotonicity, lower invariance, and non-bossiness. We show that these axioms characterize a family of "outcome-based" selection rules. This family of selection rules is rich enough to incorporate many (but not all) existing reserve and quota policies. We illustrate our findings using examples from the allocation of affordable housing in New York City.

When:  November 23, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Impartial Selection with Additive Guarantees via Iterated Deletion" 

Speaker:  Javier Cembrano (TU Berlin)

Abstract: Impartial selection is the selection of an individual from a group based on nominations by other members of the group, in such a way that individuals cannot influence their own chance of selection. We give a deterministic mechanism with an additive performance guarantee of $O(n^{(1+\gamma)/2})$ in a setting with $n$ individuals where each individual casts $O(n^{\gamma})$ nominations, where $\gamma \in [0,1]$. For $\gamma=0$, i.e., when each individual casts at most a constant number of nominations, this bound is $O(\sqrt{n})$. This matches the best-known guarantee for randomized mechanisms and a single nomination. For $\gamma=1$ the bound is $O(n)$. This is trivial, as even a mechanism that never selects provides an additive guarantee of $n-1$. We show, however, that it is also best possible: for every deterministic impartial mechanism there exists a situation in which some individual is nominated by every other individual and the mechanism either does not select or selects an individual not nominated by anyone. This is joint work with Felix Fischer, David Hannon, and Max Klimm.

When:  October 19, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Rawlsian Assignments" 

Speaker:  Juan Pereyra (U República)

Abstract: We study the assignment of indivisible objects to individuals when transfers are not allowed. Previous literature has mainly focused on efficiency (from ex-ante and ex-post perspectives), and individually fair assignments. Consequently, egalitarian concerns have been overlooked. We are inspired by the assignment of apartments in housing cooperatives where families regard the egalitarianism of the assignments as a first-order requirement. In particular, they want to avoid assignments where some families get their most preferred apartment, while others get options ranked very low in their preferences. Based on Rawls' idea of fairness, we introduce the notion of Rawlsian assignments. We prove that there always exists a unique Rawlsian assignment, which is sd-efficient, and satisfies equal treatment of equals. We illustrate our analysis with preference data from housing cooperatives. Our results show that the Rawlsian assignment substantially improves, from an egalitarian perspective, both the probabilistic serial mechanism, and the mechanism currently in use.

When:  September 21, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Bayesian Persuasion With Costly Information Acquisition" 

Speaker:  Alfonso Montes (UChile)

Abstract: We consider a Bayesian persuasion model in which the receiver can gather independent information about the state at a uniformly posterior-separable cost. We show that the sender provides information that prevents the receiver from gathering independent information in equilibrium. When the receiver faces a lower cost of information, her `threat' of gathering independent information increases, thus decreasing the sender's power to persuade. A lower cost of information can also hurt the receiver because the sender may provide strictly less information in equilibrium. Finally, we propose a solution method that can be used to solve our model in specific applications. Joint work with Ludmila Matyskova.

When:  September 7, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "The kidney exchange problem: length-constrained cycles and chains optimization on compatibility graphs" 

Speaker:  Felipe Subiabre (UChile)

Abstract: The kidney exchange problem is a combinatorial optimization problem that arises naturally when implementing centralized kidney exchange programs. Given a directed weighted graph (called the compatibility graph), we aim to find a collection of simple and vertex-disjoint cycles maximizing the total weight of their participating arcs. Because of logistical considerations, a bound k is placed on the length of each possible cycle. We will briefly explain how the problem is polynomially solvable in the cases k = 2 and unbounded k, and why it turns NP-complete for k >= 3. MIP formulations are used in practice because of their efficiency and flexibility to accommodate extra constraints of the exchange programs. We will introduce the cycles MIP formulation of Roth et al. and explain why its linear relaxation is polynomially solvable. Inspired by this result, we present a conjecture on the integrality gap of this formulation, which is part of our ongoing work. Time permitting, we will also discuss the addition of exchange chains starting from a distinguished subset of vertices (representing deceased or altruistic donors) and explain how their introduction makes even the associated linear relaxation problem NP-hard.

When:  August 24, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Solidarity Cover Problem" 

Speaker:  Laura Vargas-Koch (UChile)

Abstract: This work started with a real-world problem where the task was to partition a set of locations into disjoint subsets such that each subset is spread in a way that it covers the whole set with a certain radius. This made us formalizing the following problem which we call Solidarty Cover Problem. Given a finite set S, a metric d, and a radius r, and a number of partitions m. We define a subset C of S to be an r-cover if B(C,r)=S. The Solidarity Cover Problem is the problem of determining whether there exist m disjoint r-covers. We consider the optimization problems of maximizing the number of r-covers which is essentially the domatic number problem, and the optimization problem of minimizing the radius. This is joint work with Britta Peis and Eran Rosenbluth.

When:  August 17, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Prophet Inequalities via the Expected Competitive Ratio" 

Speaker:  Alexandros Tsigonias-Dimitriadis (UChile)

Abstract: We consider prophet inequalities under general downward-closed constraints. In a prophet inequality problem, a decision-maker sees a series of online elements and needs to decide immediately and irrevocably whether or not to select each element upon its arrival, subject to an underlying feasibility constraint. Traditionally, the decision-maker’s expected performance has been compared to the expected performance of the prophet, i.e., the expected offline optimum. We refer to this measure as the Ratio of Expectations (or, in short, RoE). However, a major limitation of the RoE measure is that it only gives a guarantee against what the optimum would be on average, while, in theory, algorithms still might perform poorly compared to the realized ex-post optimal value. Hence, we study alternative performance measures. In particular, we suggest the Expected Ratio (or, in short, EoR), which is the expectation of the ratio between the value of the algorithm and the value of the prophet. This measure yields desirable guarantees, e.g., a constant EoR implies achieving a constant fraction of the ex-post offline optimum with constant probability. Moreover, in the single-choice setting, we show that the EoR is equivalent (in the worst case) to the probability of selecting the maximum, a well-studied measure in the literature. This is no longer the case for combinatorial constraints (beyond single-choice), which is the main focus of this paper. Our main goal is to understand the relation between RoE and EoR in combinatorial settings. Specifically, we establish a two-way black-box reduction: for every feasibility constraint, the RoE and the EoR are at most a constant factor apart. This implies a wealth of EoR results in multiple settings where RoE results are known.

When:  May 11, 15 hrs

Where: Center for Mathematical Modeling, Universidad de Chile, Sala Von Neumann

Title:  "Efficiency and fairness in random resource allocation and social choice" 

Speaker:  Federico Echeñique (Caltech)

Abstract: We study efficiency in general collective choice problems when agents have ordinal preferences, and randomization is allowed.  We establish the equivalence between welfare maximization and ex-ante efficiency for general domains, and relate ex-ante efficiency with ex-post efficiency, characterizing when the two notions coincide. We also propose a new general notion of fairness that is applicable in any social choice environment, not only in resource allocation. Our results have implications for well-studied mechanisms including random serial dictatorship and a number of specific environments, including the dichotomous, single-peaked, and social choice domains. Joint with Joe Root and Fedor Sandomirskiy.

When:  March 9

Where:  Facultad de Economía y Negocios, U. de Chile, sala  P-305, Diagonal Paraguay 257, Santiago.

14h30: “On bargaining sets for exchange economies”

Speaker: Emma Moreno García, Universidad de Salamanca

Abstract: We focus on the study of bargaining sets for exchange economies.  This two-step conception of the blocking process attempts to inject a sense of stability and credibility into the veto mechanism. We analyze the behavior of such a cooperative solution when there are restrictions on the formation of coalitions. Moreover, we introduce a notion of bargaining set for finite economies and show its convergence to the set of Walrasian allocations.  Finally, we address the case where the presence of a leader is required in the objection system.

15h30: "Coalitional stability in matching problems with externalities and random preferences"

Speaker: Adriana Piazza, Universidad de Chile

Abstract: The aim of this work is to analyze the probability of existence of coalitionally stable outcomes in matching problems with externalities. We propose a general model that includes marriage markets, roommate problems, and Shapley-Scarf housing markets as particular cases. When preferences are randomly determined, the probability of having a coalitionally stable solution is positively affected by three factors: the prudence of coalitions when evaluating a deviation, the social connectedness of those that can react to it, and the incidence of externalities in preferences. At the same time, this probability is negatively affected by the number of agreements that agents can implement to block a matching. In this context, if agents  have a limited  capacity  to organize themselves into large  coalitions, then coalitional stability holds asymptotically even when individuals become less and less prudent as the population grows.