Algorithm and Mechanism Design in Decision-making Environments

Other Titles


This dissertation studies algorithm and mechanism design for decision-making environments with specific characteristics regarding the input generation process and the desired output. We focus particularly on addressing the challenges posed by online input, stochastic input, input distributed among strategic and prone-to-failure agents, as well as considerations regarding the fairness of the algorithmic decisions made. Our contributions amount to making progress in the field of algorithmic decision-making by studying new versions of standard problems in Combinatorial Optimization, Optimal Stopping Theory, and Mechanism Design better tailored for such decision-making environments in one or more aspects. Each problem is accompanied by some theoretical performance guarantees appropriate for each setting, offering insights into the trade-offs between different assumptions and constraints. In the first part of this thesis we focus on Prophet Inequalities, a collection of results for online decision-making problems under uncertainty and we explore two aspects of those problems. The first has to do with the power of the decision-maker to decide the order in which to inspect parts of the input, or in other words, the order in which to eliminate uncertainty about the input. We introduce a model interpolating between the two extremes of having no such power to having full order-selection power and quantify the performance vs. freedom trade-offs. The second aspect has to do with the fairness of the decision-making process. We define two notions of Individual Fairness in the context of Prophet Inequality problems, discuss techniques for designing optimal algorithms under fairness constraints and prove competitiveness guarantees. We then study the emblematic Mechanism Design problem of Revenue-maximizing Auctions under the novel assumption that a subset of the bidders are “Byzantine”, a term borrowed from the area of Computer Systems, meaning they can behave in arbitrary ways, departing from the assumptions under which the mechanism was designed. In this setting, we prove a revenue monotonicity theorem characterizing exactly the settings in which the presence of those Byzantine, or misspecified bidders, does not hurt the performance (revenue) of the auction compared to an auction designed in the absence of them. Finally, we study the classic Combinatorial Optimization problem of Maximum Flow from a new, online perspective where sources arrive one at a time and request to send a unit of flow while the algorithm is required to serve each request, maintaining an optimal flow after each source arrival. To achieve this, the algorithm might need to modify the flow maintained at each step which is assumed to incur a cost. We analyze a natural algorithm for this problem and bound its worst-case cost using techniques developed for a similar online version of the Bipartite Matching problem.

Journal / Series

Volume & Issue


178 pages


Date Issued




Algorithmic Fairness; Mechanism Design; Online Decision-making; Online Maximum Flow; Prophet Inequalities


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Kleinberg, Robert

Committee Co-Chair

Committee Member

Agarwal, Rachit
Tardos, Eva

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record