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

Online learning with consistency oracle.

Event Date: Nov 29, 2023 in ACGO, Seminars

Abstract:  A binary classification game is being played between a learner and an adversary. At each round, the adversary selects a natural number x and the learner has to predict its label h(x). Is there a bound on the number of mistakes made by the learner, assuming that h comes from some class H? Littlestone gave a learning algorithm which achieves an optimal mistake bound d, provided H has a certain combinatorial property. However, Littlestone’s algorithm is believed to be computationally demanding. Can we have a feasible strategy for the learner and if so, how many mistakes would...

Read More

Optimal Disease Screening Policies Under Budget Constraints.

Event Date: Nov 15, 2023 in ACGO, Seminars

Abstract:  We study the problem of selecting screening policies for a given disease in a large population which is divided into risk groups, and where we have a measure of benefit and cost for each possible policy. We want to find a selection of them, one for each risk group so that the total benefit is maximized and a budget constraint per time period is satisfied. To that end we start from an individual base model that accounts for the probabilistic appearance and evolution of the disease along stages. Our main result is an ergodic-like theorem which allows us to calculate the expected...

Read More

Computing Bayes-Nash Equilibria in Auctions via Online Learning.

Event Date: Nov 08, 2023 in ACGO, Seminars

Abstract:  Auction games are a central application of game theory in economics. However, while explicit formulas for Bayes-Nash equilibria are known for particular auction settings, we generally have to rely on numerical methods to predict the outcomes of auctions. We present a simple class of learning algorithms to approximate Bayes-Nash equilibria in these games. Surprisingly, while recent theoretical results suggest that such algorithms perform poorly in general matrix games, we provide experimental evidence that they perform very well in many different auction scenarios. Despite the...

Read More