Found 2 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

We consider multiplayer games in which the players fall in two teams of size k, with payoffs equal within, and of opposite sign across, the two teams. In the classical case of k=1, such zero-sum games possess a unique value, independent of order of play, due to the von Neumann minimax theorem. However, this fails for all k>1; we can measure this failure by a duality gap, which quantifies the benefit of being the team to commit last to its strategy. In our main result we show that the gap equals 2(1-2^{1-k}) for m=2 and 2(1-\m^{-(1-o(1))k}) for m>2, with m being the size of the action space of each player.
At a finer level, the cost to a team of individual players acting independently while the opposition employs joint randomness is 1-2^{1-k} for k=2, and 1-\m^{-(1-o(1))k} for m>2.
This class of multiplayer games, apart from being a natural bridge between two-player zero-sum games and general multiplayer games, is motivated from Biology (the weak selection model of evolution) and Economics (players with shared utility but poor coordination).

Leonard Schulman and Umesh V. Vazirani. The Duality Gap for Two-Team Zero-Sum Games. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 56:1-56:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{schulman_et_al:LIPIcs.ITCS.2017.56, author = {Schulman, Leonard and Vazirani, Umesh V.}, title = {{The Duality Gap for Two-Team Zero-Sum Games}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {56:1--56:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.56}, URN = {urn:nbn:de:0030-drops-81429}, doi = {10.4230/LIPIcs.ITCS.2017.56}, annote = {Keywords: multi-player games, duality gap, zero-sum games, evolution} }

Document

**Published in:** LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)

We study the decision theory of a maximally risk-averse investor ---
one whose objective, in the face of stochastic uncertainties, is to
minimize the probability of ever going broke. With a view to
developing the mathematical basics of such a theory, we start with a
very simple model and obtain the following results: a characterization
of best play by investors; an explanation of why poor and rich players
may have different best strategies; an explanation of why
expectation-maximization is not necessarily the best strategy even for
rich players. For computation of optimal play, we show how to apply
the Value Iteration method, and prove a bound on its convergence
rate.

Noam Berger, Nevin Kapur, Leonard Schulman, and Vijay Vazirani. Solvency Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 61-72, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.FSTTCS.2008.1741, author = {Berger, Noam and Kapur, Nevin and Schulman, Leonard and Vazirani, Vijay}, title = {{Solvency Games}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {61--72}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1741}, URN = {urn:nbn:de:0030-drops-17419}, doi = {10.4230/LIPIcs.FSTTCS.2008.1741}, annote = {Keywords: Decision making under uncertainity, multi-arm bandit problems, game theory} }

Document

Invited Talk

**Published in:** LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Data, for the most part, is used in order to inform potential interventions: whether by individuals (decisions about education or employment), government (public health, environmental regulation, infrastructure investment) or business. The most common data analysis tools are those which identify correlations among variables - think of regression or of clustering. However, some famous paradoxes illustrate the futility of relying on correlations alone without a model for the causal relationships between variables.
Historically, causality has been teased apart from correlation through controlled experiments. But for a variety of reasons - cost, ethical constraints, or uniqueness of the system - we must often make do with passive observation alone. A theory based upon directed graphical models has been developed over the past three decades, which in some situations, enables statistically defensible causal inference even in the absence of controlled experiments.
Yet "some situations" is rather fewer than one would like. This limitation spurs a range of research questions. In this talk I will describe a couple of causality paradoxes along with how they are captured within the graphical model framework; this will lead naturally toward some of the computational and information-theoretic questions which arise in the theory.

Leonard J. Schulman. Computational and Information-Theoretic Questions from Causal Inference (Invited Talk). In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, p. 3:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{schulman:LIPIcs.FSTTCS.2023.3, author = {Schulman, Leonard J.}, title = {{Computational and Information-Theoretic Questions from Causal Inference}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.3}, URN = {urn:nbn:de:0030-drops-193769}, doi = {10.4230/LIPIcs.FSTTCS.2023.3}, annote = {Keywords: Causal Inference, Bayesian Networks} }

Document

**Published in:** LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

We analyze a stylized model of co-evolution between any two purely competing species (e.g., host and parasite), both sexually reproducing. Similarly to a recent model [Livnat et al. FOCS'14] the fitness of an individual depends on whether the truth assignments on n variables that reproduce through recombination satisfy a particular Boolean function. Whereas in the original model a satisfying assignment always confers a small evolutionary advantage, in our model the two species are in an evolutionary race with the parasite enjoying the advantage if the value of its Boolean function matches its host, and the host wishing to mismatch its parasite. Surprisingly, this model makes a simple and robust behavioral prediction. The typical system behavior is periodic. These cycles stay bounded away from the boundary and thus, learning-dynamics competition between sexual species can provide an explanation for genetic diversity. This explanation is due solely to the natural selection process. No mutations, environmental changes, etc., need be invoked.
The game played at the gene level may have many Nash equilibria with widely diverse fitness levels. Nevertheless, sexual evolution leads to gene coordination that implements an optimal strategy, i.e., an optimal population mixture, at the species level. Namely, the play of the many "selfish genes" implements a time-averaged correlated equilibrium where the average fitness of each species is exactly equal to its value in the two species zero-sum competition.
Our analysis combines tools from game theory, dynamical systems and Boolean functions to establish a novel class of conservative dynamical systems.

Georgios Piliouras and Leonard J. Schulman. Learning Dynamics and the Co-Evolution of Competing Sexual Species. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 59:1-59:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{piliouras_et_al:LIPIcs.ITCS.2018.59, author = {Piliouras, Georgios and Schulman, Leonard J.}, title = {{Learning Dynamics and the Co-Evolution of Competing Sexual Species}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {59:1--59:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.59}, URN = {urn:nbn:de:0030-drops-83637}, doi = {10.4230/LIPIcs.ITCS.2018.59}, annote = {Keywords: Dynamical Systems, Potential Game, Team Zero-Sum Game, Boolean Functions, Replicator Dynamics} }

Document

**Published in:** LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

We present a simple and natural non-pricing mechanism for allocating divisible goods among strategic agents having lexicographic preferences. Our mechanism has favorable properties of strategy-proofness (incentive compatibility). In addition (and even when extended to the case of Leontief bundles) it enjoys Pareto efficiency, envy-freeness, and time efficiency.

Leonard J. Schulman and Vijay V. Vazirani. Allocation of Divisible Goods Under Lexicographic Preferences. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 543-559, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{schulman_et_al:LIPIcs.FSTTCS.2015.543, author = {Schulman, Leonard J. and Vazirani, Vijay V.}, title = {{Allocation of Divisible Goods Under Lexicographic Preferences}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {543--559}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.543}, URN = {urn:nbn:de:0030-drops-56279}, doi = {10.4230/LIPIcs.FSTTCS.2015.543}, annote = {Keywords: Mechanism design, lexicographic preferences, strategyproof, Pareto optimal, incentive compatible} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail