Economics

Permanent URI for this collectionhttps://hdl.handle.net/10679/316

Browse

Browsing by Subject "Algorithmic game theory"

Filter results by typing the first few letters
Now showing 1 - 2 of 2
  • Thumbnail Image
    ArticlePublicationOpen Access
    On approximate Nash equilibria of the two-source connection game
    (TÜBİTAK, 2022) Çaşkurlu, B.; Açikalin, U. U.; Kizilkaya, F. E.; Ekici, Özgün; Economics; EKİCİ, Özgün
    The arbitrary-sharing connection game is prominent in the network formation game literature [1]. An undirected graph with positive edge weights is given, where the weight of an edge is the cost of building it. An edge is built if agents contribute a sufficient amount for its construction. For agent i, the goal is to contribute the least possible amount while assuring that the source node si is connected to the terminal node ti. In this paper, we study the special case of this game in which there are only two source nodes. In this setting, we prove that there exists a 2-approximate Nash equilibrium that is socially optimal. We also consider the further special case in which there are no auxiliary nodes (i.e., every node is a terminal or source node). In this further special case, we show that there exists a 3/2 -approximate Nash equilibrium that is socially optimal. Moreover, we show that it is computable in polynomial time.
  • Thumbnail Image
    ArticlePublicationOpen Access
    On efficient computation of equilibrium under social coalition structures
    (TÜBİTAK) Caskurlu, B.; Ekici, Özgür; Kizilkaya, F. E.; Economics; EKİCİ, Özgün
    In game-theoretic settings the key notion of analysis is an equilibrium, which is a profile of agent strategies such that no viable coalition of agents can improve upon their coalitional welfare by jointly changing their strategies. A Nash equilibrium, where viable coalitions are only singletons, and a super strong equilibrium, where every coalition is deemed viable, are two extreme scenarios in regard to coalition formation. A recent trend in the literature is to consider equilibrium notions that allow for coalition formation in between these two extremes and which are suitable to model social coalition structures that arise in various real-life settings. The recent literature considered the question on the existence of equilibria under social coalition structures mainly in Resource Selection Games (RSGs), due to the simplicity of this game form and its wide range of application domains. We take the question on the existence of equilibria under social coalition structures from the perspective of computational complexity theory. We study the problem of deciding the existence of an equilibrium in RSGs with respect to a given social coalition structure. For an arbitrary coalition structure, we show that it is computationally intractable to decide whether an equilibrium exists even in very restricted settings of RSGs. In certain settings where an equilibrium is guaranteed to exist we give polynomial-time algorithms to find an equilibrium.