Prophet Inequalities Require Only a Constant Number of Samples.

Event Date: May 15, 2024 in ACGO, Seminars

Abstract:  In a prophet inequality problem, n independent random variables are presented to a gambler one by one. The gambler decides when to stop the sequence and obtains the most recent value as a reward. We evaluate a stopping rule by the worst-case ratio between its expected reward and the expectation of the maximum variable. Because of its connections with resource allocation and posted-price mechanisms, this problem has been intensively studied, and several variants have been introduced. While most of the literature assumes that distributions are known to the gambler, recent work has...

Read More

Aggregating opinions — do we need (Kolmogorov) complexity?

Event Date: May 08, 2024 in ACGO, Seminars

Abstract:  Imagine a group of people that need each day to make some collective decision (for the entire group), choosing one of two options A and B. Some people prefer A, some prefer B, and others are OK with any of the two options. (The next day the preferences may change arbitrarily, and a new group choice is made.) The group management needs to choose A or B, in both cases making some people unhappy. This cannot be avoided completely (if someone wants A and someone else wants B, one of them will be unhappy), so the goal is more modest: each person should not be unhappy too many times....

Read More

Tariff Zone Assignment: Complexity Results ans Solution Approaches.

Event Date: Apr 24, 2024 in ACGO, Seminars

Abstract:  In the Tariff Zone Assignment problem, an operator is tasked with partitioning a transport network (i.e., a graph) into tariff zones in order to maximize revenue under a linear pricing model. In this model, customers pay a price proportional to the number of zones traveled through, up to some maximum accepted price. If this price gets exceeded, customers drop out of the model and thus generate no revenue at all. In this talk, first we will look at the complexity of this problem and show APX-hardness on star graphs and strong NP-hardness on paths. These complexity results motivate...

Read More

Oracle-Augmented Prophet Inequalities.

Event Date: Nov 30, 1999 in ACGO, Seminars

Abstract:  In the top-1-of-k prophet inequality setting, a gambler is given a sequence of n random variables X_1, …, X_n, taken from known distributions, observes their values in an adversarial order, and selects up to k of them, immediately after they are observed, so that the top value selected is as high as possible, comparing against a prophet who always selects the maximum realization. For k = 1, one recovers the classical prophet inequality, and thus this model serves as a generalization. In this talk, we look at a new approach to solve the top-1-of-k model. We generalize the...

Read More

Event Date: Apr 10, 2024 in ACGO, Seminars

Abstract:  In this talk, I will give an introduction to linear programming hierarchies, with a particular focus on the hierarchy by Sherali & Adams. I will discuss some limitations of the tool, but also ways to get useful and stronger relaxations.

Read More

The Limitations of Machine Learning & Us.

Event Date: Mar 25, 2024 in ACGO, Seminars

Abstract:  Machine learning (ML), particularly deep learning, is being used everywhere. However, not always is used well, ethically and scientifically. In this talk we first do a deep dive in the limitations of supervised ML and data, its key component. We cover small data, datification, bias, predictive optimization issues, evaluating success instead of harm, and pseudoscience, among other problems.  The second part is about our own limitations using ML, including different types of human incompetence: cognitive biases, unethical applications, no administrative competence, copyright...

Read More