ترغب بنشر مسار تعليمي؟ اضغط هنا

Leadership in Singleton Congestion Games: What is Hard and What is Easy

66   0   0.0 ( 0 )
 نشر من قبل Nicola Gatti
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

We study the problem of computing Stackelberg equilibria Stackelberg games whose underlying structure is in congestion games, focusing on the case where each player can choose a single resource (a.k.a. singleton congestion games) and one of them acts as leader. In particular, we address the cases where the players either have the same action spaces (i.e., the set of resources they can choose is the same for all of them) or different ones, and where their costs are either monotonic functions of the resource congestion or not. We show that, in the case where the players have different action spaces, the cost the leader incurs in a Stackelberg equilibrium cannot be approximated in polynomial time up to within any polynomial factor in the size of the game unless P = NP, independently of the cost functions being monotonic or not. We show that a similar result also holds when the players have nonmonotonic cost functions, even if their action spaces are the same. Differently, we prove that the case with identical action spaces and monotonic cost functions is easy, and propose polynomial-time algorithm for it. We also improve an algorithm for the computation of a socially optimal equilibrium in singleton congestion games with the same action spaces without leadership, and extend it to the computation of a Stackelberg equilibrium for the case where the leader is restricted to pure strategies. For the cases in which the problem of finding an equilibrium is hard, we show how, in the optimistic setting where the followers break ties in favor of the leader, the problem can be formulated via mixed-integer linear programming techniques, which computational experiments show to scale quite well.



قيم البحث

اقرأ أيضاً

This paper aims at providing a global perspective on electromagnetic nonreciprocity and clarifying confusions that arose in the recent developments of the field. It provides a general definition of nonreciprocity and classifies nonreciprocal systems according to their linear time-invariant (LTI), linear time-variant (LTV) or nonlinear nonreciprocal natures. The theory of nonlinear systems is established on the foundation of the concepts of time reversal, time-reversal symmetry, time-reversal symmetry breaking and related Onsager- Casimir relations. Special attention is given to LTI systems, as the most common nonreciprocal systems, for which a generalized form of the Lorentz reciprocity theorem is derived. The delicate issue of loss in nonreciprocal systems is demystified and the so-called thermodynamics paradox is resolved from energy conservation considerations. The fundamental characteristics and applications of LTI, LTV and nonlinear nonreciprocal systems are overviewed with the help of pedagogical examples. Finally, asymmetric structures with fallacious nonreciprocal appearances are debunked.
Electromagnetically-induced-transparency (EIT) and Autler-Townes splitting (ATS) are two prominent examples of coherent interactions between optical fields and multilevel atoms. They have been observed in various physical systems involving atoms, mol ecules, meta-structures and plasmons. In recent years, there has been an increasing interest in the implementations of all-optical analogues of EIT and ATS via the interacting resonant modes of one or more optical microcavities. Despite the differences in their underlying physics, both EIT and ATS are quantified by the appearance of a transparency window in the absorption or transmission spectrum, which often leads to a confusion about its origin. While in EIT the transparency window is a result of Fano interference among different transition pathways, in ATS it is the result of strong field-driven interactions leading to the splitting of energy levels. Being able to tell objectively whether a transparency window observed in the spectrum is due to EIT or ATS is crucial for clarifying the physics involved and for practical applications. Here we report a systematic study of the pathways leading to EIT, Fano, and ATS, in systems of two coupled whispering-gallery-mode (WGM) microtoroidal resonators. Moreover, we report for the first time the application of the Akaike Information Criterion discerning between all-optical analogues of EIT and ATS, and clarifying the transition between them.
121 - Carl H. Gibson 2012
Turbulence is defined as an eddy-like state of fluid motion where the inertial-vortex forces of the eddies are larger than any other forces that tend to damp the eddies out. By this definition, turbulence always cascades from small scales (where the vorticity is created) to larger scales (where other forces dominate and the turbulence fossilizes). Fossil turbulence is any perturbation in a hydrophysical field produced by turbulence that persists after the fluid is no longer turbulent at the scale of the perturbation. Fossil turbulence patterns and fossil turbulence waves preserve and propagate information about previous turbulence to larger and smaller length scales. Big bang fossil turbulence patterns are identified in anisotropies of temperature detected by space telescopes in the cosmic microwave background. Direct numerical simulations of stratified shear flows and wakes show that turbulence and fossil turbulence interactions are recognizable and persistent.
110 - Jeffrey C. Jackson 2017
General acceptance of a mathematical proposition $P$ as a theorem requires convincing evidence that a proof of $P$ exists. But what constitutes convincing evidence? I will argue that, given the types of evidence that are currently accepted as convinc ing, it is inconsistent to deny similar acceptance to the evidence provided for the existence of proofs by certain randomized computations.
In this paper we introduce a qualitative decision and game theory based on belief (B) and desire (D) rules. We show that a group of agents acts as if it is maximizing achieved joint goals.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا