Back to search

University of Patras

Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής

Abstract

dc:description

In this dissertation we consider auction markets and examine their properties and how these are affected by the way the participants act. An auction may refer to any mechanism or set of rules governing a resource allocation process. Designing such a mechanism is not an easy task and this is partly due to their vulnerability to strategic manipulation by the participants. Our goal is to examine the theoretical properties of auction mechanisms in order to predict, explain, or even adjust their behavior in practice in terms of some desired features.We focus on sponsored search auctions, which constitute the leading procedure in Internet advertising. We adopt a game-theoretic approach and provide Price of Anarchy bounds in order to measure the efficiency loss due to the strategic behavior of the players. Moreover, we prove revenue guarantees to bound the suboptimality of GSP (generalized second price mechanism) in that respect. Ιn particular, we define variants of the GSP auction mechanism that yield good revenue guarantees. We also consider the problem of designing an optimal auction in the single-item setting. We prove a strong APX-hardness result that applies to the 3-player case. We furthermore give a separation result between the revenue of deterministic and randomized optimal auctions.

Degree

thesis:*
Grantor dc:publisher
University of Patras
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kyropoulou, Maria
  • Κυροπούλου, Μαρία

Subjects

dc:subject × 20

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/35138

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kyropoulou, Maria; Κυροπούλου, Μαρία. Υπολογιστικά ζητήματα σε στρατηγικά παίγνια και διαδικασίες κοινωνικής επιλογής. University of Patras, 2014. http://hdl.handle.net/10442/hedi/35138