We study a network formation game where players wish to send traffic to other players. Players can be seen as nodes of an undirected graph whose edges are defined by contracts between the corresponding players. Each player can contract bilaterally with others to form bidirectional links or break unilaterally contracts to eliminate the corresponding links. Our model is an extension of the traffic routing model considered in Arcaute, E., Johari, R., Mannor, S., (IEEE Trans. Automat. Contr. 54(8), 1765–1778 2009) in which we do not require the traffic to be uniform and all-to-all. Player i specifies the amount of traffic tij = 0 that wants to send to player j. Our notion of stability is the network pairwise Nash stability, when no node wishes to deviate unilaterally and no pair of nodes can obtain benefit from deviating bilaterally. We show a characterization of the topologies that are pairwise Nash stable for a given traffic matrix. We prove that the best response problem is NP-hard and devise a myopic dynamics so that the deviation of the active node can be computed in polynomial time. We show the convergence of the dynamics to pairwise Nash configurations, when the contracting functions are anti-symmetric and affine, and that the expected convergence time is polynomial in the number of nodes when the node activation process is uniform.
The Generalized Second Price (GSP) auction used typically to model sponsored search auctions does not include the notion of budget constraints, which is present in practice. Motivated by this, we introduce the different variants of GSP auctions that take budgets into account in natural ways. We examine their stability by focusing on the existence of Nash equilibria and envy-free assignments. We highlight the differences between these mechanisms and find that only some of them exhibit both notions of stability. This shows the importance of carefully picking the right mechanism to ensure stable outcomes in the presence of budgets.
Alt, H.; Arkin, E. M.; Efrat, A.; Hart, G.; Hurtado, F.; Kostitsyna, I.; Kröller, A.; Mitchell, J. S. B.; Polishchuk, V. Theory of computing systems Vol. 54, num. 4, p. 689-714 DOI: 10.1007/s00224-013-9493-9 Data de publicació: 2014-05-01 Article en revista
We show how to compute the smallest rectangle that can enclose any polygon, from a given set of polygons, in nearly linear time; we also present a PTAS for the problem, as well as a linear-time algorithm for the case when the polygons are rectangles themselves. We prove that finding a smallest convex polygon that encloses any of the given polygons is NP-hard, and give a PTAS for minimizing the perimeter of the convex enclosure. We also give efficient algorithms to find the smallest rectangle simultaneously enclosing a given pair of convex polygons.
We analyze the complexity of equilibria problems for a class of strategic zero-sum games, called angel-daemon games. Those games were introduced to asses the performance of the execution of a web orchestration on a moderate faulty or under stress environment. Angel-daemon games are a natural example of zero-sum games whose representation is naturally succinct. We show that the problems of deciding the existence of a pure Nash equilibrium or of a dominant strategy for a given player are (Formula presented.)-complete. Furthermore, computing the value of an angel-daemon game is EXP-complete. Thus, our results match the already known classification of the corresponding problems for the generic families of succinctly represented games with exponential number of actions.
Chattopadhyay, A.; Gavaldà, R.; Arnsfelt Hansen, K.; Thérien, D. Theory of computing systems Vol. 55, num. 2, p. 404-420 DOI: 10.1007/s00224-013-9488-6 Data de publicació: 2013-07-01 Article en revista
Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC0. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model.
In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.
Boolean functions that have constant degree polynomial representation over a fixed finite ring form a natural and strict subclass of the complexity class ACC0. They are also precisely the functions computable efficiently by programs over fixed and finite nilpotent groups. This class is not known to be learnable in any reasonable learning model. In this paper, we provide a deterministic polynomial time algorithm for learning Boolean functions represented by polynomials of constant degree over arbitrary finite rings from membership queries, with the additional constraint that each variable in the target polynomial appears in a constant number of monomials. Our algorithm extends to superconstant but low degree polynomials and still runs in quasipolynomial time.
Blesa, M.; Calzada, D.; Fernández López, A.; López, L.; Martínez, A.; Santos, A.; Serna, M.; Thraves, C. Theory of computing systems Vol. 44, num. 3, p. 304-331 DOI: 10.1007/s00224-007-9046-1 Data de publicació: 2009-04 Article en revista
This paper analyzes the performance of vector-dominated regions of code in numerical and multimedia applications in a superscalar + vector architecture and compares it with an eight-way superscalar processor. The ability to split a program’s execution into scalar and vector regions allows us to show that (1) as expected, the vector unit is much better than the wide-issue superscalar at executing the vector-dominated regions of the code; (2) on the scalar regions, the eight-way superscalar, although better than a four-way superscalar, is clearly not worth the extra complexity in terms of extra transistors and potential cycle-time limitations. Overall, the vector-enhanced superscalar is from 6% to 303% better than an eight-way superscalar. We also present detailed data on the performance of the memory system, which is usually the key limiting factor when running numerical and multi-\break media applications. We evaluate two additional cache designs that try to alleviate problems created by non-unit stride memory references.