Talks@DI

Existence and Complexity of Equilibria in Congestion Games

Transmissão através de Videoconferência

Speaker: Diogo Poças.

Abstract: We study the existence of approximate pure Nash equilibria (α-PNE) in weighted atomic congestion games with polynomial cost functions of maximum degree d. Previously it was known that d-approximate equilibria always exist, while nonexistence was established only for small constants, namely for 1.153-PNE. We improve significantly upon this gap, proving that such games in general do not have Θ̃(√d)-approximate PNE, which provides the first super-constant lower bound. Furthermore, we provide a black-box gap-introducing method of combining such nonexistence results with a specific circuit gadget, in order to derive NP-completeness of the decision version of the problem. In particular, deploying this technique we are able to show that deciding whether a weighted congestion game has an Õ(√d)-PNE is NP-complete. Previous hardness results were known only for the special case of exact equilibria and arbitrary cost functions. We also study the existence of approximate equilibria in weighted congestion games with general (nondecreasing) costs, as a function of the number of players n. We show that n-PNE always exist, matched by an almost tight nonexistence bound of Θ̃(n) which we can again transform into an NP-completeness proof for the decision problem.

Bio: Diogo Poças did his MSc in Mathematics and Applications at Instituto Superior Técnico, and his PhD in Mathematics at McMaster University. Before coming to FCUL, he worked as a postdoctoral researcher in the Operations Research Group at TU Munich. Diogo's research interests are on theoretical computer science, at the intersection of mathematics and general computer science. Recently, he has been working in algorithmic game theory topics such as the existence and computational complexity of finding Nash equilibria in games.

Personal webpage: https://diogopocas1991.gitlab.io.

Zoom: https://videoconf-colibri.zoom.us/j/88461206223.

14h30
Departamento de Informática
Imagem ilustrativa do evento, acompanhada da data de realização e outras informações relevantes

Em 2020, a Feira Internacional de Minerais, Gemas e Fósseis decorre num formato exclusivamente online.

Capa do livro

Sessão de lançamento do livro de Maria Amélia Loução (Ciências ULisboa).

Um programa exclusivo para alunos da área de Informática ou Tecnologias de Informação.

Fotografia de um curso de água

Submissão de pré-propostas até 07 de dezembro de 2020.

Speaker: Ulrich Kohlenbach (Department of Mathematics - Technische Universität Darmstadt).

Logótipo da iniciativa, sobre um fundo branco

A Cimeira contará com participações de Alto Nível, incluindo os Ministros da Ciência de Portugal e da Índia, e juntará representantes da academia e da indústria dos dois países, possibilitando a criação de parcerias bilaterais em ciência e tecnologia, bem como o reforço das redes já existentes, nas mais variadas áreas do conhecimento.

Imagem ilustrativa do evento, acompanhada da data de realização e outras datas importantes e dos logótipos das entidades organizadoras

O XIX ENE - Desafios para a Nova Década é duplamente especial, pois a SPECO - Sociedade Portuguesa de Ecologia - celebra as suas bodas de prata, 25 anos.

Imagem ilustrativa da iniciativa

Pré-inscrições a decorrer para as colheitas dos dias 09 e 11 de dezembro.

Speaker: Sebastian Engelke (University of Geneva).

Mudam-se os tempos, mudam-se as vontades - contributos da psicologia no ensino superior

Seminários sobre os temas "Méis Portugueses - caracterização química e avaliação da atividade biológica" e "Other uses for underutilized forest biomass".

Por Lorenzo Baravalle (CFCUL/GI2).

Por João Pedro Gouveia (CENSE - Center for Environmental and Sustainability Research - Energy and Climate - FCT-NOVA).

Logótipo dos Prémios Científicos Universidade de Lisboa / Caixa Geral de Depósitos, sobre um fundo azul escuro

Decorrem, até 21 de dezembro de 2020, as candidaturas aos Prémios Científicos Universidade de Lisboa / Caixa Geral de Depósitos de estímulo à publicação de artigos científicos.

Fotografia de um computador portátil, com a mensagem "Join us online" no respetivo ecrã

Candidaturas online de 01 a 31 de dezembro de 2020.

Logótipo do Programa Doutoral Plants for Life, inserido numa imagem ilustrativa do mesmo

Candidaturas a Bolsas de Doutoramento até 05 de janeiro de 2021.

Objectives: Provide students with basic workflows, platforms and tools to increase reproducibility at all scientific levels.

Objectives: Under the general framework of Global Change Ecology, the goal of this course is to provide the participants with the most recent and practical knowledge on the use of Functional Diversity.

Objectives: The objective of this course is to introduce participants to the details of communication and writing scientific publications. The main emphasis is on the most common form, the “primary scientific paper”, but other forms will be covered.

Objectives: Lack of fertile land to feed the exponentially growing population, insufficient water availability and quality, changes in the flow of nutrients through the bio-geo-cycles (especially N and P) and climate and land use changes are impacting ecosystem

Imagem ilustrativa do concurso, acompanhada do respetivo logótipo

Candidaturas para a 2.ª edição do Campus 2030 a decorrer até 07 de fevereiro de 2021 - uma oportunidade para estudantes, professores e investigadores converterem o seu campus num modelo global de sustentabilidade.

Objectives: Symbiosis is a key strategy for life on Earth.

Objectives: The goal of this course is to provide to the participants with current and practical knowledge on urban ecology, including ecological and social aspects. It aims at providing an integrated approach on urban socio-ecological systems.

Feixes luminosos

Ação de formação dirigida aos docentes e investigadores de Ciências ULisboa, pela formadora Sofia Sá, a decorrer nos dias 18 e 19 de fevereiro de 2021.

A sessão será transmitida na plataforma Zoom (restrita aos inscritos na ação).

Páginas