BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T210750Z
UID:Seminar-EcCo-993@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20210317T130000
DTEND:20210317T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Themistoklis Melissourgos: Walrasian Equilibria in Markets with Small Demands\n\nWe study the complexity of finding a Walrasian equilibrium in markets where the agents have k-demand valuations. These valuations are an extension of unit-demand valuations where a bundle's value is the maximum of its k-subsets' values. For unit-demand agents, where the existence of a Walrasian equilibrium is guaranteed, we show that the problem is in quasi-NC. For k=2, we show that it is NP-hard to decide if a Walrasian equilibrium exists even if the valuations are submodular, while for k=3 the hardness carries over to budget-additive valuations. In addition, we give a polynomial-time algorithm for markets with 2-demand single-minded valuations, or unit-demand valuations.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=993
LOCATION:
END:VEVENT
END:VCALENDAR