國立虎尾科技大學 |

Algorithmic Mechanism Design in Dynamic Environments.

Record Type:	Language materials, manuscript : Monograph/item
Title/Author:	Algorithmic Mechanism Design in Dynamic Environments./
Author:	Psomas, Christos Alexandros.
Description:	1 online resource (125 pages)
Notes:	Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
Contained By:	Dissertation Abstracts International78-11B(E).
Subject:	Computer science. -
Online resource:	click for full text (PQDT)
ISBN:	9780355033748

Algorithmic Mechanism Design in Dynamic Environments.
Psomas, Christos Alexandros.

Algorithmic Mechanism Design in Dynamic Environments. - 1 online resource (125 pages)

Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.

Thesis (Ph.D.)

Includes bibliographical references

Over the past few decades, a new field has emerged from the interaction between Computer Science and Game Theory: Algorithmic Mechanism Design. The field has seen tremendous growth and has been extremely successful in tackling a wide variety of problems. Despite all this progress, the vast majority of the literature to date focuses on static, one-time decisions. In many situations of interest, however, this simplification is too far from reality. For example, a search engine must choose how to allocate its advertising inventory in the face of changing search queries and advertiser budgets. In a cloud computing center resources need to be dynamically reallocated in response to the arrival of new computational tasks of varying priority. This thesis explores the interplay of incentives and the dynamic nature of decision-making in the design of efficient mechanisms.

Electronic reproduction.
Ann Arbor, Mich. :
ProQuest,
2018

Mode of access: World Wide Web

ISBN: 9780355033748Subjects--Topical Terms:

573171
Computer science.
Index Terms--Genre/Form:

554714
Electronic books.

Algorithmic Mechanism Design in Dynamic Environments.
LDR:03666ntm a2200361Ki 4500 001 910768
005 20180517112610.5
006 m o u
007 cr mn||||a|a||
008 190606s2017 xx obm 000 0 eng d
020 $a 9780355033748
035 $a (MiAaPQ)AAI10281502
035 $a (MiAaPQ)berkeley:16945
035 $a AAI10281502
040 $a MiAaPQ $b eng $c MiAaPQ
099 $a TUL $f hyy $c available through World Wide Web
100 1 $a Psomas, Christos Alexandros. $3 1182222
245 1 0 $a Algorithmic Mechanism Design in Dynamic Environments.
264 0 $c 2017
300 $a 1 online resource (125 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertation Abstracts International, Volume: 78-11(E), Section: B.
500 $a Adviser: Christos Papadimitriou.
502 $a Thesis (Ph.D.) $c University of California, Berkeley $d 2017.
504 $a Includes bibliographical references
520 $a Over the past few decades, a new field has emerged from the interaction between Computer Science and Game Theory: Algorithmic Mechanism Design. The field has seen tremendous growth and has been extremely successful in tackling a wide variety of problems. Despite all this progress, the vast majority of the literature to date focuses on static, one-time decisions. In many situations of interest, however, this simplification is too far from reality. For example, a search engine must choose how to allocate its advertising inventory in the face of changing search queries and advertiser budgets. In a cloud computing center resources need to be dynamically reallocated in response to the arrival of new computational tasks of varying priority. This thesis explores the interplay of incentives and the dynamic nature of decision-making in the design of efficient mechanisms.
520 $a In the first part of this thesis we study Dynamic Auction Design. We introduce a novel class of dynamic auction problems in which a monopolist is selling m items in m consecutive stages to n buyers. We study these problem from several different perspectives: Computational Complexity, i.e. how hard is it to compute the optimal auction, Competition Complexity, i.e. how much additional competition is necessary for a standard Vickrey (second-price) auction at every stage to extract more revenue than the optimal auction, Power of Adaptivity, i.e. what is the revenue gap between adaptive and non-adaptive auctions, Power of Commitment, i.e. what happens if the seller cannot commit to her future behavior.
520 $a In the second part of this thesis we study Dynamic Fair Division. We introduce a novel class of resource allocation problems in which resources are shared between agents dynamically arriving and departing over time. For a single resource, when n agents are present, there is only one truly "fair" allocation: each agent receives 1/n of the resource. Implementing this static solution over time is notoriously impractical. There are too many disruptions to existing allocations: for a new agent to get her fair share, all other agents must give up a small piece. What if, at every c arrivals we could only reclaim resources from a fixed number of agents d? We provide non-wasteful such algorithms that are almost optimal with respect to fairness, even for multiple, heterogeneous resources.
533 $a Electronic reproduction. $b Ann Arbor, Mich. : $c ProQuest, $d 2018
538 $a Mode of access: World Wide Web
650 4 $a Computer science. $3 573171
655 7 $a Electronic books. $2 local $3 554714
690 $a 0984
710 2 $a ProQuest Information and Learning Co. $3 1178819
710 2 $a University of California, Berkeley. $b Computer Science. $3 1179511
773 0 $t Dissertation Abstracts International $g 78-11B(E).
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=10281502 $z click for full text (PQDT)