Hasil untuk "cs.GT"

Naoyuki Kamiyama

In this paper, we consider a matroid generalization of the stable matching problem. In particular, we consider the setting where preferences may contain ties. For this generalization, we propose a polynomial-time algorithm for the problem of checking the existence of a common independent set satisfying non-uniform stability, which is a common generalization of super-stability and strong stability.

Andrey Leonidov

A description of static equilibria in the noisy binary choice (Ising) game on complete and random graphs resulting from maximisation of the likelihood of system configurations is presented. An equivalence of such likelihood equilibria to the competitive Bayes-Nash quantal response expectation equilibria in the special case of consistent agents expectations is established. It is shown that the same likelihood equilibria are obtained by considering the system's partition function.

Mark Voorneveld

Fourier-Motzkin elimination, a standard method for solving systems of linear inequalities, leads to an elementary, short, and self-contained proof of von Neumann's minimax theorem.

Luis Sánchez-Fernández

I propose an alternative algorithm to compute the MMS voting rule. Instead of using linear programming, in this new algorithm the maximin support value of a committee is computed using a sequence of maximum flow problems.

Maximilian Fichtl

We study the problem of computing optimal prices for a version of the Product-Mix auction with budget constraints. In contrast to the ``standard'' Product-Mix auction, the objective is to maximize revenue instead of social welfare. We prove correctness of an algorithm proposed by Paul Klemperer and DotEcon which is sufficiently efficient in smaller markets.

Meziane Privat

To predict the behavior of a population game when time becomes very long, the process that characterizes the evolution of our game dynamics must be reversible. Known games satisfying this are 2 strategy games as well as potential games with an exponential protocol. We will try to extend the study of infinite horizons for what are called symetric strategy games.

Liad Nagi, Moriya Elgrabli

A comparison of four fair division algorithms performed on real data from the spliddit website. The comparison was made on the sum of agent's utilities, and the minimum utility for an agent in an allocation.

Vladimir Gurvich

We formulate a conjecture from graph theory that is equivalent to Nash-solvability of the finite two-person shortest path games with positive local costs. For the three-person games such conjecture fails.

Mahdi Takalloo, Changhyun Kwon

For single-commodity networks, the increase of the price of anarchy is bounded by a factor of $(1+ε)^p$ from above, when the travel demand is increased by a factor of $1+ε$ and the latency functions are polynomials of degree at most $p$. We show that the same upper bound holds for multi-commodity networks and provide a lower bound as well.

Haris Aziz

Fairness is becoming an increasingly important concern when designing markets, allocation procedures, and computer systems. I survey some recent developments in the field of multi-agent fair allocation.

Kanstantsin Pashkovich

We provide an algorithm for computing the nucleolus for an instance of a weighted voting game in pseudo-polynomial time. This resolves an open question posed by Elkind. et.al. 2007.

Jaroslaw Pykacz, Pawel Bytner, Piotr Frackiewicz

The problem of the existence of Berge equilibria in the sense of Zhukovskii in normal form finite games in pure and in mixed strategies is studied. The example of a three-player game that has Berge equilibrium neither in pure nor in mixed strategies is given.

Reshef Meir

Consider Plurality with random tie-breaking. This paper uses standard axiomatic extensions of preferences over elements to preferences over sets (Kelly, Gardenfors, Responsiveness) to characterize all better-replies of a voter under stochastic dominance.

Anisse Ismaili

In a multi-objective game, each agent individually evaluates each overall action-profile on multiple objectives. I generalize the price of anarchy to multi-objective games and provide a polynomial-time algorithm to assess it. This work asserts that policies on tobacco promote a higher economic efficiency.

Marcello Mamino

We prove that to find optimal positional strategies for stochastic mean payoff games when the value of every state of the game is known, in general, is as hard as solving such games tout court. This answers a question posed by Daniel Andersson and Peter Bro Miltersen.

Krzysztof Leśniak

We investigate an alternative concept of Nash equilibrium, m-equilibrium, which slightly resembles Harsanyi-Selten risk dominant equilibrium although it is a different notion. M-equilibria provide nontrivial solutions of normal form games as shown by comparison of the Prisoner's Dilemma with the Traveler's Dilemma. They are also resistant on the deep iterated elimination of dominated strategies.

Yannick Viossat

If a game has a unique Nash equilibrium, then this equilibrium is arguably the solution of the game from the refinement's literature point of view. However, it might be that for almost all initial conditions, all strategies in the support of this equilibrium are eliminated by the replicator dynamics and the best-reply dynamics.

Shahar Dobzinski, Hu Fu, Robert Kleinberg

This short note exhibits a truthful-in-expectation $O(\frac {\log m} {\log \log m})$-approximation mechanism for combinatorial auctions with subadditive bidders that uses polynomial communication.

Peter Bro Miltersen

It is NP-hard to decide if a given pure-strategy Nash equilibrium of a given three-player game in strategic form with integer payoffs is trembling hand perfect.

Thierry Cachat, Igor Walukiewicz

We prove an n-EXPTIME lower bound for the problem of deciding the winner in a reachability game on Higher Order Pushdown Automata (HPDA) of level n. This bound matches the known upper bound for parity games on HPDA. As a consequence the mu-calculus model checking over graphs given by n-HPDA is n-EXPTIME complete.