BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//5.981//EN
TZID:Asia/Jerusalem
X-WR-TIMEZONE:Asia/Jerusalem
BEGIN:VEVENT
UID:17@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20201028T113000
DTEND;TZID=Asia/Jerusalem:20201028T123000
DTSTAMP:20201109T060748Z
URL:https://web.iem.technion.ac.il/site/iemevents/when-both-players-choose
-dominated-actions-underweighting-rare-events-in-2-player-repeated-games/
SUMMARY:When both players choose dominated actions: Underweighting rare eve
nts in 2-player repeated games [ \n Game Theory Seminar\n Seminars
\n \n ]
DESCRIPTION:By: Ori Plonsky\n Advisors: \n Where: Zoom From:\nTechnion\nA
bstract:\n\nBehavioral decision studies of individuals who make repeated d
ecisions with feedback reveal robust evidence that people behave as if the
y believe “it won’t happen to me”\, a phenomenon coined underweighti
ng of rare events. We experimentally show that the tendency to underweight
rare events persists in 2-person repeated games with stochastic payoffs\,
and that other agents can learn to exploit it. In a simultaneous-move asy
mmetric 2x2 game\, most row players consistently choose a stochastically d
ominated action that provides a better payoff most of the time but on aver
age leads to a large loss over the equilibrium prediction\, behavior consi
stent with underweighting of the rare event. In response\, most column pla
yers learn to exploit this bias by choosing a strictly dominated action th
at is worse for the row players on average but better most of the time. Th
at is\, due to underweighting of rare events by the row players\, most dya
ds converge to a profile of two dominated strategies. A second study rules
out different explanations like boredom\, altruism or risk seeking.\n\nJo
int work with Yefim Roth (University of Haifa)\n\nLink to Seminar Zoom
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:23@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20201111T113000
DTEND;TZID=Asia/Jerusalem:20201111T123000
DTSTAMP:20201109T060933Z
URL:https://web.iem.technion.ac.il/site/iemevents/an-algorithmic-framework
-for-approximating-maximin-share-allocation-of-chores/
SUMMARY:An Algorithmic Framework for Approximating Maximin Share Allocation
of Chores [ \n Game Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Xin Huang\n Advisors: \n Where: ZOOM From:\nTechnion\nAbst
ract:\n\nIn this paper\, we consider the problem of how to fairly dividing
m indivisible chores among n agents. The fairness measure we considered h
ere is the maximin share. The previous best known result is that there alw
ays exists a 4/3 approximation maximin share allocation. With our algorit
hm\, we can always find a 11/9 approximation maximin share allocation for
any instance. We also discuss how to improve the efficiency of the algorit
hm and its connection to the job scheduling problem.\n\nSeminar Zoom Link
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:28@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20201125T113000
DTEND;TZID=Asia/Jerusalem:20201125T123000
DTSTAMP:20201118T173908Z
URL:https://web.iem.technion.ac.il/site/iemevents/fair-cake-division/
SUMMARY:Fair Cake Division [ \n Game Theory Seminar\n Seminars\n
\n ]
DESCRIPTION:By: Nidhi Rathi \n Advisors: \n Where: ZOOM From:\nthe Indian
Institute of Science\nAbstract:\n\nThe classic cake-cutting problem provid
es a model for addressing fair allocation of a divisible resource (metapho
rically\, the cake) among agents with distinct preferences. Envy-free (fai
r) cake divisions with contiguous pieces are known to exist under mild con
ditions\, but it is computationally hard to find them. In this talk\, I wi
ll present two of my recent results which complements these existential (a
nd non-constructive) guarantees by developing polynomial-time approximatio
n algorithms and by identifying computationally tractable instances for fa
ir cake division. First\, I will discuss an efficient algorithm for findin
g a cake division whose envy is multiplicatively bounded by 1/3. Moving fo
rward\, I will present a result that develops efficient cake-cutting algor
ithms to find envy-free divisions for a broad class of valuations (that sa
tisfies the monotone likelihood ratios property). In particular\, our algo
rithmic result holds when the agents' valuations are induced by linear tra
nslations of any log-concave function\, such as Gaussian\, exponential\, l
inear\, or binomial.\n\n \;\n\nJoint work with Siddharth Barman\, Eshw
ar Ram Arunchaleswaran and Rachitesh Kumar\n\n \;\n\nZoom Link
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:31@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20201209T113000
DTEND;TZID=Asia/Jerusalem:20201209T113000
DTSTAMP:20201203T070657Z
URL:https://web.iem.technion.ac.il/site/iemevents/incomplete-information-v
cg-contracts-for-common-agency/
SUMMARY:Incomplete Information VCG Contracts for Common Agency [ \n Gam
e Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Tal Alon \n Advisors: \n Where: Zoom From:\nTechnion\nAbst
ract:\nWe study the social efficiency of contracts as economic mechanisms
when multiple principals simultaneously manage a common agent. We consider
an incomplete-information setting: The agent chooses an unobservable acti
on that induces both a cost for the agent and an expected value for each p
rincipal. The sum of these terms is referred to as the resulting social we
lfare. The agent’s choice is incentivized by payment schemes (“contrac
ts”) set forth by the principals\, who have different private values for
different stochastic outcomes of the agent’s choice. We enforce two sta
ndard properties of contracts: individual rationality a.k.a. IR (for the p
rincipals)\, and limited liability a.k.a. LL (for the agent).\n\nJoint wor
k with Ron Lavi\, Elisheva Shamash\, and Inbal Talgam-Cohen\n\nZoom Link
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:39@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20201223T113000
DTEND;TZID=Asia/Jerusalem:20201223T123000
DTSTAMP:20201220T115150Z
URL:https://web.iem.technion.ac.il/site/iemevents/settling-the-complexity-
of-nash-equilibrium-in-congestion-games/
SUMMARY:A Market-Inspired Bidding Scheme for Peer Review Paper Assignment [
\n Game Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Reshef Meir \n Advisors: \n Where: Zoom From:\nTechnion\nA
bstract:\n\nWe propose a market-inspired bidding scheme for the assignment
of paper reviews in large academic conferences. We provide an analysis of
the incentives of reviewers during the bidding phase\, when reviewers hav
e both private costs and some information about the demand for each paper\
; and their goal is to obtain the best possible k papers for a predetermin
ed k.\n\nWe show that by assigning `budgets' to reviewers and a `price' fo
r every paper that is (roughly) proportional to its demand\, the best resp
onse of a reviewer is to bid sincerely\, i.e.\, on her most favorite pape
rs\, and match the budget even when it is not enforced. This game-theore
tic analysis is based on a simple extension of the Trading Post mechanism.
\nWe show via extensive simulations on bidding data from real conferences\
, that our bidding scheme would substantially improve both the bid distr
ibution and the resulting assignment.\n\n \;\n\njoint work with Jerome
Lang\, Lulien Lesca\, Nick Mattei\, and Natan Kaminsky\n\nZoom Link\n\n&n
bsp\;
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:40@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210106T113000
DTEND;TZID=Asia/Jerusalem:20210106T123000
DTSTAMP:20201230T172116Z
URL:https://web.iem.technion.ac.il/site/iemevents/settling-the-complexity-
of-nash-equilibrium-in-congestion-games-2/
SUMMARY:Settling the complexity of Nash equilibrium in congestion games [ \
n Game Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Yakov Babichenko \n Advisors: \n Where: Zoom From:\nTechni
on\nAbstract:\n\nWe consider (i) the problem of finding a (possibly mixed)
Nash equilibrium in congestion game\, and (ii) the problem of finding an
(exponential precision) fixed point of the gradient descent dynamics of a
smooth function f ∶ [0\, 1]^n → R. We prove that these problems are eq
uivalent. Our result holds for various explicit descriptions of f\, rangin
g from (almost general) arithmetic circuits\, to degree-5 polynomials. By
a very recent result of [FGHS20]\, this implies that these problems are PP
AD ∩ PLS-complete. As a corollary\, we also obtain the following equival
ence of complexity classes:\n\nCCLS = PPAD∩PLS\n\nZoom https://technion.
zoom.us/j/95592625013
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:51@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210120T113000
DTEND;TZID=Asia/Jerusalem:20210120T123000
DTSTAMP:20210113T082053Z
URL:https://web.iem.technion.ac.il/site/iemevents/prophet-and-secretary-on
line-algorithms-for-matching-in-general-graphs/
SUMMARY:Prophet and Secretary Online Algorithms for Matching in General Gra
phs [ \n Game Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Michal Feldman \n Advisors: \n Where: ZOOM From:\nTel-Avi
v University\nAbstract:\n\nProphet and Secretary Online Algorithms for Mat
ching in General Graphs\n\nA common tension in market scenarios is choosin
g the right timing to commit to a decision. This tension is captured by th
e mathematical literature of optimal stopping theory\, within two models t
hat have become to be known as the secretary problem and the prophet inequ
ality. In these models\, a sequence of originally-unknown values arrive on
e by one. Upon arrival\, the online algorithm observes the value and shoul
d decide whether or not to accept it. In secretary settings\, the value se
quence is arbitrary\, but the values arrive in a uniformly random order. I
n prophet settings\, every value is drawn from a known probability distrib
ution\, but the arrival order is arbitrary.\n\nIn this talk I will review
the basic settings of secretary and prophet\, as well as previous extensio
ns to matching in bipartite graphs with 1-sided vertex arrival. I will the
n present our recent work\, which studies online algorithms (in both secre
tary and prophet settings) for matching in *general* graphs\, under both v
ertex- and edge-arrival models. We provide tight competitive ratios for bo
th secretary and prophet matching scenarios under vertex arrival. Under ed
ge arrival\, we provide competitive ratios that improve upon the state of
the art.\n\nBased on the following joint work with Tomer Ezra\, Nick Gravi
n\, and Zhihao Tang:\n\nhttps://arxiv.org/abs/2002.09807\n\nhttps://arxiv.
org/abs/2011.01559\n\nBe rational and attend\n\nZoom Link\n\nhttps://techn
ion.zoom.us/j/95592625013
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:74@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210519T113000
DTEND;TZID=Asia/Jerusalem:20210519T123000
DTSTAMP:20210512T130803Z
URL:https://web.iem.technion.ac.il/site/iemevents/collective-information-a
cquisition/
SUMMARY:Collective Information Acquisition [ \n Game Theory Seminar\n
Seminars\n \n ]
DESCRIPTION:By: Ran Wilat \n Advisors: \n Where: Bloomfield 424 From:\nBe
n-Gurion University\nAbstract:\n\nWe consider the problem faced by a group
of players who bargain over what public signal to acquire before deciding
on a collective action. The players differ in their privately known state
-dependent payoffs from taking the action\, and therefore differ also in t
heir willingness to pay for the public signal. We take a mechanism design
approach to characterize the frontier of outcomes achievable via bargainin
g over information. We identify novel distortions in the optimal informati
on structure that arise from the information asymmetry and because\, after
the signal is realized\, the outcome is determined in equilibrium of a su
bsequent voting game.\n\n(joint with K. Eliaz)
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:76@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210602T113000
DTEND;TZID=Asia/Jerusalem:20210602T123000
DTSTAMP:20210530T052855Z
URL:https://web.iem.technion.ac.il/site/iemevents/informative-tests-in-sig
naling-environments/
SUMMARY:Informative Tests in Signaling Environments [ \n Game Theory Se
minar\n Seminars\n \n ]
DESCRIPTION:By: Ran Weksler\n Advisors: \n Where: Bloomfield 424 From:\nU
niversity of Haifa\nAbstract:\n\nWe study a receiver’s learning problem
of choosing an informative test in a signaling environment. Each test that
the receiver chooses induces a signaling subgame. Thus\, in addition to t
he direct effect of the chosen test on the information that the receiver o
btains\, it also has an indirect effect on the receiver’s information th
rough the sender’s signaling strategy. We analyze how signaling consider
ations affect the receiver’s preference relation over tests. Specificall
y\, we find that the receiver’s preference relation does not comply with
Blackwell’s order. Our findings may help shed light on phenomena such a
s grade inflation and information coarsening.\n\n \;\n\n(joint with B.
Zick)
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:81@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210616T113000
DTEND;TZID=Asia/Jerusalem:20210616T123000
DTSTAMP:20210609T064041Z
URL:https://web.iem.technion.ac.il/site/iemevents/barter-exchange-with-len
gth-sensitive-utility-functions/
SUMMARY:Barter Exchange with Length Sensitive Utility Functions [ \n Ga
me Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Matan-el Shpiro \n Advisors: \n Where: Bloomfield 424 Fro
m:\nTechnion\nAbstract:\n\nConsider a \\emph{barter exchange} problem over
a finite set of agents\, where each agent owns an item and is also associ
ated with a (privately known) \\emph{wish list} of items belonging to the
other agents. An outcome of the problem is a (re)allocation of the items t
o the agents such that each agent either keeps her own item or receives an
item from her (reported) wish list\, subject to the constraint that the l
ength of the trading cycles induced by the allocation is up-bounded by a p
respecified \\emph{length bound} $k$. The utility of an agent from an allo
cation is $0$ if she keeps her own item\; and it is $\\lambda(\\ell)$ if s
he receives an item from her (true) wish list and participates in a tradin
g cycle of length $2 \\leq \\ell \\leq k$\, where $\\lambda$ is a prespeci
fied monotonically non-increasing \\emph{length function}. (The agent incu
rs a large dis-utility if she receives an item that is neither hers nor be
longs to her wish list.)\n\nIn this talk\, we investigate the aforemention
ed barter exchange problem from the perspective of mechanism design withou
t money\, aiming for truthful (and individually rational) mechanisms whose
objective is to maximize the \\emph{social welfare}. As the construction
of a social welfare maximizing allocation is computationally intractable f
or length bounds $k \\geq 3$\, we focus on (computationally efficient) tru
thful mechanisms that approximate the optimal social welfare. In particula
r\, we establish upper and lower bounds on the guaranteed approximation ra
tio\, expressed in terms of the length bound $k$ and the length function $
\\lambda$. Our main technical contribution is an algorithmic tool that can
be viewed as a truthful version of the \\emph{local search} paradigm.\n\n
(joint with Y. Emek)
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:104@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210707T113000
DTEND;TZID=Asia/Jerusalem:20210707T113000
DTSTAMP:20210630T095052Z
URL:https://web.iem.technion.ac.il/site/iemevents/learner-private-sequenti
al-learning-and-convex-optimization/
SUMMARY:Learner-Private Sequential Learning and Convex Optimization [ \n
Game Theory Seminar\n Seminars\n \n ]
DESCRIPTION:By: Kuang Xu \n Advisors: \n Where: Bloomfield 424 From:\nSta
nford University\nAbstract:\n\nThe increasing ubiquity of large-scale infr
astructures for surveillance and data analysis has made understanding the
impact of privacy a pressing priority. We propose a framework for studying
a fundamental query complexity versus privacy tradeoff in sequential lea
rning. The central question is: how can one perform learning in such a man
ner that makes sure that an overseeing adversary cannot obtain the learned
model by observing the queries. We will examine two formulations of the
model (deterministic and Bayesian)\, and in both cases establish matching
upper and lower bounds on the optimal query complexity\, for a given level
of privacy guarantees. The analysis will exploit on some essential combi
natorial as well as information theoretic structures of the problem\, whic
h we will also discuss.\n\nPapers:\nhttps://arxiv.org/pdf/1805.02136.pdf\n
\nhttps://arxiv.org/abs/1911.06903\n\nhttps://arxiv.org/abs/1909.09836\n\n
https://arxiv.org/pdf/2102.11976.pdf\n\n \;\n\nBio: Kuang Xu is an
Associate Professor of Operations\, Information and Technology at Stanford
Graduate School of Business\, and Associate Professor by courtesy with th
e Electrical Engineering Department\, Stanford University. Born in Suzhou
\, China\, he received the B.S. degree in Electrical Engineering (2009) fr
om the University of Illinois at Urbana-Champaign\, and the Ph.D. degree i
n Electrical Engineering and Computer Science (2014) from the Massachusett
s Institute of Technology. His research focuses on understanding fundamen
tal properties and design principles of large-scale stochastic systems usi
ng tools from probability theory and optimization\, with applications in q
ueueing networks\, privacy and machine learning. He is a recipient of the
First Place in the INFORMS George E. Nicholson Student Paper Competition
(2011)\, the Best Paper Award\, as well as the Kenneth C. Sevcik Outstandi
ng Student Paper Award at ACM SIGMETRICS (2013)\, and the ACM SIGMETRICS
Rising Star Research Award (2020). He currently serves as an Associate Edi
tor for Operations Research.
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VEVENT
UID:108@web.iem.technion.ac.il
DTSTART;TZID=Asia/Jerusalem:20210715T103000
DTEND;TZID=Asia/Jerusalem:20210715T113000
DTSTAMP:20210711T061737Z
URL:https://web.iem.technion.ac.il/site/iemevents/equitable-voting-rules/
SUMMARY:Equitable voting rules [ \n Game Theory Seminar\n Seminars\
n \n ]
DESCRIPTION:By: Omer Tamuz \n Advisors: \n Where: Bloomfield 424 and ZOOM
From:\nCaltech\nAbstract:\nMay’s Theorem (1952)\, a celebrated result in
social choice\, provides the foundation for majority rule. May’s crucia
l assumption of symmetry\, often thought of as a procedural equity require
ment\, is violated by many choice procedures that grant voters identical r
oles. We show that a weakening of May’s symmetry assumption allows for a
far richer set of rules that still treat voters equally. We show that suc
h rules can have minimal winning coalitions comprising a vanishing fractio
n of the population\, but not less than the square root of the population
size. Methodologically\, we introduce techniques from group theory and ill
ustrate their usefulness for the analysis of social choice questions.\n(wi
th Laurent Bartholdi\, Wade Hann-Caruthers\, Maya Josyula\, and Leeat Yari
v)\n\nZoom Link\n\nhttps://technion.zoom.us/j/94614628255
CATEGORIES:Game Theory Seminar,Seminars
END:VEVENT
BEGIN:VTIMEZONE
TZID:Asia/Jerusalem
X-LIC-LOCATION:Asia/Jerusalem
BEGIN:STANDARD
DTSTART:20201025T010000
TZOFFSETFROM:+0300
TZOFFSETTO:+0200
TZNAME:IST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20210326T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0300
TZNAME:IDT
END:DAYLIGHT
END:VTIMEZONE
END:VCALENDAR