10 octobre 2024: Mingkun Liu et Kanstantsin Pashkovich

par Kanstantsin Pashkovich (University of Waterloo), Mingkun Liu (LIPN)

jeudi 10 oct. 2024, 14:00 → 17:00 Europe/Paris

institut

14h00 Mingkun Liu LIPN, Université Paris 13

Length spectra of random metric map of large genus: a Teichmüller approach.

The Weil--Petersson model of random hyperbolic surfaces has been extensively studied since the pioneering work of Guth--Parlier--Young and Mirzakhani in 2010. In this talk, after a brief historical review, we will focus on the bottom of the length spectrum. More precisely, we study short closed geodesics on a random hyperbolic surface of large genus. It turns out that the lengths of these geodesics are distributed in exactly the same way as those of the short cycles in a large random graph. This is a joint work with Simon Barazer and Alessandro Giacchetto.

15h30 Kanstantsin Pashkovich, University of Waterloo

Contracts for Functions Based on Graphs

We study contracts for combinatorial problems in multi-agent settings. In this problem, a principal designs a contract with several agents, whose actions the principal is unable to observe. The principal is able to see only the outcome of the agents' collective actions; and the outcome is either a success or failure. All agents that decided to exert effort incur costs, and so naturally all agents expect a fraction of the principal's reward as a compensation. The principal needs to decide what fraction of their reward to give to each agent so that the principal's expected utility is maximized. One of our focuses is on the case when the principal's reward function is supermodular and is based on some graph. Recently, Deo-Campo Vuong et.al. showed that for this problem it is impossible to provide any finite multiplicative approximation or additive FPTAS unless P= NP. On a positive note, Deo-Campo Vuong et.al. provided an additive PTAS for the case when all agents have the same cost. Der-Campo Vuong et.al. asked whether an additive PTAS can be obtained for the general case, i.e for the case when agents potentially have different costs. In this work, we answer this open question in positive.