Hasil untuk "cs.GT"

Pierre Ohlmann

We propose a new deterministic symmetric recursive algorithm for solving mean-payoff games.

Keita Kuwahara

We propose an $O(n^2)$-time algorithm to determine whether a given matching is efficient in the roommates problem.

Vladimir Yankovskiy

In this work, we consider properties of VCG and GSP positional auctions in queues. The work is a continuation of "Position Auctions for Sponsored Search in Marketplaces" by the same author.

Jannik Peters

In this note, we uncover three connections between the metric distortion problem and voting methods and axioms from the social choice literature.

Constantine Caramanis, Paul Dütting, Matthew Faw et al.

We study single-sample prophet inequalities (SSPIs), i.e., prophet inequalities where only a single sample from each prior distribution is available. Besides a direct, and optimal, SSPI for the basic single choice problem [Rubinstein et al., 2020], most existing SSPI results were obtained via an elegant, but inherently lossy, reduction to order-oblivious secretary (OOS) policies [Azar et al., 2014]. Motivated by this discrepancy, we develop an intuitive and versatile greedy-based technique that yields SSPIs directly rather than through the reduction to OOSs. Our results can be seen as generalizing and unifying a number of existing results in the area of prophet and secretary problems. Our algorithms significantly improve on the competitive guarantees for a number of interesting scenarios (including general matching with edge arrivals, bipartite matching with vertex arrivals, and certain matroids), and capture new settings (such as budget additive combinatorial auctions). Complementing our algorithmic results, we also consider mechanism design variants. Finally, we analyze the power and limitations of different SSPI approaches by providing a partial converse to the reduction from SSPI to OOS given by Azar et al.

Maximilian Fichtl

In this note we prove that the class of valuation functions representable via integral assignment messages is a proper subset of strong substitutes valuations. Thus, there are strong substitutes valuations not expressible via assignment messages.

Fred Batty

This paper presents an Elo-based rating system for programming contests, specifically Topcoder's Single Round Matches (SRMs). We introduce a logarithmic rank-based performance metric that allows single-round, multi-player contest results to be incorporated into an Elo-style continuous rating framework. Model parameters and adjustment factors are calibrated empirically by minimizing absolute prediction error over historical data, accounting for experience level, initial ratings, and competition characteristics. The resulting system demonstrates improved rank predictions and rating progressions consistent with natural skill development over player careers.

Benjamin Golub

This note, suitable for a lecture in an advanced undergraduate or basic graduate course on the economic theory of networks, exposits basic ideas of linear best-response games and their equilibria.

Kanstantsin Pashkovich

In this note, we show that for every simple game with n players the critical threshold value is at most n/4. This verifies the conjecture of Freixas and Kurz.

Guillaume Chèze

In this note we study how to share a good between n players in a simple and equitable way. We give a short proof for the existence of such fair divisions.

Liad Blumrosen, Shahar Dobzinski

We study the bilateral trade problem: one seller, one buyer and a single, indivisible item for sale. It is well known that there is no fully-efficient and incentive compatible mechanism for this problem that maintains a balanced budget. We design simple and robust mechanisms that obtain approximate efficiency with these properties. We show that even minimal use of statistical data can yield good approximation results. Finally, we demonstrate how a mechanism for this simple bilateral-trade problem can be used as a "black-box" for constructing mechanisms in more general environments.

Christopher P. Chambers, Federico Echenique

We prove that combinatorial demand functions are characterized by two properties: continuity and the law of demand.

Guillaume Chèze

Consider the framework of topological aggregation introduced by Chichilnisky (1980). We prove that in this framework the Twin Paradox and the No Show Paradox cannot be avoided. Anonymity and unanimity are not needed to obtain these results.

Federico Echenique

This paper shows that it is computationally hard to decide (or test) if a consumption data set is consistent with separable preferences.

Marco Dall'Aglio, Camilla Di Luca

We consider upper and lower bounds for maxmin allocations of a completely divisible good in both competitive and cooperative strategic contexts. We then derive a subgradient algorithm to compute the exact value up to any fixed degree of precision.

Michael J. Collins

We consider the use of cost sharing in the Aspnes model of network inoculation, showing that this can improve the cost of the optimal equilibrium by a factor of $O(\sqrt{n})$ in a network of $n$ nodes.

Shang-Guan H. Wu

In this note, we argue that there is a bug in [Tirole, J., "Hierarchies and bureaucracies: On the role of collusion in organizations," {\em Journal of Law, Economics and Organization}, vol.2, 181-214, 1986].

Yashodhan Kanoria, Mohsen Bayati, Christian Borgs et al.

Bargaining networks model the behavior of a set of players that need to reach pairwise agreements for making profits. Nash bargaining solutions are special outcomes of such games that are both stable and balanced. Kleinberg and Tardos proved a sharp algorithmic characterization of such outcomes, but left open the problem of how the actual bargaining process converges to them. A partial answer was provided by Azar et al. who proposed a distributed algorithm for constructing Nash bargaining solutions, but without polynomial bounds on its convergence rate. In this paper, we introduce a simple and natural model for this process, and study its convergence rate to Nash bargaining solutions. At each time step, each player proposes a deal to each of her neighbors. The proposal consists of a share of the potential profit in case of agreement. The share is chosen to be balanced in Nash's sense as far as this is feasible (with respect to the current best alternatives for both players). We prove that, whenever the Nash bargaining solution is unique (and satisfies a positive gap condition) this dynamics converges to it in polynomial time. Our analysis is based on an approximate decoupling phenomenon between the dynamics on different substructures of the network. This approach may be of general interest for the analysis of local algorithms on networks.

Riccardo Alberti

This paper has been withdrawn by the author due to a crucial error in the submission action.

Pierre Lescanne

In order to better understand reasoning involved in analyzing infinite games in extensive form, we performed experiments in the proof assistant Coq that are reported here.