자료유형  

 학위논문

Control Number  

0016934176

International Standard Book Number  

9798380318327

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Arsenis, Makis.

Publication, Distribution, etc. (Imprint  

[S.l.] : Cornell University., 2023

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2023

Physical Description  

1 online resource(179 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-03, Section: B.

General Note  

Advisor: Kleinberg, Robert.

Dissertation Note  

Thesis (Ph.D.)--Cornell University, 2023.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약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.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Applied mathematics.

Subject Added Entry-Topical Term  

Systems science.

Index Term-Uncontrolled  

Algorithmic fairness

Index Term-Uncontrolled  

Mechanism design

Index Term-Uncontrolled  

Online decision-making

Index Term-Uncontrolled  

Online maximum flow

Index Term-Uncontrolled  

Prophet Inequalities

Added Entry-Corporate Name  

Cornell University Computer Science

Host Item Entry  

Dissertations Abstracts International. 85-03B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:641266