Back to search

Cornell University

Algorithm and Mechanism Design in Decision-making Environments

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Arsenis, Makis
Chair dc:contributor.chair
  • Kleinberg, Robert
Committee members dc:contributor.committeemember
  • Agarwal, Rachit
  • Tardos, Eva

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16219233
Dc Identifier Other
ProQuest Submission ID: 13811
ProQuest Publication ID: 30572587

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Arsenis, Makis. Algorithm and Mechanism Design in Decision-making Environments. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114564