BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:69cf6bdc14f7f
DTSTART;TZID=America/Toronto:20241203T130000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241203T140000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/co-reading-g
 roup-mahtab-alghasi
SUMMARY:C&O Reading Group - Mahtab Alghasi
CLASS:PUBLIC
DESCRIPTION:TITLE: A constant factor approximation for Nash social welfare 
 with\nsubadditive valuations\, Part II\n\nSPEAKER:\n Mahtab Alghasi\n\nAFF
 ILIATION:\n University of Waterloo\n\nLOCATION:\n MC 6029\n\nABSTRACT::Soc
 ial welfare refers to a class of optimization problems\nwhere the goal is 
 to allocate subsets of resources $\\mathcal{I}$ among\nagents $\\mathcal{A
 }$ (or people) such that maximizes the overall\n\"happiness\" of society i
 n a fair and efficient manner. More\nspecifically\, each agent $i \\in \\m
 athcal{I}$ has an intrinsic\n\\emph{valuation} function $v_i: 2^{\\mathcal
 {I}}\\rightarrow\n\\mathbb{R}$\, which is a monotone function with $v_i(\\
 emptyset)=0$\, and\n$v_i$ quantifies the intrinsic value for subsets of it
 ems $S\\subseteq\n\\mathcal{I}$. \n\nVariations of allocation with differe
 nt valuation and objective\nfunctions has been studied in different areas 
 of computer science\,\neconomies\, and game theory. In this talk we focus 
 on the Nash social\nwelfare welfare (NSW) problem\; given an allocation $\
 \mathcal{S}=\n(S_i)_{i\\in \\mathcal{A}}$ the goal is to maximize the geom
 etric mean\nof agents valuations.\n\nUnfortunately\, Nash social welfare p
 roblem is NP-hard already in the\ncase of two agents with identical additi
 ve valuations\, and it is\nNP-hard to approximate within a factor better t
 han 0.936 for additive\nvaluations and $(1-\\frac{1}{e})$ for submodular v
 aluation. \n\nMoreover\, the current best approximation factors of $\\sim
 eq 0.992$ for\nadditive valuations and $(\\frac{1}{4}-\\epsilon)$ for subm
 odular\nvaluations were found by Barman et al (2018) and Garg et al. (2023
 )\,\nrespectively.\n\nIn this talk\, we present a sketch of the algorithm 
 in recent work by\nDobzinski et al.\, which proves the first constant-fact
 or approximation\nalgorithm (with a fairly large constant $\\sim \\frac{1}
 {375\,000}$) for\nNSW problem with subadditive valuations accessible via d
 emand queries.
DTSTAMP:20260403T072724Z
END:VEVENT
END:VCALENDAR