Researcher profile

Akaki Mamageishvili

Akaki Mamageishvili contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate

Computer Science and Game Theory Data Structures and Algorithms econ.TH

Trust snapshot

Quick read

Trust 21 - Emerging

6works

0followers

3topics

4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

On-Chain Auctions with Deposits

Second-price auctions with deposits are frequently used in blockchain environments. An auction takes place on-chain: bidders deposit an amount that fully covers their bid (but possibly exceeds it) in a smart contract. The deposit is used as insurance against bidders not honoring their bid if they win. The deposit, but not the bid, is publicly observed during the bidding phase of the auction. The visibility of deposits can fundamentally change the strategic structure of the auction if bidding happens sequentially: Bidding is costly since deposit are costly to make. Thus, deposits can be used as a costly signal for a high valuation. This is the source of multiple inefficiencies: To engage in costly signalling, a bidder who bids first and has a high valuation will generally over-deposit in equilibrium, i.e.~deposit more than he will bid. If high valuations are likely there can, moreover, be entry deterrence through high deposits: a bidder who bids first can deter subsequent bidders from entering the auction. Pooling can happen in equilibrium, where bidders of different valuations deposit the same amount. The auction fails to allocate the item to the bidder with the highest valuation.

preprint2020arXiv

Sequential Solutions in Machine Scheduling Games

We consider the classical machine scheduling, where $n$ jobs need to be scheduled on $m$ machines, and where job $j$ scheduled on machine $i$ contributes $p_{i,j}\in \mathbb{R}$ to the load of machine $i$, with the goal of minimizing the makespan, i.e., the maximum load of any machine in the schedule. We study inefficiency of schedules that are obtained when jobs arrive sequentially one by one, and the jobs choose themselves the machine on which they will be scheduled, aiming at being scheduled on a machine with small load. We measure the inefficiency of a schedule as the ratio of the makespan obtained in the worst-case equilibrium schedule, and of the optimum makespan. This ratio is known as the \emph{sequential price of anarchy}. We also introduce two alternative inefficiency measures, which allow for a favorable choice of the order in which the jobs make their decisions. As our first result, we disprove the conjecture of Hassin and Yovel claiming that the sequential price of anarchy for $m=2$ machines is at most 3. We show that the sequential price of anarchy grows at least linearly with the number $n$ of players, i.e., we show that $SPoA = Ω(n)$. Furthermore, we show that there exists an order of the jobs, resulting in makespan that is at most linearly larger than the optimum makespan. To the end, we show that if an authority can change the order of the jobs adaptively to the decisions made by the jobs so far (but cannot influence the decisions of the jobs), then there exists an adaptive ordering in which the jobs end up in an optimum schedule.

preprint2015arXiv

Multicast Network Design Game on a Ring

In this paper we study quality measures of different solution concepts for the multicast network design game on a ring topology. We recall from the literature a lower bound of 4/3 and prove a matching upper bound for the price of stability, which is the ratio of the social costs of a best Nash equilibrium and of a general optimum. Therefore, we answer an open question posed by Fanelli et al. in [12]. We prove an upper bound of 2 for the ratio of the costs of a potential optimizer and of an optimum, provide a construction of a lower bound, and give a computer-assisted argument that it reaches $2$ for any precision. We then turn our attention to players arriving one by one and playing myopically their best response. We provide matching lower and upper bounds of 2 for the myopic sequential price of anarchy (achieved for a worst-case order of the arrival of the players). We then initiate the study of myopic sequential price of stability and for the multicast game on the ring we construct a lower bound of 4/3, and provide an upper bound of 26/19. To the end, we conjecture and argue that the right answer is 4/3.

preprint2015arXiv

Tighter Bounds on the Inefficiency Ratio of Stable Equilibria in Load Balancing Games

In this paper we study the inefficiency ratio of stable equilibria in load balancing games introduced by Asadpour and Saberi [3]. We prove tighter lower and upper bounds of 7/6 and 4/3, respectively. This improves over the best known bounds in problem (19/18 and 3/2, respectively). Equivalently, the results apply to the question of how well the optimum for the $L_2$ -norm can approximate the $L_{\infty}$-norm (makespan) in identical machines scheduling.

preprint2014arXiv

An $H_{n/2}$ Upper Bound on the Price of Stability of Undirected Network Design Games

In the network design game with $n$ players, every player chooses a path in an edge-weighted graph to connect her pair of terminals, sharing costs of the edges on her path with all other players fairly. We study the price of stability of the game, i.e., the ratio of the social costs of a best Nash equilibrium (with respect to the social cost) and of an optimal play. It has been shown that the price of stability of any network design game is at most $H_n$, the $n$-th harmonic number. This bound is tight for directed graphs. For undirected graphs, the situation is dramatically different, and tight bounds are not known. It has only recently been shown that the price of stability is at most $H_n \left(1-\frac{1}{Θ(n^4)} \right)$, while the worst-case known example has price of stability around 2.25. In this paper we improve the upper bound considerably by showing that the price of stability is at most $H_{n/2} + ε$ for any $ε$ starting from some suitable $n \geq n(ε)$.

preprint2013arXiv

Tree Nash Equilibria in the Network Creation Game

In the network creation game with n vertices, every vertex (a player) buys a set of adjacent edges, each at a fixed amount α > 0. It has been conjectured that for α >= n, every Nash equilibrium is a tree, and has been confirmed for every α >= 273n. We improve upon this bound and show that this is true for every α >= 65n. To show this, we provide new and improved results on the local structure of Nash equilibria. Technically, we show that if there is a cycle in a Nash equilibrium, then α < 65n. Proving this, we only consider relatively simple strategy changes of the players involved in the cycle. We further show that this simple approach cannot be used to show the desired upper bound α < n (for which a cycle may exist), but conjecture that a slightly worse bound α < 1.3n can be achieved with this approach. Towards this conjecture, we show that if a Nash equilibrium has a cycle of length at most 10, then indeed α < 1.3n. We further provide experimental evidence suggesting that when the girth of a Nash equilibrium is increasing, the upper bound on α obtained by the simple strategy changes is not increasing. To the end, we investigate the approach for a coalitional variant of Nash equilibrium, where coalitions of two players cannot collectively improve, and show that if α >= 41n, then every such Nash equilibrium is a tree.