Source author record

Maria Polukarov

Maria Polukarov appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Computer Science and Game Theory Data Structures and Algorithms Multiagent Systems Artificial Intelligence Computational Complexity physics.soc-ph Populations and Evolution q-fin.EC q-fin.ST

Catalog footprint

What is connected

7works

9topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

preprint2016arXiv

A new structural stochastic volatility model of asset pricing and its stylized facts

Building on a prominent agent-based model, we present a new structural stochastic volatility asset pricing model of fundamentalists vs. chartists where the prices are determined based on excess demand. Specifically, this allows for modelling stochastic interactions between agents, based on a herding process corrected by a price misalignment, and incorporating strong noise components in the agents' demand. The model's parameters are estimated using the method of simulated moments, where the moments reflect the basic properties of the daily returns of a stock market index. In addition, for the first time we apply a (parametric) bootstrap method in a setting where the switching between strategies is modelled using a discrete choice approach. As we demonstrate, the resulting dynamics replicate a rich set of the stylized facts of the daily financial data including: heavy tails, volatility clustering, long memory in absolute returns, as well as the absence of autocorrelation in raw returns, volatility-volume correlations, aggregate Gaussianity, concave price impact and extreme price events.

preprint2016arXiv

New Results on Equilibria in Strategic Candidacy

We consider a voting setting where candidates have preferences about the outcome of the election and are free to join or leave the election. The corresponding candidacy game, where candidates choose strategically to participate or not, has been studied %initially by Dutta et al., who showed that no non-dictatorial voting procedure satisfying unanimity is candidacy-strategyproof, that is, is such that the joint action where all candidates enter the election is always a pure strategy Nash equilibrium. Dutta et al. also showed that for some voting tree procedures, there are candidacy games with no pure Nash equilibria, and that for the rule that outputs the sophisticated winner of voting by successive elimination, all games have a pure Nash equilibrium. No results were known about other voting rules. Here we prove several such results. For four candidates, the message is, roughly, that most scoring rules (with the exception of Borda) do not guarantee the existence of a pure Nash equilibrium but that Condorcet-consistent rules, for an odd number of voters, do. For five candidates, most rules we study no longer have this guarantee. Finally, we identify one prominent rule that guarantees the existence of a pure Nash equilibrium for any number of candidates (and for an odd number of voters): the Copeland rule. We also show that under mild assumptions on the voting rule, the existence of strong equilibria cannot be guaranteed.

preprint2015arXiv

Cooperative Equilibrium beyond Social Dilemmas: Pareto Solvable Games

A recently introduced concept of "cooperative equilibrium", based on the assumption that players have a natural attitude to cooperation, has been proven a powerful tool in predicting human behaviour in social dilemmas. In this paper, we extend this idea to more general game models, termed "Pareto solvable" games, which in particular include the Nash Bargaining Problem and the Ultimatum Game. We show that games in this class possess a unique pure cooperative equilibrium. Furthermore, for the Ultimatum Game, this notion appears to be strongly correlated with a suitably defined variant of the Dictator Game. We support this observation with the results of a behavioural experiment conducted using Amazon Mechanical Turk, which demonstrates that our approach allows for making statistically precise predictions of average behaviour in such settings.

preprint2014arXiv

Coalition Structure Generation over Graphs

We give the analysis of the computational complexity of coalition structure generation over graphs. Given an undirected graph G = (N,E) and a valuation function v : P(N) \to R over the subsets of nodes, the problem is to find a partition of N into connected subsets, that maximises the sum of the components values. This problem is generally NP-complete; in particular, it is hard for a defined class of valuation functions which are independent of disconnected members - that is, two nodes have no effect on each other's marginal contribution to their vertex separator. Nonetheless, for all such functions we provide bounds on the complexity of coalition structure generation over general and minor-free graphs. Our proof is constructive and yields algorithms for solving corresponding instances of the problem. Furthermore, we derive linear time bounds for graphs of bounded treewidth. However, as we show, the problem remains NP-complete for planar graphs, and hence, for any K_k minor free graphs where k \geq 5. Moreover, a 3-SAT problem with m clauses can be represented by a coalition structure generation problem over a planar graph with O(m^2) nodes. Importantly, our hardness result holds for a particular subclass of valuation functions, termed edge sum, where the value of each subset of nodes is simply determined by the sum of given weights of the edges in the induced subgraph.

preprint2014arXiv

Cooperative Games with Overlapping Coalitions

In the usual models of cooperative game theory, the outcome of a coalition formation process is either the grand coalition or a coalition structure that consists of disjoint coalitions. However, in many domains where coalitions are associated with tasks, an agent may be involved in executing more than one task, and thus may distribute his resources among several coalitions. To tackle such scenarios, we introduce a model for cooperative games with overlapping coalitions--or overlapping coalition formation (OCF) games. We then explore the issue of stability in this setting. In particular, we introduce a notion of the core, which generalizes the corresponding notion in the traditional (non-overlapping) scenario. Then, under some quite general conditions, we characterize the elements of the core, and show that any element of the core maximizes the social welfare. We also introduce a concept of balancedness for overlapping coalitional games, and use it to characterize coalition structures that can be extended to elements of the core. Finally, we generalize the notion of convexity to our setting, and show that under some natural assumptions convex games have a non-empty core. Moreover, we introduce two alternative notions of stability in OCF that allow a wider range of deviations, and explore the relationships among the corresponding definitions of the core, as well as the classic (non-overlapping) core and the Aubin core. We illustrate the general properties of the three cores, and also study them from a computational perspective, thus obtaining additional insights into their fundamental structure.

preprint2011arXiv

Graph Coalition Structure Generation

We give the first analysis of the computational complexity of {\it coalition structure generation over graphs}. Given an undirected graph $G=(N,E)$ and a valuation function $v:2^N\rightarrow\RR$ over the subsets of nodes, the problem is to find a partition of $N$ into connected subsets, that maximises the sum of the components' values. This problem is generally NP--complete; in particular, it is hard for a defined class of valuation functions which are {\it independent of disconnected members}---that is, two nodes have no effect on each other's marginal contribution to their vertex separator. Nonetheless, for all such functions we provide bounds on the complexity of coalition structure generation over general and minor free graphs. Our proof is constructive and yields algorithms for solving corresponding instances of the problem. Furthermore, we derive polynomial time bounds for acyclic, $K_{2,3}$ and $K_4$ minor free graphs. However, as we show, the problem remains NP--complete for planar graphs, and hence, for any $K_k$ minor free graphs where $k\geq 5$. Moreover, our hardness result holds for a particular subclass of valuation functions, termed {\it edge sum}, where the value of each subset of nodes is simply determined by the sum of given weights of the edges in the induced subgraph.

preprint2010arXiv

Considerate Equilibrium

We consider the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent approach termed partition equilibrium. We assume that players in a strategic game are embedded in a social network, and there are coordination constraints that restrict the potential coalitions that can jointly deviate in the game to the set of cliques in the social network. In addition, players act in a "considerate" fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors. We study the properties of such considerate equilibria in application to the class of resource selection games (RSG). Our main result proves existence of a considerate equilibrium in all symmetric RSG with strictly increasing delays, for any social network among the players. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for the standard RSG showing that there exists a state that is stable against selfish and considerate behavior simultaneously. In addition, we show results on convergence of considerate dynamics.