Noticias en español
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,...
Read MoreWeak Ergodicity Approach to POMDPs.
Abstract: This seminar introduces Partially Observable Markov Decision Processes (POMDPs), emphasizing their relationship with decision problems and decidability. We then explore a novel theoretical class of POMDPs based on a weak ergodicity property. The seminar concludes by identifying necessary conditions for POMDPs to exhibit this characteristic, bridging the gap between this theoretical result and its potential practical implementation.
Read MoreEnergy-Efficient Distributed Algorithms for Synchronous Networks.
Abstract: We study the design of energy-efficient algorithms for well known distributed models of computation: the LOCAL and CONGEST models. Specifically, as a measure of complexity, we consider the maximum, taken over all the edges, or over all the nodes, of the number of rounds at which an edge, or a node, is activein the algorithm. We first show that every Turing-computable problem has a CONGEST algorithm with constant node-activation complexity, and therefore constant edge-activation complexity as well. That is, every node (resp., edge) is active in sending (resp., transmitting) messages...
Read MoreIn 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...
Read MoreThe 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...
Read MoreMulti-weighted (sample)-prophet and secretary matching problems.
Abstract: A k-graph is a hypergraph whose edges have size k. Consider a k-graph G and a collection of m agents. Agent i has a weight function w_i over all edges. Our task is to assign at most one edge e to each agent i (receiving a profit of w_i(e)) in such a way that no edge is assigned twice, that the set of assigned edges form a matching while maximizing total profit. We tackle online and stochastic variants of this problem and generalizations to other independence systems. In these versions, agents arrive one by one revealing their weight function and the decision maker must assign edges...
Read More