BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/423
DTSTAMP:20230914T125924Z
SUMMARY:Price of Anarchy\, Auctions\, and Approximations
DESCRIPTION:Speaker: Dr. Sayan Bhattacharya (Max-Planck-Institut fur Inform
atik\nDepartment 1: Algorithms and Complexity\nCampus E14\, Room 318\n6612
3 Saarbrucken\nGermany)\n\nAbstract: \nIn many applications driven by the
internet\, computation has to be performed in the presence of strategic in
teractions between multiple autonomous entities. This raises the question:
What happens when the input to an algorithm are controlled by rational ag
ents\, and each of them\, in turn\, is affected by the algorithm's output?
A systematic study of this question led to the growth of ``algorithmic
game theory''. In the talk I will focus on two important topics within thi
s field -- the study of auctions\, and price of anarchy.\n\nMotivated by t
he electronic markets such as eBay and Google adwords\, I will first visit
the topic of Auction Theory from an algorithmic perspective. In this se
tting\, an auctioneer wants to sell some items to a group of bidders. The
bidders' valuations for the items are private knowledge\, but they are dra
wn from publicly known prior distributions. An auction scheme is called ``
truthful'' if it gives an incentive to every bidder to report her true val
ue. The goal is to find a truthful auction that maximizes the seller's rev
enue.\n\nNaturally\, to execute the optimal auction we need to know the pr
ior distributions. An intriguing question is to design a truthful auction
that does not require the knowledge of these priors\, but still manages to
get a constant fraction of the optimal revenue. Such auctions are called
``prior-free''. I will conclude the first part of the talk by presenting m
y work on prior-free auctions with asymmetric bidders.\n\nNext\, I will co
nsider the game-theoretic variant of a classical scheduling-problem. The s
etting captures a distributed environment with heterogeneous machines (or
data centers) and jobs (or clients) that are situated across different geo
graphical locations. The objective is to minimize the weighted sum of th
e completion times of the jobs. Each job\, however\, is a selfish agent an
d selects a machine that minimizes its own completion time. This defin
es a game between the jobs. A Nash equilibrium of this game is an outcom
e where no job wants to switch to another machine. The ``price of anarchy'
' is the maximum possible ratio between the objective at a Nash equilibriu
m and the objective at the globally-optimal outcome. Intuitively\, it meas
ures the degradation in overall system-performance due to the presence of
selfish jobs.\n\nI will present a generic characterization of the scheduli
ng policies which give a small Price of Anarchy. On the technical side\, I
will show how to derive this result using a linear program for the underl
ying optimization problem and dual-fitting.\n\nI will conclude the talk by
presenting some interesting open directions for future research.\n
URL:https://www.tcs.tifr.res.in/web/events/423
DTSTART;TZID=Asia/Kolkata:20131119T160000
DTEND;TZID=Asia/Kolkata:20131119T170000
LOCATION:D-405 (D-Block Seminar Room)
END:VEVENT
END:VCALENDAR