Noticias en español
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...
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 MoreA 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...
Read MoreSingle-choice secretary problems with ordinal advice.
Abstract: We examine variations of the classical secretary problem in a new setting, where the decision-maker (DM) can request one (or more) bits of ordinal information from agents before they arrive. Specifically, each agent has private information (their weight) that is publicly revealed upon arrival. As usual, the DM must irrevocably decide whether to select the agent or not after this step. Additionally, at any given time, the DM can privately ask yes-or-no questions to agents who have not yet arrived, and the agents can only answer ordinal questions based on comparing their private...
Read MoreLearning 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...
Read More