Computer Science and Game Theory

Date: Fri, 21 Jun 2024 | Total: 14

#1 Strategy-proof Selling: a Geometric Approach [PDF] [Copy] [Kimi]

Author: Mridu Prabal Goswami

We consider one buyer and one seller. For a bundle $(t,q)\in [0,\infty[\times [0,1]=\mathbb{Z}$, $q$ either refers to the wining probability of an object or a share of a good, and $t$ denotes the payment that the buyer makes. We define classical and restricted classical preferences of the buyer on $\mathbb{Z}$; they incorporate quasilinear, non-quasilinear, risk averse preferences with multidimensional pay-off relevant parameters. We define rich single-crossing subsets of the two classes, and characterize strategy-proof mechanisms by using monotonicity of the mechanisms and continuity of the indirect preference correspondences. We also provide a computationally tractable optimization program to compute the optimal mechanism. We do not use revenue equivalence and virtual valuations as tools in our proofs. Our proof techniques bring out the geometric interaction between the single-crossing property and the positions of bundles $(t,q)$s. Our proofs are simple and provide computationally tractable optimization program to compute the optimal mechanism. The extension of the optimization program to the $n-$ buyer environment is immediate.

Subject: Theoretical Economics

Publish: 2024-06-18 05:15:11 UTC

#2 The Surprising Benefits of Base Rate Neglect in Robust Aggregation [PDF] [Copy] [Kimi]

Authors: Yuqing Kong ; Shu Wang ; Ying Wang

Robust aggregation integrates predictions from multiple experts without knowledge of the experts' information structures. Prior work assumes experts are Bayesian, providing predictions as perfect posteriors based on their signals. However, real-world experts often deviate systematically from Bayesian reasoning. Our work considers experts who tend to ignore the base rate. We find that a certain degree of base rate neglect helps with robust forecast aggregation. Specifically, we consider a forecast aggregation problem with two experts who each predict a binary world state after observing private signals. Unlike previous work, we model experts exhibiting base rate neglect, where they incorporate the base rate information to degree $\lambda\in[0,1]$, with $\lambda=0$ indicating complete ignorance and $\lambda=1$ perfect Bayesian updating. To evaluate aggregators' performance, we adopt Arieli et al. (2018)'s worst-case regret model, which measures the maximum regret across the set of considered information structures compared to an omniscient benchmark. Our results reveal the surprising V-shape of regret as a function of $\lambda$. That is, predictions with an intermediate incorporating degree of base rate $\lambda<1$ can counter-intuitively lead to lower regret than perfect Bayesian posteriors with $\lambda=1$. We additionally propose a new aggregator with low regret robust to unknown $\lambda$. Finally, we conduct an empirical study to test the base rate neglect model and evaluate the performance of various aggregators.

Subjects: Machine Learning ; Computer Science and Game Theory

Publish: 2024-06-19 12:20:29 UTC

#3 Nicer Than Humans: How do Large Language Models Behave in the Prisoner's Dilemma? [PDF] [Copy] [Kimi]

Authors: Nicoló Fontana ; Francesco Pierri ; Luca Maria Aiello

The behavior of Large Language Models (LLMs) as artificial social agents is largely unexplored, and we still lack extensive evidence of how these agents react to simple social stimuli. Testing the behavior of AI agents in classic Game Theory experiments provides a promising theoretical framework for evaluating the norms and values of these agents in archetypal social situations. In this work, we investigate the cooperative behavior of Llama2 when playing the Iterated Prisoner's Dilemma against random adversaries displaying various levels of hostility. We introduce a systematic methodology to evaluate an LLM's comprehension of the game's rules and its capability to parse historical gameplay logs for decision-making. We conducted simulations of games lasting for 100 rounds, and analyzed the LLM's decisions in terms of dimensions defined in behavioral economics literature. We find that Llama2 tends not to initiate defection but it adopts a cautious approach towards cooperation, sharply shifting towards a behavior that is both forgiving and non-retaliatory only when the opponent reduces its rate of defection below 30%. In comparison to prior research on human participants, Llama2 exhibits a greater inclination towards cooperative behavior. Our systematic approach to the study of LLMs in game theoretical scenarios is a step towards using these simulations to inform practices of LLM auditing and alignment.

Subjects: Computers and Society ; Artificial Intelligence ; Computer Science and Game Theory ; Physics and Society

Publish: 2024-06-19 14:51:14 UTC

#4 An Algorithm for the Assignment Game Beyond Additive Valuations [PDF] [Copy] [Kimi]

Authors: Eric Balkanski ; Christopher En ; Yuri Faenza

The assignment game, introduced by Shapley and Shubik (1971), is a classic model for two-sided matching markets between buyers and sellers. In the original assignment game, it is assumed that payments lead to transferable utility and that buyers have unit-demand valuations for the items being sold. Two important and mostly independent lines of work have studied more general settings with imperfectly transferable utility and gross substitutes valuations. Multiple efficient algorithms have been proposed for computing a competitive equilibrium, the standard solution concept in assignment games, in these two settings. Our main result is an efficient algorithm for computing competitive equilibria in a setting with both imperfectly transferable utility and gross substitutes valuations. Our algorithm combines augmenting path techniques from maximum matching and algorithms for matroid intersection. We also show that, in a mild generalization of our model, computing a competitive equilibrium is NP-hard.

Subjects: Discrete Mathematics ; Computer Science and Game Theory

Publish: 2024-06-19 15:16:34 UTC

#5 Nash equilibria of quasisupermodular games [PDF] [Copy] [Kimi]

Author: Lu Yu

We prove three results on the existence and structure of Nash equilibria for quasisupermodular games. A theorem is purely order-theoretic, and the other two involve topological hypotheses. Our topological results genralize Zhou's theorem (for supermodular games) and Calciano's theorem.

Subjects: Theoretical Economics ; Computer Science and Game Theory

Publish: 2024-06-19 19:13:37 UTC

#6 Guaranteed shares of benefits and costs [PDF] [Copy] [Kimi]

Authors: Anna Bogomolnaia ; Hervé Moulin

In a general fair division model with transferable utilities we discuss endogenous lower and upper guarantees on individual shares of benefits or costs. Like the more familiar exogenous bounds on individual shares described by an outside option or a stand alone utility, these guarantees depend on my type but not on others' types, only on their number and the range of types. Keeping the range from worst share to best share as narrow as permitted by the physical constraints of the model still leaves a large menu of tight guarantee functions. We describe in detail these design options in several iconic problems where each tight pair of guarantees has a clear normative meaning: the allocation of indivisible goods or costly chores, cost sharing of a public facility and the exploitation of a commons with substitute or complementary inputs. The corresponding benefit or cost functions are all sub- or super-modular, and for this class we characterise the set of minimal upper and maximal lower guarantees in all two agent problems.

Subjects: Theoretical Economics ; Computer Science and Game Theory

Publish: 2024-06-20 11:03:51 UTC

#7 A Lower Bound on Swap Regret in Extensive-Form Games [PDF] [Copy] [Kimi]

Authors: Constantinos Daskalakis ; Gabriele Farina ; Noah Golowich ; Tuomas Sandholm ; Brian Hu Zhang

Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach $\epsilon$ average swap regret against an adversary in any extensive-form game within $m^{\tilde{\mathcal O}(1/\epsilon)}$ rounds, where $m$ is the number of nodes in the game tree. However, the question of whether a $\mathrm{poly}(m, 1/\epsilon)$-round algorithm could exist remained open. In this paper, we show a lower bound that precludes the existence of such an algorithm. In particular, we show that achieving average swap regret $\epsilon$ against an oblivious adversary in general extensive-form games requires at least $\mathrm{exp}\left(\Omega\left(\min\left\{m^{1/14}, \epsilon^{-1/6}\right\}\right)\right)$ rounds.

Subject: Computer Science and Game Theory

Publish: 2024-06-19 00:09:04 UTC

#8 Submodular Participatory Budgeting [PDF] [Copy] [Kimi]

Authors: Jing Yuan ; Shaojie Tang

Participatory budgeting refers to the practice of allocating public resources by collecting and aggregating individual preferences. Most existing studies in this field often assume an additive utility function, where each individual holds a private utility for each candidate project, and the total utility of a set of funded projects is simply the sum of the utilities of all projects. We argue that this assumption does not always hold in reality. For example, building two playgrounds in the same neighborhood does not necessarily lead to twice the utility of building a single playground. To address this, we extend the existing study by proposing a submodular participatory budgeting problem, assuming that the utility function of each individual is a monotone and submodular function over funded projects. We propose and examine three preference elicitation methods, including \emph{ranking-by-marginal-values}, \emph{ranking-by-values} and \emph{threshold approval votes}, and analyze their performances in terms of distortion. Notably, if the utility function is addicative, our aggregation rule designed for threshold approval votes achieves a better distortion than the state-of-the-art approach.

Subjects: Computer Science and Game Theory ; Artificial Intelligence

Publish: 2024-06-19 14:22:54 UTC

#9 Symmetrically Fair Allocations of Indivisible Goods [PDF] [Copy] [Kimi]

Authors: Connor Johnston ; Aleksandr M. Kazachkov

We consider allocating indivisible goods with provable fairness guarantees that are satisfied regardless of which bundle of items each agent receives. Symmetrical allocations of this type are known to exist for divisible resources, such as consensus splitting of a cake into parts, each having equal value for all agents, ensuring that in any allocation of the cake slices, no agent would envy another. For indivisible goods, one analogous concept relaxes envy freeness to guarantee the existence of an allocation in which any bundle is worth as much as any other, up to the value of a bounded number of items from the other bundle. Previous work has studied the number of items that need to be removed. In this paper, we improve upon these bounds for the specific setting in which the number of bundles equals the number of agents. Concretely, we develop the theory of symmetrically envy free up to one good, or symEF1, allocations. We prove that a symEF1 allocation exists if the vertices of a related graph can be partitioned (colored) into as many independent sets as there are agents. This sufficient condition always holds for two agents, and for agents that have identical, disjoint, or binary valuations. We further prove conditions under which exponentially-many distinct symEF1 allocations exist. Finally, we perform computational experiments to study the incidence of symEF1 allocations as a function of the number of agents and items when valuations are drawn uniformly at random.

Subjects: Computer Science and Game Theory ; Optimization and Control

Publish: 2024-06-19 20:34:08 UTC

#10 Bundling in Oligopoly: Revenue Maximization with Single-Item Competitors [PDF] [Copy] [Kimi]

Authors: Moshe Babaioff ; Linda Cai ; Brendan Lucier

We consider a principal seller with $m$ heterogeneous products to sell to an additive buyer over independent items. The principal can offer an arbitrary menu of product bundles, but faces competition from smaller and more agile single-item sellers. The single-item sellers choose their prices after the principal commits to a menu, potentially under-cutting the principal's offerings. We explore to what extent the principal can leverage the ability to bundle product together to extract revenue. Any choice of menu by the principal induces an oligopoly pricing game between the single-item sellers, which may have multiple equilibria. When there is only a single item this model reduces to Bertrand competition, for which the principal's revenue is $0$ at any equilibrium, so we assume that no single item's value is too dominant. We establish an upper bound on the principal's optimal revenue at every equilibrium: the expected welfare after truncating each item's value to its revenue-maximizing price. Under a technical condition on the value distributions -- that the monopolist's revenue is sufficiently sensitive to price -- we show that the principal seller can simply price the grand-bundle and ensure (in any equilibrium) a constant approximation to this bound (and hence to the optimal revenue). We also show that for some value distributions violating our conditions, grand-bundle pricing does not yield a constant approximation to the optimal revenue in any equilibrium.

Subjects: Computer Science and Game Theory ; Theoretical Economics

Publish: 2024-06-19 20:59:02 UTC

#11 Planning Against a Prophet: A Graph-Theoretic Framework for Making Sequential Decisions [PDF] [Copy] [Kimi]

Authors: Andrés Cristi ; Sigal Oren

We devise a general graph-theoretic framework for studying prophet inequalities. In this framework, an agent traverses a directed acyclic graph from a starting node $s$ to a target node $t$. Each edge has a value that is sampled from a known distribution. When the agent reaches a node $v$ it observes the realized values of all the outgoing edges from $v$. The agent's objective is to maximize the expected total value of the path it takes. As in prophet inequalities, we compare the agent's performance against a prophet who observes all the realizations of the edges' values ahead of time. Our analysis reveals that this ratio highly depends on the number of paths $k$ required to cover all the nodes in the graph. In particular, we provide an algorithm that guarantees a prophet inequality ratio of $\frac{1}{2k}$ and show an upper bound of $\frac{1}{k+1}$. Our framework captures planning problems in which there is uncertainty regarding the costs/benefits of each action. In particular, it captures an over-time variant of the classic prophet inequality in which a seller leases a durable item, such as an apartment, for $n$ time units. Each period a lessee appears and may have a different value for each lease term. We obtain a tight bound of $1/2$ for this variant. To make this framework even more expressive, we further generalize it to accommodate correlations between edges originating from the same node and allow for additional constraints on the edges the agent can take. The generalized framework captures many well-studied prophet inequality problems, including $d$-dimensional matching, $k$-prophet inequality, and more.

Subject: Computer Science and Game Theory

Publish: 2024-06-20 00:56:32 UTC

#12 Tracking solutions of time-varying variational inequalities [PDF] [Copy] [Kimi]

Authors: Hédi Hadiji ; Sarah Sachs ; Cristóbal Guzmán

Tracking the solution of time-varying variational inequalities is an important problem with applications in game theory, optimization, and machine learning. Existing work considers time-varying games or time-varying optimization problems. For strongly convex optimization problems or strongly monotone games, these results provide tracking guarantees under the assumption that the variation of the time-varying problem is restrained, that is, problems with a sublinear solution path. In this work we extend existing results in two ways: In our first result, we provide tracking bounds for (1) variational inequalities with a sublinear solution path but not necessarily monotone functions, and (2) for periodic time-varying variational inequalities that do not necessarily have a sublinear solution path-length. Our second main contribution is an extensive study of the convergence behavior and trajectory of discrete dynamical systems of periodic time-varying VI. We show that these systems can exhibit provably chaotic behavior or can converge to the solution. Finally, we illustrate our theoretical results with experiments.

Subjects: Computer Science and Game Theory ; Machine Learning ; Optimization and Control ; Machine Learning

Publish: 2024-06-20 07:32:07 UTC

#13 Tractable Equilibrium Computation in Markov Games through Risk Aversion [PDF] [Copy] [Kimi]

Authors: Eric Mazumdar ; Kishan Panaganti ; Laixi Shi

A significant roadblock to the development of principled multi-agent reinforcement learning is the fact that desired solution concepts like Nash equilibria may be intractable to compute. To overcome this obstacle, we take inspiration from behavioral economics and show that -- by imbuing agents with important features of human decision-making like risk aversion and bounded rationality -- a class of risk-averse quantal response equilibria (RQE) become tractable to compute in all $n$-player matrix and finite-horizon Markov games. In particular, we show that they emerge as the endpoint of no-regret learning in suitably adjusted versions of the games. Crucially, the class of computationally tractable RQE is independent of the underlying game structure and only depends on agents' degree of risk-aversion and bounded rationality. To validate the richness of this class of solution concepts we show that it captures peoples' patterns of play in a number of 2-player matrix games previously studied in experimental economics. Furthermore, we give a first analysis of the sample complexity of computing these equilibria in finite-horizon Markov games when one has access to a generative model and validate our findings on a simple multi-agent reinforcement learning benchmark.

Subjects: Computer Science and Game Theory ; Machine Learning ; Multiagent Systems

Publish: 2024-06-20 09:53:56 UTC

#14 Mechanism design augmented with output advice [PDF] [Copy] [Kimi]

Authors: George Christodoulou ; Alkmini Sgouritsa ; Ioannis Vlachos

Our work revisits the design of mechanisms via the learning-augmented framework. In this model, the algorithm is enhanced with imperfect (machine-learned) information concerning the input, usually referred to as prediction. The goal is to design algorithms whose performance degrades gently as a function of the prediction error and, in particular, perform well if the prediction is accurate, but also provide a worst-case guarantee under any possible error. This framework has been successfully applied recently to various mechanism design settings, where in most cases the mechanism is provided with a prediction about the types of the players. We adopt a perspective in which the mechanism is provided with an output recommendation. We make no assumptions about the quality of the suggested outcome, and the goal is to use the recommendation to design mechanisms with low approximation guarantees whenever the recommended outcome is reasonable, but at the same time to provide worst-case guarantees whenever the recommendation significantly deviates from the optimal one. We propose a generic, universal measure, which we call quality of recommendation, to evaluate mechanisms across various information settings. We demonstrate how this new metric can provide refined analysis in existing results. This model introduces new challenges, as the mechanism receives limited information comparing to settings that use predictions about the types of the agents. We study, through this lens, several well-studied mechanism design paradigms, devising new mechanisms, but also providing refined analysis for existing ones, using as a metric the quality of recommendation. We complement our positive results, by exploring the limitations of known classes of strategyproof mechanisms that can be devised using output recommendation.

Subject: Computer Science and Game Theory

Publish: 2024-06-20 10:10:21 UTC