BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20191027T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20200329T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.18979.field_data.0@www.glad.uniroma1.it
DTSTAMP:20260405T093529Z
CREATED:20200126T181642Z
DESCRIPTION:We study mechanism design for combinatorial cost sharing. Imagi
 ne that multiple items or services are available to be shared among a set 
 of interested agents. The outcome of a mechanism in this setting consists 
 of an assignment\, determining for each item the set of players who are gr
 anted service\, together with respective payments. Although there are seve
 ral works studying specialized versions of such problems\, there has been 
 almost no progress for general combinatorial cost sharing domains until re
 cently \cite{DobzinskiO17}. The main goal of our work is to further unders
 tand this interplay in terms of budget balance and social cost approximati
 on. Towards this\, we provide a refinement of cross-monotonicity (trace-mo
 notonicity) that is applicable to iterative mechanisms. The trace here ref
 ers to the order in which players become finalized. On top of this\, we al
 so provide two parameterizations of cost functions which capture the behav
 ior of their average cost-shares. Based on our trace-monotonicity property
 \, we design a scheme of ascending cost sharing mechanisms which is applic
 able to the combinatorial cost sharing setting with symmetric submodular v
 aluations. Using our first cost function we identify conditions under whic
 h our mechanism is weakly group-strategyproof\, O(1)-budget-balanced and O
 (logn)-approximate with respect to the social cost. Finally\, we consider 
 general valuation functions and exploit our second parameterization to der
 ive a more fine-grained analysis of the Sequential Mechanism introduced by
  Moulin. This mechanism is budget balanced by construction\, but in genera
 l only guarantees a poor social cost approximation of n. We identify condi
 tions under which the mechanism achieves improved social cost approximatio
 n guarantees. 
DTSTART;TZID=Europe/Paris:20200130T140000
DTEND;TZID=Europe/Paris:20200130T140000
LAST-MODIFIED:20200528T094037Z
LOCATION:B203
SUMMARY:Cost Sharing over Combinatorial Domains - Georgios Birmpas (Univers
 ity of Oxford)
URL;TYPE=URI:http://www.glad.uniroma1.it/node/18979
END:VEVENT
END:VCALENDAR